Труды КНЦ вып.124 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 5/2014(24))

отличие от методов систематического перебора методы локального поиска обладают следующими преимуществами: • сравнительно низкой вычислительной сложностью относительно числа переменных; • при незначительном изменении условий уже решённой задачи можно использовать полученное для неё решение в качестве отправной точки для поиска новых решений; • алгоритмы подобного класса, как правило, легко поддаются распа­ раллеливанию. К недостаткам методов данного класса относится то, что они могут не найти решение CSP даже при его существовании, или найти лишь локальный экстремум оптимизируемой функции. Дело в том, что в пространстве состояний могут встречаться области, для которых нельзя выбрать преемника текущего состояния (соседнее состояние), улучшающего значение функции оценки. К таким областям можно отнести плато (участки пространства поиска, на которых функция оценки не изменяется) и хребты (последовательности близко распо­ ложенных локальных максимумов). К алгоритмам локального поиска относятся: • генетические алгоритмы; • алгоритмы лучевого поиска; • роевой интеллект: муравьиный алгоритм, пчелиный алгоритм, метод роя частиц и др.; • стохастические методы (имитация отжига). В публикациях [3-5] описаны разработанные одним из авторов методы распространения ограничений и эвристического поиска, ориентированные на систематический поиск решений и использующие матрицеподобные структуры алгебры кортежей (АК). Алгебра кортежей - алгебраическая система, пред­ назначенная для моделирования и анализа многоместных отношений, с ее помощью удобно анализировать ограничения с конечными доменами. Поиск на основе этих методов, в отличие от методов полного перебора, состоит из последовательности таких шагов, как а) редукция пространства поиска и Ь) выбор на основе эвристик того преемника текущей вершины дерева поиска, который способен быстрее всего привести к цели. Созданные методы поиска позволили на практике эффективно решать многие задачи CSP, имеющие высокую вычислительную сложность в теории. Базовые структуры, операции и алгоритмы АК, использующие концеп­ цию дерева поиска, реализованы в виде специализированной программной библиотеки [ 6 ]. При её создании был применим язык программирования C++ и RAD C++ Builder 6 . Далее в настоящей работе подробно рассматриваются недостатки упомянутой библиотеки, и предлагается подход к созданию среды для программирования задач удовлетворения ограничений в терминах АК, свобод­ ной от подобных недостатков и поддерживающей методы локального поиска, а также отвечающей современным требованиям к свободно распространяемому программному обеспечению. 160