Об эффективных алгоритмах для задачи CSP и их программной реализации

• Автор: Скворцов, Евгений Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Екатеринбург
• Количество страниц: 97 с. : ил.

Оглавление
Введение

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

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

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

2.2 Амальгамы подклассов СБР.

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

2.4 Алгоритм УЕХЗАБ.

1 Амальгамы подклассов СЭР

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

1.1.1 Задача СБР

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 Алгоритм V
3.1 Основные определения.
3.1.1 Взвешенная Максимальная Выполнимость.
3.1.2 Генетические алгоритмы.
3.2 Описание алгоритма V.
3.2.1 Эволюция среды обитания
3.2.2 Моделирование социальной структуры популяции .
3.2.3 Алгоритм
3.3 Результаты экспериментов.
3.3.1 Сравнение эффективности V и
3.3.2 Исследование влияния социальной структуры популяции на эффективность вычисления
Литература


При конференции SAT регулярно проходит соревнование таких программ, в котором принимают участие десятки программных продуктов, созданных учеными со всего мира. Возможный путь решения задачи СБР — это сведение ее к задаче ВЫПОЛНИМОСТЬ и использование эффективных эвристических алгоритмов. Однако, богатый язык общей задачи СБР позволяет сохранить при моделировании структуру исходной задачи, что даст ряд преимуществ. Во-первых, как было отмечено выше, многие задачи могут быть естественным образом охарактеризованы как ограниченные задачи СЭР. Например, /с-раекраска графа — это в точности задача СЭР на ^-элементном . Во-вторых, большая структурированность задачи позволяет перенести в теорию СБР и обобщить алгоритмы, разработанные для других комбинаторных задач. Кроме того, язык задачи СБР оказывается проще для понимания, поэтому запись задачи в виде СЭР на практике оказывается предпочтительнее кодирования в виде задачи ВЫПОЛНИМОСТЬ с точки зрения взаимодействия с заказчиком при моделировании предметной области. Литература, появившаяся за десятилетия изучения задачи СЭР, весьма обширна и рассматривает широчайший круг вопросов. Не пытаясь охватить всю литературу, посвященную задаче СЭР, в следующем разделе мы осуществляем обзор только тех работ, которые непосредственно касаются проблем, решаемых в данной диссертации. Для СЭР, как и любой МР-полной задачи, не известно алгоритмов эффективных в худшем случае, однако, существует несколько подходов, использование которых позволяет решить многие классы задачи СЭР, возникающие в практических приложениях, за приемлемое время. Результаты данной работы относятся к трем из таких подходов. Во-первых, на языке СБР могут быть сформулированы все задачи из класса КР, а значит к полиномиальные, поэтому важным направлением в исследовании задачи СБР является идентификация полиномиальных подклассов и разработка для них эффективных алгоритмов. В первой главе мы рассматриваем операцию амальгамирования классов задач СБР и устанавливаем критерий полиномиальности амальгамы. Во-вторых, вероятностное распределение интересующей задачи может быть таковым, что существует алгоритм, получающий решение (или хорошее приближение решения) за приемлемое время с большой вероятностью. Во второй главе мы выясняем каково качество решения, которое с большой вероятностью находит базовый алгоритм Локального Поиска в применении к задаче Выполнимость. В-третьих, критерием эффективности алгоритма может быть его способность решить за приемлемое время конкретный набор задач. Классы задач, возникающие на практике, зачастую не представляется возможным описать как полиномиальное множество или задать для них адекватное вероятностное распределение. Поэтому тестирование является основным методом оценки практических алгоритмов. В третьей главе мы предлагаем эвристический алгоритм для задачи Выполнимость, основанный на генетическом подходе, и устанавливаем его эффективность на наборе тестовых задач. Естественный способ выделения подзадач СЗР состоит в задании множества отношений, разрешенных для использования в ограничениях. Для каждого такого множества Г через СЗР(Г) обозначается множество задач СЭР, в которых множество отношений, заданное в условии, содержится в Г. В году Шефер (), изучая ограниченные классы задачи СЗР на двухэлементном множестве, показал, что каждый такой класс либо ИР-полон, либо имеет полиномиальный алгоритм, решающий его. Кроме того, он нашел критерий, разделяющий легкие и трудные задачи. В этой же работе Шефер поставил проблему поиска аналогичного критерия для общей задачи СБР: для каждого множества отношений Г определить сложность задачи СЗР (Г) и найти для нес полиномиальный алгоритм, если таковой существует. Множество отношений Г, для которого задача СЗР(Г) полиномиальна, пазывается полиномиальным. Полиномиальные множества отношений могут быть заданы многими разными способами. Например, в [], используя технику логического программирования и методы теории групп, удалось выявить два больших класса задач СЭР, решаемых за полиномиальное время. В частности, в эти классы попадают все ‘легкие’ задачи СЭР, найденные Шефером.