Гибридный алгоритм решения задачи удовлетворения ограничений

Abstract

Представлен гибридный алгоритм improved Guided Local and Systematic Search для решения распределенной задачи удовлетворения ограничений. Алгоритм объединяет компоненты локального и конструктивного поиска. Доказаны полнота и корректность алгоритма. Приведены результаты его экспериментальной оценки на модельной задаче о ферзях и проведено сравнение его производительности с производительностью алгоритмов Dis-GLS и iGL.

The improved Guided Local and Systematic Search hybrid algorithm is presented for solving the Distributed Constraint Satisfaction Problem, which combines two local and one systematic search methods. The completeness and correctness of the algorithm are proved. The results of our experiments with queens' problem, and a comparison of productivity for our hybrid and two other algorithms Dis-GLS and iGL are given.

Представлено гібридний алгоритм improved Guided Local and Systematic Search розв’язання розподіленої задачі задоволення обмежень, який поєднує компоненти локального та конструктивного пошуку. Доведено повноту і коректність алгоритму. Описано результати його експериментальної оцінки на модельній задачі про ферзі. Проведено порівняння його продуктивності з продуктивністю алгоритмів класу Dis-GLS та iGL.