Введение
Глава 1. Об исследуемой задаче 18
1.1. Обзор постановок задачи Вебера 18
1.2. Класс задач о назначениях 26
1.2.1. Линейные задачи о назначениях 26
1.2.2. Нелинейные задачи о назначениях 28
1.3. Формулировка исследуемой задачи 34
1.4. Выводы по первой главе 39
Глава 2. Точные алгоритмы решения задачи для графов специального вида 40
2.1. Точный алгоритм решения задачи для /с-дерева 40
2.1.1. Определение /с-дерева. Дерево декомпозиции /с-дерева 41
2.1.2. Точный алгоритм размещения /с-дерева 44
2.1.3. Обобщение алгоритма для /с-дерева на класс графов с ограниченной древовидной шириной 49
2.2. Точный алгоритм решения задачи для к-цеии 52
2.2.1. Определение к-цеии 52
2.2.2. Точный алгоритм размещения к-цеии 53
2.2.3. Обобщение алгоритма для к-цеии на класс графов с ограниченной ленточной шириной 57
2.3. Точный алгоритм решения задачи для простого цикла 59
2.4. Выводы по второй главе 64
Глава 3. Алгоритмы с оценками точности 66
3.1. Приближенный алгоритм 66
3.2. Модификации приближенного алгоритма 73
3.3. Метаэвристика с оценкой точности 77
3.4. Выводы по третьей главе 81
Глава 4. Вычислительные эксперименты 82
4.1. Исследование эффективности точных алгоритмов 82
4.2. Исследование эффективности приближенных алгоритмов 85
4.2.1. Анализ эффективности алгоритма АРХ 85
4.2.2. Анализ эффективности алгоритма APXGA 88
4.2.3. Сравнение эффективности приближенных алгоритмов 90
4.3. Выводы по четвертой главе 93
Заключение 95
Список литературы 101
Приложение. Основные обозначения
