Введение
1 Общее описание проблематики 4
2 Проблемы, решаемые в диссертации 6
2.1 Используемые подходы 6
2.2 Амальгамы подклассов CSP 7
2.3 Эффективность алгоритма Локальный Поиск . 9
2.4 Алгоритм VEGAS 12
1 Амальгамы подклассов CSP 15
1.1 Основные определения теории клонов и теории задачи CSP 15
1.1.1 Задача CSP 15
1.1.2 Клоны 17
1.1.3 Амальгамы клонов 20
1.2 Строение клона функций, сохраняющих амальгаму 21
1.2.1 Случай дизъюнктных множеств 21
1.2.2 Общий случай 24
1.3 Склеивание двух клонов 28
1.4 Критерий полиномиальности амальгамы 33
1.4.1 О мощности множества С 34
1.4.2 Случай монолитности одного из клонов 36
1.4.3 Канонический вид задачи 38
2 Эффективность Локального Поиска 52
2.1 Основные определения 52
2.1.1 Задача Выполнимость и Локальный Поиск 52
2.1.2 Теорема Вормальда 55
2.2 Локальный Поиск за Один Просмотр 56
2.2.1 Модель 56
2.3 Локальный Поиск 66
2.3.1 Модель 66
2.3.2 Эксперименты 72
Оглавление
Алгоритм VEGAS 78
3.1 Основные определения 78
3.1.1 Взвешенная Максимальная Выполнимость 78
3.1.2 Генетические алгоритмы 80
3.2 Описание алгоритма VEGAS 81
3.2.1 Эволюция среды обитания 82
3.2.2 Моделирование социальной структуры популяции . 83
3.2.3 Алгоритм TabuSearch 83
3.3 Результаты экспериментов 87
3.3.1 Сравнение эффективности VEGAS и GASAT . 87
3.3.2 Исследование влияния социальной структуры популяции на эффективность вычисления Литература
