Алгоритмы с оценками для некоторых модификаций задач коммивояжера и разбиения множества

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

Глава 1. Задачи поиска гамильтоновых циклов экстремального реберного веса

1.1. Задачи коммивояжера в евклидовом пространстве

1.1.1. Постановка задачи

1.1.2. Алгоритм А. И. Сердюкова

1.1.0. Модифицированный алгоритм А

1.2. Задачи поиска двух реберно непересекающихся гамильтоновых циклов экстремального веса

1.2.1. Общая постановка задачи

1.2.2. Задача на максимум с одной весовой функцией

1.2.3. Метрическая задача на минимум с одной весовой функцией

1.2.4. Метрическая задача на минимум с двумя весовыми функциями

Глава 2. Задачи поиска связных подграфов с ограничениями на степени вершин

2.1. Задача поиска подграфа с заданными степенями вершин максимального реберного веса
2.1.1. Постановка задачи
2.1.2. Описание приближенного алгоритма
2.1.3. Анализ алгоритма
2.2. Задача поиска регулярного связного подграфа экстремального реберного веса
2.2.1. Постановка задачи

2.2.2. ИР-трудность
2.2.3. Описание приближенного алгоритма решения задачи
2.2.4. Вероятностный анализ алгоритма
2.2.5. Случай независимого равномерного распределения элементов матрицы расстояний
2.2.6. Случай минорирующей функции распределения элементов
матрицы расстояний, заданных независимо
2.2.7. Некоторые обобщения
Глава 3. Задача разбиения множества векторов
3.1. Постановка задачи
3.2. Решения задачи в полиэдральном пространстве (Як, с) с конечной нормой
3.3. Решение задачи в ^-мерном евклидовом пространстве
3.3.1. Области принадлежности решения
3.3.2. Описание алгоритма
Заключение
Список публикаций автора по теме диссертации
Благодарности
Литература

Теоретические исследования, связанные с вопросами сложности задач дискретной оптимизации, а также с построением и анализом эффективных приближенных алгоритмов решения этих задач, находятся в русле современных, интенсивно развивающихся областей математики. Терминология, возникающая в ходе этих исследований, широко распространена в современной научной литературе и требует определенного с ней знакомства.
На вопрос, для чего надо иметь представление о сложности решаемых задач, наиболее наглядный ответ дай во введении к книге [11]. В этой книге приводится более 300 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых в настоящее время нет оснований надеяться на построение эффективных алгоритмов их решения.
В результате бурного развития вычислительной техники появилась возможность решать не отдельную конкретную задачу, а разрабатывать методы и программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому целесообразно говорить о сложности не для одной индивидуальной задачи /, а для массовой задачи, или проблемы [], соответствующей множеству индивидуальных задач.
Задачи дискретной (комбинаторной) оптимизации образуют важный класс упомянутых массовых задач. Для задачи ф[ дискретной оптимизации решением каждой индивидуальной задачи / € П является произвольная реализация оптимума Opijj(I) := тахге$п(Г) Здесь <%(/) — область допустимых
значений дискретной (целочисленной) переменной z, : Sjj(I) —■> R+
целевая функция индивидуальной задачи I оптимизации, знак max в постановке задачи может быть заменен на min.
Большинство дискретных и комбинаторных задач допускает решение с поГлава
Задачи поиска связных подграфов с ограничениями на степени вершин
2.1. Задача поиска подграфа с заданными степенями вершин максимального реберного веса
2.1.1. Постановка задачи
Задан полный неориентированный граф 6'(И, Е) без петель с п вершинами. На ребрах графа определена весовая функция ш : £ —> Д+, а для вершин графа заданы такие натуральные числа ф (і — 1 п),1 < Д < п, что набор (сії,, Фг) является графическим разбиением их суммы Хл=1 В графе (7(У, Е) требуется найти связный подграф с максимальным суммарным весом ребер и заданными степенями вершин Д (г — 1 гг), 1 < Д < п.
2.1.2. Описание приближенного алгоритма
Для решения задачи СДИР для заданного графа С предлагается следующий алгоритм Л.
Шаг 1. С использованием алгоритма Габова из [43] находится такой подграф С (У, Е') графа С? с заданными степенями вершин, что суммарный вес его ребер максимален.
Шаг 2. Выделяются компоненты связности С Сц подграфа С. Если ц= 1, то подграф С является результатом работы алгоритма А и алгоритм А заканчивает свою работу.
Шаг 3. Из каждой компоненты С, (г — 1 ц) выделяется подмножество 5; ее ребер. Подмножество СОСТОИТ ИЗ всех ребер в Сі, не являющихся пере-