ИССЛЕДОВАНИЕ СХОДИМОСТИ АЛГОРИТМА КРИСТОФИДЕСА В ЗАВИСИМОСТИ ОТ ШАГА ШТРАФОВАНИЯ

Введение.

Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов [1].

Совершенно очевидно, что задача может быть решена перебором всех вариантов объезда и выбором оптимального. Но общая постановка задачи, впрочем, как и большинство её частных случаев, относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе вершин (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет [1].

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение [1].

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

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

Суть алгоритма в том, что преобразование матрицы реберных весов , при котором различные категории деревьев штрафуются по-разному, но в то же время относительные веса всех деревьев в пределах одной категории не изменяются. Цель при этом состоит в том, чтобы разделить различные категории и сделать категорию гамильтоновых цепей более привлекательной (менее штрафуемой) [2].

Пусть на входе мы имеем m x n матрицу расстояний d_ij для графа G. Тогда алгоритм будет состоять из следующих шагов:

·     Найти минимальное остовное дерево T с матрицей весов d_ij;

·     Выделить множество N(T) всех вершин нечетной степени в T и найти кратчайшее совершенное паросочетание M в полном графе G с множеством вершин N(T);

·     Построить эйлеров граф  с множеством вершин {, … ,} и множеством ребер TUM;

·     Найти эйлеров обход  в ;

·     Построить гамильтонов цикл (соответствующий вложенный тур)  из , последовательным вычеркиванием посещенных вершин [1].

Объект и методы исследования.

Объектом исследования было выбрано влияние размера шага штрафования на количество итераций метода которое требуется для получения решения.

Цель исследования — определение оптимального начального шага штрафования для последующих исследований.

За единицу размерности шага штрафования был выбран процент от средней длины ребра.

В работах Николаса Кристофидеса неоднократно упоминается что лучше использовать комбинированный метод штрафования, т. к. он дает лучшие результаты чем положительный и отрицательный методы по-отдельности. Поэтому в нашем исследовании мы использовали комбинированный метод.

Графы были случайно сгенерированы со следующими параметрами:

·     Кол-во вершин: 10—50;

·     Минимальная степень вершин: 2;

·     Максимальная степень вершин: 6—8.

Для исследования алгоритма была реализована программа на языке C#, для рендеринга использовалась система WPF.

Исследование проходило в следующем порядке:

1.  Генерация графа по параметрам.

2.  Поиск решения для 1 %; Если решение найдено, то ищем решения переходим к шагу 3, иначе к шагу 1.

3.  Поиск решения для 2 %; Если решение найдено, то продолжаем поиск с шагом 1 % пока не достигнем верхнюю границу, иначе поиск решения в окрестностях 1 % с шагом 0,5 %.

Результаты исследования.

Таблица 1.

Таблица сходимости метода

Рисунок 1. График зависимости количества итераций от количества вершин при шаге штрафования 1 %

Данные проведенного исследования показывают, что метод с большей вероятностью сходится при шаге штрафования 1 %. Стоит заметить, что все графы решение которых было невозможно найти с шагом штрафования 1 %, так же не решались с более меньшими шагами штрафования (0,1 %; 0,01 %; 0,001 %).

Заключение.

Результаты проведенного исследования показывают, что для первоначального шага штрафования лучше использовать 1 % от средней длины ребра. Однако не для всех графов находится решение с таким размером и требуется уменьшение шага штрафования.

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

Список литературы:
1.    Википедиия — свободная энциклопедия — [Электронный ресурс] — Режим доступа. — URL: https://ru.wikipedia.org/wiki/Задача _коммивояжёра (дата обращения 11.05.2014).
2.    Кристофидес Н. Теория графов: алгоритмический подход / М.: «Мир», 1978.