автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Об эффективных алгоритмах для задачи CSP и их программной реализации

□ □3 1*72235

Государственное образовательное учреждение высшего профессионального образования ¡Уральский государственный университет им А М Горького»

На правах рукописи

СКВОРЦОВ Евгений Сергеевич

Об эффективных алгоритмах

для задачи СЭР и их программной реализации

05 13 18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург 2 и.пг ?прг

2008 '

003172235

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Уральский государственный университет им А М Горького» на кафедре алгебры и дискретной математики

Научный руководитель доктор физико-математических наук,

профессор М В Волков

Официальные оппоненты доктор физико-математических наук,

профессор М Ю Хачай

кандидат физико-математических наук, доцент Э А Гирш

Ведущая организация Саратовский государственный университет

им Н Г Чернышевского

Защита состоится 18 июня 2008 г в часов на заседании диссерта-

ционного совета Д 212 286 10 по защите докторских и кандидатских диссертаций при Уральском государственном университете им А М Горького по адресу 620083, г Екатеринбург, пр Ленина, 51, комн 248

С диссертацией можно ознакомиться в научной библиотеке Уральского государственного университета им А М Горького

Автореферат разослан « __ 2008 г

Ученый секретарь диссертационного совета, доктор физико-математических наук, профессор

В Г Пименов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы С расширением области применения компьютерных технологий растет количество комбинаторных задач, используемых в приложениях В этой ситуации оказываются востребованы эффективные универсальные алгоритмы, применимые к широким классам задач

Данная работа относится к исследованию комбинаторной задачи CSP (от английского 'Constraint Satisfaction Problem', в немногочисленной русскоязычной литературе встречается также название Обобщенная выполнимость [1]) Цель данного направления - разработать эффективные универсальные алгоритмы для задач из класса NP Задача CSP является лишь одной из многих известных NP-полных задач, однако в последнее десятилетие стало ясно, что она занимает особое место Хотя по самому определению NP-полной задачи к любой такой задаче сводится любая задача из класса NP, соответствующее сведение зачастую оказывается громоздким и искусственным Преимущество задачи CSP состоит в том, что большинство комбинаторных задач может быть представлено в виде CSP просто и естественно Многие комбинаторные задачи могут быть естественным образом охарактеризованы как подклассы задачи CSP

В задаче CSP даны множество переменных, множество их возможных значении, а также заданы ограничения на значения переменных Каждое ограничение состоит из вектора переменных s и отношения р на множестве значений переменных Ограничение считается выполненным, если вектор значений переменных s принадлежит р Требуется указать значения переменных так, чтобы выполнялись все ограничения Впервые общая задача CSP была введена Монтанари в 1974 г [43] при решении одной из задач машинного зрения - распознавания формы многогранников по их двумерному изображению В последующие годы этот формализм с успехом использовался для моделирования как дискретных, так и непрерывных прикладных задач а затем и разработки универсальных алгоритмов для их решения Теория задачи CSP находит применение в таких областях, как теория реляционных баз данных [37,54], временная и пространственная логика [52] распознавание образов [43], автоматическое доказательство

теорем [14], техническое проектирование [46], анализ языков программирования [45] и естественных языков [3], биоинформатика [39] и многих других

Для многих задач очевиден естественный способ представления в виде CSP Например, fc-раскраска графа - это в точности задача CSP на /¡-элементном множестве, в которой в качестве отношения ограничения используется только неравенство Популярная игра Судоку может быть представлена в виде задачи CSP, при помощи отношения Sv(s) = «ровно одна из переменных из s равна v» Легко видеть, что любая система уравнений есть не что иное, как задача CSP, отношениями ограничения которой являются множества векторов, удовлетворяющие каждому отдельному уравнению Разумеется, существуют задачи, для которых способ представления в виде CSP неочевиден К таковым относится, например, задача о пространственной структуре молекул белка, однако и в таких случаях задача CSP зачастую оказывается весьма полезной [5,39]

В настоящее время существуют специальные декларативные языки программирования ECLiPSe [4], Oz [49], 2LP [41], CHIP [26], в которых для решения задачи достаточно записать ее в виде CSP Существуют библиотеки с подобной функциональностью для С++ (например ILOG [48]), расширениями, позволяющими решать задачу CSP, снабжено большинство современных версий Prolog [44] Язык Newton [27] позволяет решать разновидность задачи CSP в которой областью значений переменных является множество рациональных чисел Практическая полезность таких программных продуктов напрямую зависит от эффективности алгоритмов, применяемых для решения задачи CSP

Частным случаем задачи CSP, в котором множество значений переменных двухэлементно, а разрешенные ограничения - дизъюнкции литералов (клозы), является задача выполнимость, одна из первых задач, NP-полнота которых была доказана [2,13] Задача выполнимость представляет самостоятельный интерес, так как формулируется она проще, чем CSP, и в то же время сведение задачи CSP к задаче Выполнимость не составляет труда

Сама задача Выполнимость является в настоящее время объектом активного исследования Ей посвящена ежегодная конференция SAT (это

название является сокращением от SATISFIABILITY - английского названия задачи ВЫПОЛНИМОСТЬ), проводящаяся с 1996 г С 2005 г в Нидерландах выпускается специализированный журнал JSAT (Journal on Satisfiability, Boolean Modeling and Computation) Важное место в исследовании задачи ВЫПОЛНИМОСТЬ занимает разработка реально работающих программ-решателей При конференции SAT регулярно проходит соревнование таких программ, в котором принимают участие десятки программных продуктов, созданных специалистами со всего мира Прогресс, достигнутый в разработке алгоритмов для практических задач огромен многие задачи, еще 10 лет назад считавшиеся практически неразрешимыми, современными программами могут быть решены за доли секунды

Возможный путь решения задачи CSP - это сведение ее к задаче Выполнимость и использование эффективных эвристических алгоритмов для последней Однако богатый язык общей задачи CSP позволяет сохранить при моделировании структуру исходной задачи, что дает ряд преимуществ Во-первых, как было отмечено выше, многие задачи могут быть естественным образом охарактеризованы как ограниченные задачи CSP Во-вторых, большая структурированность задачи позволяет переносить в теорию CSP алгоритмы, разработанные для других комбинаторных задач Кроме того, язык задачи CSP оказывается проще для понимания, поэтому запись задачи в виде CSP на практике оказывается предпочтительнее кодирования в виде задачи ВЫПОЛНИМОСТЬ с точки зрения взаимодействия с заказчиком при моделировании предметной области

Постановка основных задач Для CSP, как и для любой NP-полпой задачи, не известно алгоритмов, эффективных в худшем случае, однако существует несколько подходов, использование которых позволяет решать за приемлемое время многие классы задачи CSP, возникающие в практических приложениях В данной диссертации затрагиваются три таких подхода

1) На языке CSP может быть сформулированы все задачи из класса NP, а значит и полиномиальные, поэтому важным направлением в исследовании задачи CSP является идентификация полиномиальных подклассов и разработка для них эффективных алгоритмов

Естественный способ выделения подзадач СЭР состоит в задании множества отношений, разрешенных для использования в ограничениях Для каждого такого множества Г через С5Р(Г) обозначается множество задач СЭР, в которых множество отношений, используемых в ограничениях, содержится в Г

В 1978 г Шефер [51], изучая ограниченные классы задачи СЭР на двухэлементном множестве, показал, что каждый такой класс либо КР-полон, либо имеет полиномиальный алгоритм, решающий его Кроме того, он нашел критерий, разделяющий легкие и трудные задачи В этой же работе Шефер поставил проблему поиска аналогичного критерия для общей задачи СЭР для каждого множества отношений Г определить сложность задачи С8Р(Г) и найти для нее полиномиальный алгоритм, если таковой существует Множество отношений Г, для которого задача СБР(Г) полиномиальна, называется полиномиальным

Полиномиальные множества отношений могут быть заданы многими разными способами Например, в [17] с использованием техники логического программирования и методов теории групп удалось выявить два больших класса задач СЭР, решаемых за полиномиальное время В частности, в эти классы попадают все «легкие» задачи СЭР, найденные Шефером Иной подход был предложен в [34,35], где полиномиальные множества задавались с помощью некоторых инвариантов Этот подход был развит в [8,9]

Предпринимались также попытки выделить классы задач СЭР, которые могут быть сконструированы из более простых задач так, чтобы решение каждой конкретной задачи сводилось к решению составляющих ее компонент Такому разложению могут быть подвергнуты как диофантовы формулы из задачи СЭР [12,15,19,21,22], так и множества отношений [10,11]

В [10,11] новые множества отношений строятся с помощью операции амальгамирования Амальгамой множеств отношений В.а,11в на множествах А и В соответственно называется множество отношений Дв) на множестве А и В, состоящее из всевозможных объединений дл и дв, где € 11а, Вв £ Дв - отношения одинаковой арности Нетрудно показать, что задача СЭР, соответствующая амальгаме двух множеств, не менее сложна, чем ее составляющие Кроме того, амальгама двух полино-

миальных множеств не всегда полиномиальна Даже тогда, когда она полиномиальна, алгоритм, сводящий ее к составляющим, может быть весьма нетривиальным

В [10] был рассмотрен случай, когда множества А и В дпзыонктны В этом случае при некоторых необременительных ограничениях амальгама полиномиальна тогда и только тогда, когда исходные множества отношений полиномиальны, а алгоритм декомпозиции тривиален В работе [11] в предположении равенства множеств, на которых заданы отношения, указано несколько частных типов полиномиальных амальгам, важных с прикладной точки зрения Первой основной задачей является вопрос об условиях полиномиальности амальгамы двух клонов в общем случае

2) Вероятностное распределение интересующей нас задачи может быть таким, чго существует алгоритм, получающий решение (или хорошее приближение решения) за приемлемое время с большой вероятностью, в то время как в худшем случае задача может оказаться очень сложной или даже алгоритмически неразрешимой Более того, оценка эффективности алгоритма с позиции анализа худшего случая зачастую не отражает ни результаты экспериментов, пи его практическую полезность Классическим примером является алгоритм решения задач лннейного программирования симплекс-метод, являющийся экспоненциальным с точки зрения анализа худшего случая, широко используется на практике

Вероятностный анализ способен дать более адекватную оценку эффективности алгоритма в этот анализ могут быть вовлечены два вероятностных пространства, во-первых, сам алгоритм можег быть стохастическим и выдавать различные результаты в применении к одной и той же задаче, во-вторых, в анализе может быть учтено вероятностное распределение поступающих задач Распространенным подходом является комбинирование этих пространств и вычисление вероятности того или иного результата при поступлении на вход стохастического алгоритма случайной задачи В диссертации вероятностный анализ применяется к простейшему варианту локального поиска решения задачи з-выполнпмость

локальный Поиск (ЛП) относшся к числу стандартных приемов, используемых для решения КтР-полных задач, в частности задачи выпол-

НИМОСТЬ В отличие от систематического поиска, в котором происходит выбор значений переменных с откатом при появлении противоречия, в локальном поиске идет работа с векторами - наборами значений всех переменных Начальный набор значений выбирается случайно или следуя некоторой эвристике Затем на каждом шаге новый набор значений выбирается случайным образом из окрестности текущего в соответствии с некоторым вероятностным распределением

Локальный Поиск - один из первых алгоритмов, использованных для решения задачи выполнимость и ее оптимизационного варианта - задачи Максимальная Выполнимость С конца 1980-х гг внимание исследователей привлекали разные версии алгоритма ЛП, см , например, [23,50] Алгоритм UnitWalk [29], построенный на принципах локального поиска, в 2003 г занял первое место в одной из номинаций соревнования SAT Доказано [30], что некоторые варианты локального поиска даже в худшем случае находят решение задачи выполнимость за время, ограниченное экспонентой от количества переменных с основанием строго меньшим, чем 2

В простейшей версии ЛП, известной как Итеративное Улучшение [33], мы начинаем со случайного набора значений переменных и затем на каждом шаге изменяем значение одной из переменных, для которых это приводит к увеличению количества выполненных клозов Если таких переменных больше нет, то работа прекращается и возвращается найденный вектор Таким образом, работа алгоритма заканчивается, когда текущий набор значений переменных оказывается локальным максимумом количества выполненных клозов для данной формулы

Куцупиас и Пападимитриу [38] провели вероятностный анализ работы простейшей версии ЛП для модели, в которой равновероятны все формулы, истинные на заданном наборе значений, показав, что в этом случае ЛП находит решение Второй основной задачей диссертации является исследование эффективности алгоритма ЛП на задачах з-выполнимость, распределенных по другому закону, а именно, по закону Ф(п, дп) для заданного количества переменных п и константы д равновероятна любая задача, содержащая п переменных и [рп\ клозов Это распределение при-

влекает особое внимание, поскольку известно (см , например, [42]), что в зависимости от параметра р оно позволяет генерировать задачи различной сложности с ючки зрения как доказательства невыполнимости, так и нахождения решения

3) Популярным и продуктивным подходом V решению комбинаторных задач вообще и в частности задачи ВЫПОЛНИМОСТЬ, является применение генетических алгоритмов Генетические алгоритмы впервые рассматривались в [31] и позже стали широко известными благодаря работе [20] В генетических алгоритмах моделируются два основных механизма эволюции - наследование и естественный отбор, или выживание наилучших, которое приводит к исчезновению из популяции неприспособленных к среде индивидов В роли индивидов, как правило, выступают элементы области определения целевой функции а их приспособленность к окружающей среде задается значением целевой функции

Генетические алгоритмы находят широкое применение как в практических, так и теоретических областях компьютерных наук Генетический подход успешно применялся при конструировании самолетов [7], маршрутизации водопроводов [53] составлении расписаний [28] В то же время на основе генетического подхода разрабатываются эффективные эвристические алгоритмы для решения №-трудных комбинаторных задач Выполнимость [6], Задача Коммивояжера [24] и других

Различные варианты генетических алгоритмов применялись для решения задачи ВЫПОЛНИМОСТЬ (см , например, [16,18,25,36,55]) В статье [40] Лардо и др предложили гибридный алгоритм САБАТ, использующий ЛОКАЛЬНЫЙ ПОИСК при образовании новых индивидов в ходе эволюции Сравнение проведенное Лардо и др на задачах библиотеки ЭАТЫВ, показало, что такое совмещение оказывается более эффективным, чем каждый из подходов по отдельности

Работа генетического алгоритма, решающего оптимизационную задачу, строится по следующей схеме Прежде всего, некоторым образом (в простейшем варианте - случайным) генерируется начальная популяция Каждый индивид в ней - это строка, представляющая из себя код элемента множества, в котором ищется решение Затем популяция итеративно обнов-

ляется за счет того, что в нее добавляются потомки присутствующих в ней индивидов и удаляются «погибшие» особи Вероятность гибели индивида тем больше, чем меньше индивид приспособлен к среде, что соответствует худшему значению оптимизируемой функции

Третьей основной задачей диссертации является разработка эвристического алгоритма для задачи ВЫПОЛНИМОСТЬ, основанного на генетическом подходе и учитывающего влияние популяции на среду обитания, и оценка эффективности этого алгоритма путем его тестирования на общепринятом наборе тестовых задач

Цель работы, таким образом, состоит в решении следующих задач

• выяснить, каково устройство клона функций, сохраняющих амальгаму заданных клонов отношений, а также определить, в каких случаях амальгама клонов отношений полиномиальна,

• установить, каков наиболее вероятный результат применения алгоритма Локальный Поиск к случайной задаче ВЫПОЛНИМОСТЬ, поступающей в соответствии с распределением Ф(п,рп),

• разработать и протестировать эффективный генетический алгоритм для задачи ВЫПОЛНИМОСТЬ, учитывающий воздействие популяции на среду обитания

Методы исследования В диссертации используются методы теории клонов, теории вероятностей, а также экспериментальные данные по эффективности алгоритмов Локальный Поиск, GASAT и VEGAS

Научная новизна Основные результаты работы являются новыми и состоят в следующем дано описание устройства клона функций, сохраняющих амальгаму и установлен критерий полиномиальности амальгамы, получена система дифференциальных уравнений, описывающая процесс исполнения алгоритма Локальный Поиск, разработан генетический алгоритм для задачи Выполнимость, учитывающий влияние популяции на среду обитания, и проведены эксперименты свидетельствующие о его эффективности

Теоретическая и практическая ценность Результаты, полученные в областях поиска полиномиальных подзадач и вероятностного анализа алгоритмов, носят теоретический характер и могут быть использованы в теории алгоритмов

Результаты диссертации в области разработки генетических алгоритмов представляют практический интерес и могут быть использованы для создания программ-решателей практических задач

Апробация работы Результаты диссертации представлены на Всероссийской конференции «Дискретный анализ и исследование операции» (Новосибирск, 2002), на Мальцевских чтениях (Новосибирск, 2002), Объединенной конференции по искусственному интеллекту (Акапулько, Мексика 2003), Объединенной конференции по логике (Сиэтл, США, 2006), международной конференции «Компьютерные науки в России» (Екатеринбург, 2007) Отметим, что отбор работ на последние три из перечисленных конференции осуществлялся в соответствии с принятой в компьютерных науках практикой т е на конкурсной основе на базе отзывов трех анонимных рецензентов отбиралась в среднем одна работа из трех представленных Результаты диссертации докладывались также на алгебраических и алгоритмических семинарах Уральского государственного университета и университета Саймона Фрэйзера (Ванкувер Канада)

Публикации по теме диссертации Основные результаты диссертации отражены в семи публикациях автора [57-63] В трех совместных работах с А А Булатовым последнему принадлежит постановка задачи и общая методика исследований, доказательства всех основных утверждений принадлежат диссертанту Совместная работа с Е Амири выполнена в неразрывном соавторстве Работа [58] опубликована в издании, входившем в перечень ВАК на момент публикации

Структура и объем работы Диссертационная работа состоит из 97 страниц машинописного текста, включающего введение три главы, а также рисунки, таблицы и список литературы из 74 наименований

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается история проблем, решаемых в диссертации, даются общие определения

В главе 1 решается вопрос о полиномиальности амальгамы множеств отношений Для решения поставленной задачи мы используем предложенную в [34,35] методику, опирающуюся на достижения теории клонов Напомним, что клоном функций на множестве А называется семейство функций, замкнутое относительно суперпозиции и содержащее все проекции, т е функции вида eln(xi> >хп) — Далее, каждому n-местному отношению д на А естественным образом соответствует n-местный предикат Ре Это позволяет ввести следующее понятие Множество отношений Г называется клоном отношений, если оно содержит отношение равенства и для любых ßi, , Qk € Г содержит отношение д определяемое предикатом

I '^п ) = Э уи ,утФ{х 1, ) > 2/Ъ I Ут ),

где формула в правой части диофантова и ее атомарные формулы суть Pßl, , Рек Говорят, что п-местная функция / сохраняет m-местное отношение р, если результат построчного применения / к любой матрице тхп, столбцами которой являются элементы р, принадлежит р Множество всех функций, сохраняющих все отношения из Г, обозначается через Ро1(Г), множество всех отношений, сохраняемых всеми функциями из С, обозначается через Inv(C) Как хорошо известно |47], множества вида Ро1(Г) -это в точности клоны функций, а вида Inv(C) - клоны отношений, причем операции Inv и Pol задают соответствие Галуа между решетками клонов функций и отношений

Говорят, что конечное множество отношений Г полиномиально, если полиномиален класс задач CSP(r), а бесконечное множество отношении Г полиномиально, если полиномиальны все его конечные подмножества Клоны отношений играют важную роль в изучении задачи CSP ввиду того что, как было установлено в [34], если множество отношений Г полиномиально, то полиномиален и клон отношений (Г), порожденный этим множеством В то же время полиномиальность клона отношений R может быть проверена по наличию определенных функций в клоне Ро1(й)

Основным рабочими понятием в изучении клона функций, соответствующего амальгаме, является понятие схемы, собранной из функций клонов /<1, ,Р„ Для краткости мы приведем здесь определение схемы в случае п = 2 (В диссертации схема определяется для произвольного п) Пусть клоны функций FJ4,Fв определены на множествах А и В ответственно Через 2 мы будем обозначать множество {А, В}, через С - множество АГ\В, а через О - множество АиВ Вектор (Хь € мы будем на-

зывать шаблоном вектора х = £ если хг 6 X, Множество

векторов, являющихся шаблонами х, мы будем обозначать через Ф(£)

Если Ф - шаблон х, и X - элемент Z, то через х<$\х мы будем обозначать вектор, полученный из х опусканием координат, на местах которых в Ф стоит не X Через (¡хФ мы обозначаем количество вхождении X в Ф

Функция / Сп —+ С арности п называется схемой, собранной из функций клонов Ра,Рв, если существуют функция Г 2п —» 2 и семейство функций

Б = {/Ф|Фе£"Лаг(/Ф)=^(Ф)(Ф)},

содержащееся в РА и Р^ таких, что для всех х и всех Ф € Ф(т) выполня-еюя равенство /(а?) = Функция Г называется метафунщией

функции /, а функции из множества В - ее деталями

Другими словами, схемой называется такая функция, которая на векторах данного шаблона действует как некоторая определяемая по шаблону функция /ф, принадлежащая одному из клонов Ра,Рв Множество всех схем, собранных из функций клонов Рд,Рв, мы обозначаем через 5(^4, ^д) Первым основным результатом главы 1 является

Теорема 1 3 Имеет место равенство

Ро1(А(Яь ,Дп))=5(Ро!(Д1)) ,Ро1(Дп))

Обозначим клоны (А(Л41 Дл|С)} и (А(Яв, Яв\С)) через К\ и Яд соответственно Клон Яд называется монолитным, ни одно из его унарных отношении не содержится в Л\С Оказывается, если клон Яд монолитен, то задача С8Р(А(Ду1, Яв)) сводится к СЗР(Дд) Таким образом, наибольший интерес представляет случай, когда существуют такие унарные отношения

Еа € К-А, Ев £ Дв, что ЕаГ\С = ЕвПС = 0 В этом случае мы указываем следующий критерий полиномиальности амальгамы, который является вторым основным результатом главы 2

Теорема 1 6 Если клоны Яа и Яд немонолитны, то клон (А(Ла,Йв)) полиномиален тогда и только тогда, когда полиномиальны клоны Д+ и (ЯА и Кв)

В главе 2 исследуются алгоритм локальный поиск (лп) и его ослабленная версия локальный поиск за Один просмотр (ЛПОП) На вход им подается булева формула Ф, сгенерированная в соответствии с распределением Ф(п, дп) для заданного количества переменных п и константы д равновероятна любая 3-КНФ, содержащая п переменных и [ртг] клозов Псевдокод алгоритмов представлен на рис 1 В нем через ИЛ(Ф, х) обозначено множество переменных, изменение значения которых в х приводит к увеличению количества выполненных клозов в Ф(а?)

Алгоритм Локальный Поиск (ЛП)

Выборать набор значений х равномерно случайно Пока \¥(Ф,х) ф 0

Выбрать XI 6 И^(Ф,х) равномерно случайно Изменить значение а;( на противоположное

Алгоритм Локальный Поиск за Один Просмотр (ЛПОП)

Выборать набор значений х равномерно случайно Для каждой переменной хг от XI до хп Если Хг € \У(Ф,х) то изменить значение на противоположное

Рис 1 Псевдокод алгоритмов ЛП и ЛПОП

Мы используем принципиально различные модели для анализа ЛП и ЛПОП, однако и в том и в другом случае ключевым моментом нашего анализа является применение теоремы Вормальда [56], позволяющей доказать близость заданных параметров случайного процесса к решению некоторой системы дифференциальных уравнений

Мы пользуемся следующими определениями из теории вероятности Событие А(п) происходит почти наверняка при п, стремящемся к бесконечности, если Р(Л(п)) —> 0 Пусть Х{п) - некоторая случайная величина,

п—>оо

а с - некоторая константа Говорят, что равенство Х(п) = сп 4- о(п) вы-полилстсл почти пйверплш при л, ипрыллщемся к бесконечности, если существуют бесконечно малые последовательности а(п),0(п) такие, что выполняется неравенство

Р(\Х(п) - сп\ > а{п)) </?(п)

В диссертации мы сокращаем «почти наверняка при количестве переменных в задаче стремящемся к бесконечности» до «почти наверняка»

При работе алгоритма ЛПОП после выполнения шага í переменные {хх, , были рассмотрены и в дальнейшем изменяться не будут Литералы, содержащие эти переменные, мы называем обработанными В модели алгоритма ЛПОП рассматриваются следующие множества

Ев - множество клозов, не содержащих обработанных литералов,

Е\ - множество клозов содержащих выполненный обработанный литерал,

Ео - множество клозов, содержащих три невыполненных обработанных литерала,

Е++ (£+_, Е__) - множества клозов, которые содержат ровно один обработанный невыполненный литерал и два (ровно один, ноль, соответственно) других литерала выполнены,

Е+ (Е-) - множество клозов, содержащих два невыполненных обработанных литерала в которых необработанный литерал выполнен (невыполнен), соответственно

Через еТ, т € {0,1,0, ++, -I—, —, +, —} мы обозначаем мощность множества Ет

Мы показываем, что параметры ет удовлетворяют условиям теоремы Вормальда, а следовательно, близки к решению некоторой явно выписываемой системы дифференциальных уравнений (см систему (2 8) в диссертации) Поскольку в конце работы алгоритма все литералы обработа-

ны, параметр ео оказывается равным количеству невыполненных клозов Таким образом, мы получаем первый основной результат главы 2

Теорема 2.2 Для любого положительного д существует константа с\ такая, что для случайной 3-КНФ, распределенной по закону Ф (п, дп), количество клозов, выполненных набором значений, получаемым по окончании работы алгоритма ЛПОП, почти наверняка равно + о(п)

Поскольку во время работы ЛП каждая переменная может изменять значение несколько раз, модель, разработанная для ЛПОП, оказывается неприменимой В модели, описывающей работу ЛП, мы рассматриваем множества {Еаь}, где а,Ь - неотрицательные целые числа Множество Еаь содержит такие переменные хи что если значение хг изменится, то ровно а невыполненных клозов станут выполненными и ровно b выполненных клозов перестанут быть выполненными Через еаь мы обозначаем мощность множества Еаь и через е совокупность значений еаь по всем неотрицательным целым a, b Ясно, что е изменяется в ходе работы ЛП

Наш анализ алгоритма ЛП основан на следующем допущении

Допущение 1 В предположении истории е(1), , е(£) процесса работы алгоритма ЛП для произвольного клоза С текущей формулы, произвольных позиций р,г в нем, р ^ г, любых 0.1,0.2,^1,62 и любых переменных х, £ Eaubi,x3 € Еаъьг, события "хг занимает позицию р клоза С" и "х} занимает позицию г клоза С" независимы

Оно представляется вполне правдоподобным, но мы пока не смогли дать чисто математического обоснования его справедливости Тем не менее мы считаем возможным принять это допущение, поскольку получаемые на его основе результаты весьма хорошо соответствуют экспериментальным данным Принимая допущение 1, мы можем применить теорему Вормальда к набору параметров е и получить описывающую их эволюцию систему дифференциальных уравнений (система (2 16) в диссертации) Изучая решения этой системы дифференциальных уравнений, мы получаем второй основной результат главы 2

Теорема 2 3 Для любого положительного а существует константа Сг такая, что для случайной 3-КНФ, распределенной по закону Ф(п, дп), количество клозов, выполненных набором значений, получаемым по окончании работы алгоритма ЛП, почти наверняка равно сгп + о(п)

Константы с\ и С2 были определены численным решением соответствующих систем дифференциальных уравнений, при этом был использован метод Рунге-Кутты четвертого порядка, реализованный в пакете Ма11аЬ При численном решении системы дифференциальных уравнении для ЛП мы ограничиваем число переменных еаь условиями а < 20,6 < 20 Сравнение полученных значений с экспериментальными данными представлено в таблицах 1 и 2

в с (эксперимент) с (система (2 8))

3 2 95 2 95

4 3 91 3 91

10 9 53 9 52

Таблица 1 Зависимость качества решения, найденного алгоритмом ЛПОП, от плотности задачи Экспериментальные данные и предсказание системы (2 8)

о с (эксперимент) с (система (2 16))

3 2 936 2 933

4 3 884 3 878

10 9 430 9 429

Таблица 2 Зависимость качества решения, найденного алгоритмом ЛП, от плотности задачи Экспериментальные данные и предсказание сис1емы (2 16)

На рисунке 2 изображены графики зависимости количества неудовлетворенных клозов от времени работы алгоритма ЛП, полученные экспериментально и решением системы дифференциальных уравнений Можно сделать вывод, что решение системы дает очень точное приближение экспериментальных данных

В главе 3 описывается модификация генетического алгоритма решения задачи ВЫПОЛНИМОСТЬ, учитывающая влияние индивидов на окружаю-

Рис 2 Графики зависимости количества неудовлетворенных клозов от времени работы алгоритма ЛП Тонкие линии отражают значения, полученные из запусков алгоритма на конкретных задачах, а жирная линия отвечает результатам численного решения системы дифференциальных уравнений На оси ординат откладывается отношение числа невыполненных клозов к числу переменных, а на оси абсцисс - отношение числа проделанных шагов к числу переменных Наклонная часть графиков отражает работу алгоритма до попадания в локальный минимум, далее каждый график продолжается горизонтальной линией, соответствующей количеству клозов, неудовлетворенных в конце работы

щую среду Разработанный нами алгоритм мы назвали VEGAS (сокращенно от Valuation Enhanced Genetic Algorithm for Satisfability1) В то время как в классическом варианте популяция обитает и развивается в неизменном окружении, в предлагаемом нами алгоритме популяция и окружающая среда активно влияют друг на друга эволюционируя вместе В преллага-емой модели каждый клоз С мы считаем формой хищника и интерпретируем удовлетворение вектором х клоза С как способность существа х защититься от хищника С Эволюция среды в алгоритме VEGAS реализована следующим образом Когда в результате размножения появляется существо с генотипом х, хищники, от которых это существо не защищено, размножаются, что в терминах задачи выражается в увеличении веса клозов, которые нарушаются вектором х Увеличения весов невыполненных клозов производится на величину 5, которая является настроечным параметром алгоритма

Алгоритм был реализован на языке С++ в среде Microsoft Visual Studio Тестирование эффективности проводились на персональном компьютере Pentium IV тактовой частотой 3GHz Для того, чтобы оценить насколько включение воздействия индивидов на окружающую среду влияет на эффективность вычислений, мы сравниваем VEGAS с одним из лучших генетических алгоритмов - алгоритмом GASAT на ряде известных тестовых задач [32] Результаты тестирования представлены в таблице 3 В колонке время указано среднее время вычисления закончившегося решением задачи (в секундах), если задача была решена хотя бы один раз Если решение не было найдено, то в скобках указывается число невыполненых ограничений для наилучшего найденного индивида В таблице приведены результаты тестирования версии GASAT, выложенной на сайте авторов (колонка GAS AT), а также результаты, полученные самими авторами алгоритма GASAT (колонка GASAT(aBT))

Проведенные тесты показывают, что VEGAS может решить больший класс задач, чем GASAT, а задачи, посильные GASAT, алгоритм VEGAS решает за меньшее время, оказываясь таким образом сильнее своего предшественника Представляется, что предложенная нами модификация гене-

1Усиленный взвешиванием генетический алгоритм для задачи Выполнимость

Задачи VEGAS GASAT GASAT(aBT)

Файл Кол во Кол во Успех Время Успех Время Успех Время

aim-100-l_6-yesl-l cnf 100 160 100% 0,43 0% (1) 2% 2

aim-200-l_6-yesl-l cnf 200 320 85% 2,48 0% (1) - -

pai8-l-c cnf 64 254 100% 0,06 10% 0,17 100% 0,028

par8-l cnf 350 1149 100% 1,04 10% 41,87 17% 8,01

par8-2 cnf 350 1157 85% 1,45 0% (1) 25% 11,12

par32-5-c cnf 1339 5350 0% (4) 0% (13) 0% (5)

par32-5 cnf 3176 10325 0% (8) 0% (129) 0% (16)

color-15-4 cnf 900 45075 100% 14,91 100% 15 22 100% 479,248

color-22-5 cnf 2420 272129 40% 255 45 0% (3) 0% (5)

dpllulO bhuffled cnf 9197 25271 0% (2) 0% (81) 0% (36)

mat25 shuffled cnf 588 1968 0% (3) 0% (8) 0% (39)

mat26 shuffled cnf 744 2464 0% (2) 0% (8) 0% (56)

gl25 18 cnf 2250 70163 100% 5,92 100% 30,19 98% 92,0

g250 29 cnl 7250 454622 5% 313 08 0% (2) 0% (2)

Таблица 3 Таблица сравнения эффективности алгоритмов VEGAS и GASAT

тической модели заслуживает внимания и может быть применена и при решении других задач

Автор благодарит своего научного руководителя профессора М В Волкова за внимание к работе и помощь в подготовке текста диссертации, а также доцента А А Булатова за постановку задач и постоянное внимание к работе Автор с чувством глубокой благодарности вспоминает своего первого научного руководителя профессора Е В Суханова

Список литературы

[1| Гэри М , Джонсон Д Вычислительные машины и тпруднорешаемые задачи М Мир, 1982

[2] Левин Л А Универсальные- задачи перебора// Пробтемы передачи информации 1973 Т 9, №3 С 115-116

[3] Allen J Natural Language Understanding Benjamin Cummings, 1994

[4] Apt К , Wallace M Constraint Logic Programming using Eclipse Cambridge University Press, 2007

[5] Backofcn R , Will S A constraint-based approach to fast and exact structure prediction in three-dimensional protein models// Constraints 2006 Vol 11 № 1 P 5-30

[6] Bertoni A , Carpentien M , Cainpadelli P, Grossi G A genetic model Analysis and application to MAX-SAT// Evolutionary Computation 2000 Vol 8 P 291-310

[7] Bramelette M , Bouchard E Handbook of Genetic Algorithms Van Nostrand Remhold, 1991

[8] Bulatov A , Jeavons P, Kzokhin A Classifying the complexity of constraints using finite algebras// SIAM J Comput 2005 Vol 31, №3 P 720-742

[9] Bulatov A , Krokhm A , Jcavons P Constraint satisfaction problems and finite algebras// Proc 27th Int Colloq Automata Languages and Programming (ICALP'OO) LNCS Vol 1853 SnrmSPr, 9<WI P

[10] Cohen D, Jeaions P, Gault R New tractable classes from old// Principles and Practice of Constraint Programming CP'OO LNCS Vol 1894 Springer, 2000 P 1G0-171

[11] Cohen D , Jeavons P , Koubarakis M Building tractable disjunctive constraints// J ACM 2000 Vol 47 P 826-853

[12] Cohen D A Jeavons P , Gyssens M A structural decomposition for hypergraphs// Contemporary Mathematics 1994 Voll7S P161-177

[13] Cook S The complexity of theorem-proving procedures// 3id IEEE Symp the Foundations Coinput Sci 1971 P151-158

[14] Dechter R , Dechter A Structure-driven algorithms for truth maintenance// Artificial Intelligence 1996 Vol 82, №1-2 P1-20

[15] Dechter R, Pearl J Tree clustering for constraint networks// Artificial Intelligence 1989 Vol 38 P353-366

[16] Elben A E , Ven Der Hauw J K , Van Hemeit J I Graph coloring with adaptive evolutionary algorithms/; J Heuristics 1998 Vol 4, №1 P 25-46

[17] Feder T , Vardi M The computational structure of monotone monadic SNP and constraint satisfaction A study through datalog and group theory// SIAM J Comput 1998 Vol 28 P57-104

[18] Fleurent J , Ferland J Genetic algorithms and hybrids for graph coloring// Ann Operations Research 1996 Vol 63 P 437-461

[19] Freuder E Complexity of k-tree structured constraint satisfaction problems// 8th Nat Conf Artificial Intelligence AAAI'90 1990 P 4-9

¡20] Goldberg D Genetic Algorithms m Search, Optimization, and Machine Learning Addison-Wesley, 1989

[21] Gottlob G , Leone L, Scarcello F A comparison of structural CSP decomposition methods// Artificial Intelligence 2000 Vol 124, to 2 P 243-282

[22] Grohe M , Schwentick T , Segoufin L When is the evaluation of conjunctive queries tractable ?// 33rd Annual ACM Symp Theory of Computing ACM Press, 2001 P 657-666

¡23] Gu J Efficient local search for very large-scale satisfiability problem// ACM SIGART Bull 1992 Vol 3, №1 P 8-12

[24] Han H , Xiaowei Y , Zhifeng H Chunguo W , Yanrhun L , Xi Z Hybrid chromosome genetic algorithm for generalized traveling salesman problems// Adv Natural Comput LNCS Vol 3612 Springer, 2005 P137-140

[25] Hao J , Dome R A new population-based method for satisfiability problems// 11th European Conf Artificial Intelligence John Wiley & Sons, 1994 P 135-139

Hentenryck V The CLP language CHIP constraint solving and applications// Proc IEEE Comput Soc Int Conf 1991 P 382-387

Hentenryck V Michel L Neuiton Constraint programming over nonlinear real constraints// Sci Comput Programming 1997 Vol 30 P 83-118

Hiroaki U , Ouchi D , Takahashi К , Miyahara T A co-evolving timeslot/room assignment genetic algorithm technique for university timetabling// 3rd Int Conf Practice and Theory of Automated Timetabling LNCS Vol 2079 Springer, 2000 P 48-63

Hirsch E , Kojevmkov A UnitWalk A new SAT solver that uses local starch guided by unit clause elimination// Ann Math Artificial Intelligence 2001 Vol 43, №1-4 P 91-111 Hirsch E A Worst-case study of local search for Mux-k-Sat// Discrete Appl Math 2003 Vol 130 №2 P 173-184

Holland J Adaptation m Natural and Artificial Systems The University of Michigan Press, 1975

Hoos H Satisfiability Library// http //www satliborg (Электронный pecjpc) Hoos H , Stutzle T Stochastic Local Search, foundations and applications Elsevier, 2005 Jeavons P On the algebraic structure of combinatorial problemsЦ Theor Comput Sci 1998 Vol 200 P185-204

Jeavons P, Cohen D , Gysscns M Closure properties of constraints// J ACM 1997 Vol 44 P 527-548

Jong К D , Spcais W Using genetic algorithms to ¡olve np-complete problems// Proc Int Conf Genetic Algorithms 1989 P 124-132

Kolaitis P , Vardi M Conjunctive-query containment and constraint satisfaction// 3 Comput Syst Sci 2000 Vol 61, №2 P 302-332

Koutsoupias E , Papadimitnou С H On the greedy algorithm for satisfiability// Information Processing Letters 1992 Vol 43, № 1 P 53-55

Krippahl L , Barahona, P Applying constraint programming to protein structure determination/j Proc 5th Int Conf Constraint Programming LNCS Vol 1713 Sprmgei, 1999 P 289-302 Lardeux F , Saubion F Hao "I -K A hybrid genetic algorithm for the satisfiability problem// 1st Int Workshop on Heunstirs 2002 P 69-77

McAloon К , Tietkoff С SLP Linear programming ond logic programming// Principles and Practice of Constraint Programming MIT Press P 101-116

Mitchell D G , Selman Б , Lcvesque H 1 Hard and easy distributions for SAT problems// Proc 10th Mat Conf Artificial Intelligence AAAI Press, 1992 P 459-465 Montanan U Networks of constraints Fundamental properties and applications to picture processing// Information Sciences 1974 Vol 7 P 95-132

Narbom G A From Prolog III to Prolog IV The logic of constraint propramtmnp revisited// Constraints 1999 Vol 4, №4 P 313-335

Nadel В Constraint satisfaction in Prolog Complexity and theory-based heuristics// Information Scienccs 1995 Vol 83, №3-4 P 113-131

[46] Nadel В , Lin J Automobile transmission design as a constraint satisfaction problem Modeling the kinematik level/I Artificial Intelligence for Engineering Design, Anaysis and Manufacturing (AI EDAM) 1991 Vol 5, №3 P 137-171

Poschel R , Kaluimn L Funktioncn- und Relationenalgebren DVW, Berlin, 1979 Puget J F A С++ implementation of CLP// Proc 2nd Singapore Int Conf Intelligent Sys-temb 1j'j-l P 25G-2G1

Roy P V Logic programming in Oz with Mozart// Proc Int Conf on Logic programming 1999 P 38-51

Selman В , Levesque H , Mitchell D GSAT - A new method for solving hard satisfiability problems// 10th"Nat Conf Artificial Intelligence (AAAI-92) 1992 P 440-446 Schaefer T The complexity of satisfiability problems// Proc 10th ACM Symp Theory Cornp STOC'78 1978 P 21G-22G

Schwalb E , Vila L Temporal constraints a survey// Constraints 1998 Vol 3, №2-3 P 129149

Simpson A , Dandy G , Murphy L Genetic algorithms compared to other techniques for pipe optimization//} Water Resources Planning and Management 1994 Vol 120 №4 P 423-443 Vardi M Constraint satisfaction and database theory a tutorial// Proc 19th ACM Svmp Priciples of Database Systems (PODS'OO) 2000 P 76-85

Voorn R , Dastani M , Marchiori E Finding simplest pattern structures using genetic programming// Proc Genetic and Evolutionary Comput Conf 2001 P 3-10

Wormald N Differential equations for random processes and random graphs// Ann Appl Probability 1995 Vol 5, №4 P 1217-1235

Работы автора по теме диссертации

Булатов А , Скворцов Е Амальгамы комбинаторных задач// «Дискретный анализ и исследование операций» Mdi конф Новосибирск 2002 С 136

Скворцов Е О клонах на множестве и его частях// Алгебра и логика 2005 Т 44, № 1 С 97-113

Скворцов Е С VEGAS — новый генетический алгоритм для задачи Выполнимость// Изв Урал гос ун-та 2008 №62 С 192-207

Скворцов Е Решение задачи ВЫПОЛНИМОСТЬ генетическим алгоритмом// Тр 36-й молодеж школы-конф «Проблемы теоретической и прикладной математики» 2005 С 373-375

Amiri Е , Skvortsov Е S Pushing random walk beyond golden ratio // Computer Science -Theory and Applications CSR 2007 LNCS Vol 4649 Springer, 2007 P 44-55 Bulatov A , Skvortsov E Amalgams of constraint satisfaction problems// 18th Int Joint Conf Artificial Intelligence (IJCAI'03), Acapulco, Mexico 2003 P 197-202

Bulatov A , Skvortsov E Efficiency of local search// Theory and Applications of Satisfiability Testing - SAT 2006 LNCS Vol 4121 Springer, 2007 P 297-310

Введение

1 Общее описание проблематики.

2 Проблемы, решаемые в диссертации

2.1 Используемые подходы.

2.2 Амальгамы подклассов CSP.

2.3 Эффективность алгоритма Локальный Поиск

2.4 Алгоритм VEGAS.

1 Амальгамы подклассов CSP

1.1 Основные определения теории клонов и теории задачи CSP

1.1.1 Задача CSP.

1.1.2 Клоны.

1.1.3 Амальгамы клонов

1.2 Строение клона функций, сохраняющих амальгаму.

1.2.1 Случай дизъюнктных множеств.

1.2.2 Общий случай.

1.3 Склеивание двух клонов.

1.4 Критерий полиномиальности амальгамы.

1.4.1 О мощности множества С

1.4.2 Случай монолитности одного из клонов.

1.4.3 Канонический вид задачи.

2 Эффективность Локального Поиска

2.1 Основные определения.

2.1.1 Задача Выполнимость и Локальный Поиск

2.1.2 Теорема Вормальда.

2.2 Локальный Поиск за Один Просмотр.

2.2.1 Модель.

2.3 Локальный Поиск.

2.3.1 Модель.

2.3.2 Эксперименты.

3 Алгоритм VEGAS

3.1 Основные определения.

3.1.1 Взвешенная Максимальная Выполнимость.

3.1.2 Генетические алгоритмы.

3.2 Описание алгоритма VEGAS.

3.2.1 Эволюция среды обитания.

3.2.2 Моделирование социальной структуры популяции

3.2.3 Алгоритм TabuSearch.

3.3 Результаты экспериментов.

3.3.1 Сравнение эффективности VEGAS и GASAT

3.3.2 Исследование влияния социальной структуры популяции на эффективность вычисления.

1 Общее описание проблематики

С расширением области применения компьютерных технологий появляется потребность в решении все большего количества комбинаторных задач. В связи с этим возникает естественное стремление разработать универсальные алгоритмы, способные решать как можно более широкие классы задач. При этом желательно, .чтобы универсальный алгоритм при решении конкретных задач был бы сравним по затратам ресурсов с наилучшим возможным алгоритмом. ,

Мы будем использовать стандартные определения комбинаторной задачи, класса задач NP, сведения, полиномиальности и NP-полноты задачи, см. например [1, 56]. Данная работа относится к исследованию комбинаторной задачи CSP (От английского 'Constraint Satisfaction Problem', в немногочисленной русскоязычной литературе встречается также название 'Обобщенная выполнимость'). Цель данного направления — разработать эффективные универсальные алгоритмы для задач из класса NP. Задача CSP является лишь одной из многих известных NP-полных задач, однако в последнее десятилетие стало ясно, что она занимает особое место. Сведение задачи к NP-полной очень часто оказывается громоздким и искусственным. Преимущество задачи CSP состоит в том, что большинство комбинаторных задач может быть представлено в виде CSP просто и естественно. Многие комбинаторные задачи могут быть естественным образом охарактеризованы как подклассы задачи CSP. Теория задачи CSP находит свое применение в таких областях как теория реляционных баз данных [43, 65], временная и пространственная логика [62], распознавание зрительных образов [52], автоматическое доказательство теорем [16], техническое проектирование [55], анализ языков программирования [54] и естественных языков [4], биоинформатика [45] и многих других.

Формулируется задача CSP следующим образом. Пусть даны множество переменных V и множество их возможных значений D. Ограничением называется пара, состоящая из вектора переменных (vi,., v^) и отношения р С Dk. Говорят, что функция ф : V —► D, ставящая в соответствие переменным их значения, удовлетворяет ограничению ((г^,., г^), р), если вектор (c/>(vi),., ф(ьк)) содержится в отношении р. В конкретной задаче CSP даны множества V и D, а также некоторое множество ограничений С. Требуется указать значения переменных (т. е. выбрать функцию ф : V —> D) так, чтобы удовлетворялись все ограничения из С.

Впервые общая задача CSP была введена Монтанари в 1974 г. [52] при решении одной из задач машинного зрения — распознавания формы многогранников по их двумерному изображению. В последующие годы этот формализм был активно использован для моделирования прикладных задач, а затем и разработки универсальных алгоритмов для их решения. В настоящее время существуют специальные декларативные языки программирования: ECLiPSc[5], Oz[59], 2LP[50], СН1Р[30] и Newton[31], в которых для решения задачи достаточно записать ее в виде CSP, существуют библиотеки с подобной функциональностью для С++ (например ILOG[58]), расширениями, позволяющими решать задачу CSP, снабжено большинство современных версий Prolog[53].

Частным случаем задачи CSP, в котором множество значений переменных двухэлементно, а разрешенные ограничения — дизъюнкции ли-тералов(клозы), является задача ВЫПОЛНИМОСТЬ, одна из первых задач, NP-полнота которых была доказана. Задача ВЫПОЛНИМОСТЬ представляет самостоятельный интерес, так как формулируется она проще, чем CSP, и в то же время сведение задачи CSP к задаче ВЫПОЛНИМОСТЬ не составляет труда.

Сама задача Выполнимость является в настоящее время объектом активного исследования. Ей посвящена ежегодная конференция SAT (это название является сокращением от SATISFIABILITY — английского названия задачи ВЫПОЛНИМОСТЬ), проводящаяся с 1996-го года. С 2005-го года выпускается журнал JSAT. Важное место в исследовании задачи Выполнимость занимает разработка реально работающих программ-решателей. При конференции SAT регулярно проходит соревнование таких программ, в котором принимают участие десятки программных продуктов, созданных учеными со всего мира. Прогресс, достигнуты!! в разработке алгоритмов для практических задач, огромен: многие задачи, еще 10 лет назад считавшиеся практически неразрешимыми, современными программами могут быть решены за доли секунды.

Возможный путь решения задачи CSP — это сведение ее к задаче ВЫПОЛНИМОСТЬ и использование эффективных эвристических алгоритмов. Однако, богатый язык общей задачи CSP позволяет сохранить при моделировании структуру исходной задачи, что дает ряд преимуществ. Во-первых, как было отмечено выше, многие задачи могут быть естественным образом охарактеризованы как ограниченные задачи CSP. Например, fc-раскраска графа — это в точности задача CSP на fc-элементном множестве, в которой в качестве отношения ограничения используется только неравенство. Во-вторых, большая структурированность задачи позволяет перенести в теорию CSP и обобщить алгоритмы, разработанные для других комбинаторных задач. Кроме того, язык задачи CSP оказывается проще для понимания, поэтому запись задачи в виде CSP на практике оказывается предпочтительнее кодирования в виде задачи ВЫПОЛНИМОСТЬ с точки зрения взаимодействия с заказчиком при моделировании предметной области.

Литература, появившаяся за десятилетия изучения задачи CSP, весьма обширна и рассматривает широчайший круг вопросов. Не пытаясь охватить всю литературу, посвященную задаче CSP, в следующем разделе мы осуществляем обзор только тех работ, которые непосредственно касаются проблем, решаемых в данной диссертации.

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи// М.: Мир, 1982.

2. Левин Л. А. Универсальные задачи перебора// Проблемы передачи информации. 1973. Т.9, №3. С. 115-116.

3. Achlioptas D. Lower bounds for random 3-SAT via differential equations/ / Theor. Comput. Sci. 2001. Vol.265. №1-2. P.159-185.

4. Allen J. Natural Language Understanding// Benjamin Cummings, 1994.

5. Apt K., Wallace M. Constraint Logic Programming using Eclipse// Cambridge University Press, 2007.

6. Asahiro Y., Iwama K., Miyano E. Random generation of test instances with controlled attributes// DIMACS Series on Discrete Mathematics and Theoretical Computer Science. 1996. Vol.26. P.377-393.

7. Asano Т., Williamson. D. Improved approximation algorithms for MAX SAT// J. Algorithms. 2002. Vol.42.№l. P.173-202.

8. Bertoni A., Carpentieri M., Campadelli P., Grossi G. A genetic model: Analysis and application to MAX-SAT// Evolutionary Computation. 2000. Vol.8. P.291-310.

9. Bramelette M., Bouchard E. Handbook of Genetic Algorithms // Van Nostrand Reinhold, New York, 1991.

10. Bulatov A., Jeavons P., Krokhin A. Classifying the complexity of constraints using finite algebras// SIAM J. Comput. 2005. Vol.34. №3 P.720-742.

11. Bulatov A., Krokhin A., Jeavons P. Constraint satisfaction problems and finite algebras// Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP'00). LNCS Vol. 1853. Springer-Verlag, 2000. P.272-282.

12. Cohen D., Jeavons P., Gault R. New tractable classes from old// Principles and Practice of Constraint Programming CP2000. LNCS Vol. 1894. P. 160-171.

13. Cohen D., Jeavons P., Koubarakis M. Building tractable disjunctive constraints// Journal of the ACM. 2000. Vol.47. P. 826-853.

14. Cohen D.A. Jeavons P., Gyssens M. A structural decomposition for hy-■ pergraphs// Contemporary Mathematics. 1994. Vol.178. P.161-177.

15. Cook S. The complexity of theorem-proving procedures// The 3rd IEEE Symp. on the Foundations of Computer Science. 1971. P.151-158.

16. Dechter R., Dechter A. Structure-driven algorithms for truth maintenance// Artificial Intelligence. 1996. Vol. 82. №1-2. P. 1-20.

17. Dechter R., Pearl J. Tree clustering for constraint networks// Artificial Intelligence. 1989. Vol.38. P.353-366.

18. Eiben A.E., Ven Der Hauw J.K., Van Hemert J.I. Graph coloring with adaptive evolutionary algorithms// Journal of Heuristics. 1998. Vol.4.№l. P.25-46.

19. Feder T., Vardi M. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory// SIAM Journal of Computing. 1998. Vol.28. P.57-104.

20. Fleurent. J., Ferland J. Genetic algorithms and hybrids for graph coloring// Annals of Operations Research. 1996. Vol. 63. P.437-461.

21. Freuder E. Complexity of k-tree structured constraint satisfaction problems/ / The 8th National Conference on Artificial Intelligence AAAI-90. 1990. P. 4-9.

22. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning// Addison-Wesley, 1989.

23. Gottlob G., Leone L., Scarcello F. A comparison of structural CSP decomposition methods// Artificial Intelligence. 2000. Vol. 124. №. 2. P.243-282.

24. Grohe M., Schwentick T., Segoufin L. When is the evaluation of conjunctive queries tractable?// The 33rd Annual ACM Simposium on Theory of Computing. ACM Press, 2001. P.657-666.

25. Gu. J. Efficient local search for very large-scale satisfiability problem// ACM SIGART Bulletin. 1992. Vol. 3. № 1. P. 8-12.

26. Han H., Xiaowei Y., Zhifeng H. Chunguo W., Yanchun L., Xi Z. Hybrid chromosome genetic algorithm for generalized traveling salesman problems// Advances in Natural Computation. 2005. LNCS Vol. 3612. P. 137-140.

27. Hansen P., Jaumard. B. Algorithms for the maximum satisfiability problem// Computing. 1990. Vol.44. P.279-303.

28. Hao J., Dorne R. A new population-based method for satisfiability problems// The 11th European Conf. on Artificial Intelligence. John Wiley & Sons, 1994. P. 135-139.

29. Hao J., Lardeux F., Saubion F. Evolutionary computing for the satisfiability problem// Applications of Evolutionary Computing. 2003. LNCS Vol.2611. P.258-267.

30. Hentenryck V. The CLP Language CHIP: Constraint Solving and Applications/ / Proceedings of the IEEE Computer Society InternationalConference. 1991. P. 382-387.'

31. Hentenryck V., Michel L. Newton: Constraint Programming over Nonlinear Real Constraints// Science of Computer Programming. 1997. Vol. 30. P. 83-118.

32. Hirsch E., Kojevnikov A. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination// Annals of Mathematics and Artificial Intelligence. 2001. Vol. 43, №1-4. P. 91-111.

33. Hirsch E. A. Worst-case study of local search for Max-k-Sat// Discrete Appl. Math. 2003. Vol. 130. №2. P.173-184.

34. Holland J. Adaptation in Natural and Artificial Systems// The University of Michigan Press, 1975.

35. Hoos H. Satisfiability Library, http://www.satlib.org.

36. Hoos H., Stutzle T. Stochastic Local Search, foundations and applications. Elsevier, 2005.

37. Jeavons P. On the algebraic structure of combinatorial problems// Theoretical Computer Science. 1998. Vol.200. P. 185-204.

38. Jeavons P., Cohen D., Cooper M. Constraints, consistency and closure// Artificial Intelligence. 1998. Vol.101. №1-2. P.251-265.

39. Jeavons P., Cohen D., Gyssens M. A unifying framework for tractable constraints// Proceedings 1st International Conference on Constraint Programming—CP'95. Springer-Verlag, 1995. LNCS Vol.976. P. 276291.

40. Jeavons P., Cohen D., Gyssens M. Closure properties of constraints// Journal of the ACM. 1997. Vol.44. P.527-548.

41. Jong K. D., Spears W. Using genetic algorithms to solve np-complete problems/ / Proceedings of the International Conference on Genetic Algorithms. 1989. P. 124-132.

42. Kolaitis P., Vardi M. Conjunctive-query containment and, constraint satisfaction// J. Comput. Syst. Sci. 2000. Vol. 61. №.2. P.302-332.

43. Koutsoupias E., Papadimitriou C. H. On the greedy algorithm for satisfiability// Information Processing Letters. 1992. Vol.43, №1. P.53-55.

44. Krippahl L., Barahona P. Applying constraint programming to protein structure determination// Proceedings 5th International Conference on Constraint Programming. Springer-Verlag, 1999. LNCS Vol. 1713. P. 289-302.

45. Lardeux F., Saubion F., Hao J.-K. A hybrid genetic algorithm for the satisfiability problem// The 1st Int. Workshop on Heuristics. 2002. P. 6977.

46. Lardeux F., Saubion F., Hao J.K. A chessboard coloring problem for SAT solver// Technical report. LERIA, Université d'Angers, 2003.

47. Li C., Jurkowiak B., Purdom P. Integrating symmetry breaking into a dll procedure// Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT2002). P.149-155.

48. Mackworth A. Consistency in networks of relations// Artificial Intelligence. 1977. Vol. 8. P.99-118.

49. McAloon K., TYetkoff C. 2LP: Linear Programming and Logic Programming/ / Principles and Practice of Constraint Programming. MIT Press. P. 101-116.

50. Mitchell D. G., Selman B., Levesque H. J. Hard and easy distributions for SAT problems// Proceedings of the Tenth National Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 1992. P. 459465.

51. Montanari U. Networks of constraints: Fundamental properties and applications to picture processing// Information Sciences. 1974. Vol. 7. P. 95-132.

52. Narboni G. A. From Prolog III to Prolog IV: The Logic of Constraint Programming Revisited// Constraints. Springer-Netherlands. Vol.4. №4. 2004.

53. Nadel B. Constraint satisfaction in Prolog: Complexity and theory-based heuristics// Information Sciences. 1995. Vol.83. №3-4. P.113-131.

54. Nadel B., Lin J. Automobile transmission design as a constraint satisfaction problem: Modeling the kinematik level// Artificial Intelligence for Engineering Design, Anaysis and Manufacturing (AI EDAM). 1991. Vol.5. №3. P. 137-171.

55. Papadimitriou C. Computational Complexity// Addison-Wesley, 1994.

56. Poschel R., Kaluznin L. Punktionen- und Relationenalgebren. DVW, Berlin, 1979.

57. Puget J. F. A C++ implementation of CLP// Proceedings of the Second Singapore International Conference on Intelligent Systems. 1994. P. 256261.

58. Roy P.V. Logic programming in Oz with Mozart// Proceesings of the 1999 international conference on Logic programming. 1999. P. 38-51.

59. Sclman B., Levesque H., Mitchell D. GSAT A new method for solving hard satisfiability problems// The 10th National Conference on Artificial Intelligence (AAAI-92). 1992. P.440-446.

60. Schaefer T. The complexity of satisfiability problems// Proceedings 10th ACM Symposium on Theory of Computing (STOC'78). 1978. P. 216226.

61. Schwalb E., Vila L. Temporal constraints: a survey// Constraints. 1998. Vol. 3, №. 2-3. P. 129-149.

62. Simpson A., Dandy G., Murphy L. Genetic algorithms compared to other techniques for pipe optimization// Journal of Water Resources Planning and Management. 1994. Vol. 120. №4. P. 423-443.

63. Thornton C. Parity: the problem that won't go away// Advances in Artificial Intelligence. Springer-Verlag, 1996. LNCS Vol. 1081. P. 362-374.

64. Vardi M. Constraint satisfaction and database theory: a tutorial// Proceedings of 19th ACM Symposium on Priciples of Database Systems (PODS'00). 2000. P. 76-85.

65. Voorn R., Dastani M., Marchiori E. Finding simplest pattern structures using genetic programming// Proceedings of the Genetic and Evolutionary Computation Conference. 2001. P.3-10.

66. Wormald N. Differential equations for random processes and random graphs// The Annals of Applied Probability. 1995. Vol.5. №4. P.1217-1235.Работы автора по теме диссертации

67. Булатов А., Скворцов Е. Амальгамы комбинаторных задач// Российская конференция "Дискретный анализ и исследование операций", материалы конференции, Новосибирск. 2002. С. 136.

68. Скворцов Е. О клонах на множестве и его частях// Алгебра и логика. 2005. №1. С.97-113.

69. Скворцов Е. С. VEGAS — новый генетический алгоритм для задачи Выполнимость// Известия Уральского государственного университета. Серия Компьютерные науки и информационные технологии. 2008. №62. Р. 192-207.

70. Скворцов Е. Решение задачи Выполнимость генетическим алгоритмом/ / Труды 36й молодежной школы-конференции "Проблемы теоретической и прикладной математики". 2005. Р.373-375.

71. Amiri Е., Skvortsov Е. S. Pushing random walk beyond golden ratio // Computer Science Theory and Applications. CSR 2007. LNCS Vol. 4649. P.44-55.

72. Bulatov A., Skvortsov E. Amalgams of constraint satisfaction problems/ / The 18th International Joint Conference on Artificial Intelligence (IJCAI'03), Acapulco, Mexico. 2003. P. 197-202.

73. Bulatov A., Skvortsov E. Efficiency of local search// Theory and Applications of Satisfiability Testing SAT 2006. LNCS Vol. 4121. P.297-310.