Эвристики в задаче коммивояжера, основанные
на построении минимальных остовных деревьев.
© , студ. 4 курса
Научный руководитель - к. ф-м. н., доц.
Аннотация: Выполнен анализ качества двух эвристик в задаче коммивояжера, опирающихся на построение минимальных остовных деревьев. Для исследования были отобраны экземпляры задачи из библиотеки TSPLIB различной размерности. Показано, что, по мере увеличения порядка графа погрешность эвристик существенно не изменяется, при этом худший случай не достигается. Выяснилось, что, несмотря на различие в оценках худшего случая, обе изученные эвристики в среднем дают практически одинаковые погрешности.
Ключевые слова: задача коммивояжера, эвристики, сравнительный анализ эвристик, нижние границы.
Данная работа является продолжением предыдущего исследования [1]. Причиной, вызвавшей интерес к эвристикам, основанным на построении минимальных остовных деревьях, стало то, что в отличие от [1], их погрешность всегда ограничена. Кроме того, помимо самих эвристик представляет интерес и оценка нижних границ. Действительно, при тестировании на известных экземплярах из библиотеки TSPLIB точное решение известно, поэтому с вычислением погрешности проблем не возникает. Однако, если использовать произвольно выбранный экземпляр задачи, то качество решения оценить уже невозможно. В таких случаях стоит использовать нижние границы.
В данной работе исследовались такие популярные эвристики, как DoubleTree и эвристика Кристофидеса. Существуют известные теоремы, которые дают оценку решения в худшем случае [2]. В то же время данные о качестве этих эвристик в среднем случае носят весьма отрывочный характер.
По общепринятой традиции обе эвристики рассматривались на полных графах порядка n. Общая схема их реализации выглядит одинаково [2]:
- Нахождение минимального остовного дерева в исходном графе; Приведение полученного дерева к Эйлерову графу; Построение Эйлерова цикла в полученном графе; Преобразование Эйлерова цикла в Гамильтонов.
Ключевая разница в алгоритмах заключается в особенностях преобразовании остовного дерева в Эйлеров граф. Для эвристики DoubleTree это достигается при помощи удвоения всех ребер, а для эвристики Кристофидеса путем добавления ребер полученных с помощью построения совершенного паросочетания минимального веса на вершинах имеющих нечетную степень.
С преобразованием остовного дерева для эвристики DoubleTree не возникало. В то время как для эвристики Кристофидеса пришлось столкнуться с рядом трудностей. Дело в том, что алгоритмы нахождения паросочетания минимального веса в произвольном графе осложняются необходимостью сжатия цветков, которые представляют собой циклы нечетной длины. В литературе описано много способов нахождения паросочетаний в планарных графах, для которых количество нечетных циклов достаточно мало. Однако полные графы характеризуются большим количеством таких циклов. В частности, для полного графа проблема стягивания цветков сводится к стягиванию треугольников в ребро, а их количество оказывается пропорционально 
, что приходится учитывать при реализации известных алгоритмов.
В ходе проделанной работы были произведены эмпирические оценки качества обеих эвристик на экземплярах задачи из библиотеки TSPLIB. Эта библиотека известна тем, что содержащиеся в ней экземпляры не допускают точного решения с помощью эвристик низкой сложности. Для каждого экземпляра погрешность рассчитывалась как отношение приближенного решения, к точному. Все изученные экземпляры были разделены на 3 группы: маленькие (
), средние (
) и большие (
), где n – это порядок графа.
Таблица 1. Результаты для эвристики DoubleTree
Экземпляр | Полученное решение | Точное решение | Погрешность | |
Маленькие экземпляры | burma14 | 4062 | 3323 | 1.222 |
ulysses16 | 7796 | 6859 | 1.137 | |
gr17 | 2396 | 2085 | 1.149 | |
gr21 | 3922 | 2707 | 1.449 | |
ulysses22 | 8132 | 7013 | 1.160 | |
Средние экземпляры | gr96 | 74815 | 55209 | 1.355 |
bier127 | 156418 | 118282 | 1.322 | |
ch130 | 8204 | 6110 | 1.343 | |
gr137 | 93559 | 69853 | 1.339 | |
ch150 | 9029 | 6528 | 1.383 | |
Большие экземпляры | a280 | 3959 | 2579 | 1.535 |
pr299 | 65644 | 48191 | 1.362 | |
lin318 | 59095 | 42029 | 1.406 | |
gr431 | 216722 | 171414 | 1.264 | |
pr439 | 146759 | 107217 | 1.369 |
Результаты усреднения погрешности по каждой из групп дали следующие результаты: 1.223, 1.348, 1.387. С учетом относительно большой дисперсии вряд ли можно говорить о значимых различиях между погрешностями второй и третьей групп.
Таблица 2. Результаты для эвристики Кристофидеса
Экземпляр | Полученное решение | Точное решение | Погрешность | |
Маленькие Экземпляры | burma14 | 3921 | 3323 | 1.178 |
ulysses16 | 7877 | 6859 | 1.148 | |
gr17 | 2449 | 2085 | 1.175 | |
gr21 | 3503 | 2707 | 1.294 | |
ulysses22 | 7867 | 7013 | 1.122 | |
Средние экземпляры | gr96 | 70387 | 55209 | 1.275 |
bier127 | 171035 | 118282 | 1.446 | |
ch130 | 7680 | 6110 | 1.257 | |
gr137 | 91934 | 69853 | 1.316 | |
ch150 | 7344 | 6528 | 1.125 | |
Большие экземпляры | a280 | 3565 | 2579 | 1.381 |
pr299 | 59218 | 48191 | 1.229 | |
lin318 | 48165 | 42029 | 1.146 | |
gr431 | 209639 | 171414 | 1.223 | |
pr439 | 123943 | 107217 | 1.156 |
Аналогичные оценки погрешности для второй эвристики имеют вид: 1.183, 1.284, 1.227. Аномально большое значение погрешности в средней группе обусловлено паталогическим поведением эвристики Кристофидеса для экземпляра bier127. Стоит отметить, что большая погрешность для данного экземпляра задачи характерна и для многих других эвристик низкой степени сложности.
Не смотря на лучшую оценку поведения эвристики Кристофидеса в худшем случае, усреднение по большому количеству экземпляров свидетельствует о том, что в среднем качество рассматриваемых эвристик примерно одинаково.
В работе рассматривалось несколько способов построения нижних границ: 1-tree, 2-neighbors [2], задача о назначениях.
Для вычисления нижней границы c помощью 1-Tree необходимо выбрать произвольную вершину графа, и на оставшихся вершинах построить минимальное остовное дерево. В полученное остовное дерево необходимо добавить 2 ребра минимального веса, которые будут соединять его с выбранной в начале вершиной. Для получения наилучшей нижней границы необходимо построить n остовных деревьев, что приводит к сложности работы алгоритма 
. Желательно, что бы затраты на нахождение нижней границы оказались сравнимы, а еще лучше, что бы они были меньше, чем время работы самой эвристики. Исходя из этого в работе использовалось упрощенное 1-tree [2]. Это ускоряло время нахождения нижней границы в n раз, при этом погрешность составляла в среднем 12%.
Для всех рассмотренных в работе методов получения нижних границ были произведены оценки их качества, на экземплярах из TSPLIB. Усредненная погрешность для 1-tree была указана выше. Аналогичная оценка для метода 2-neighbor составила 25%, а для задачи о назначениях – 22%. Как видно из полученных результатов, явным лидером по качеству является метод 1-tree. Однако, для всех трех методов прослеживается зависимость погрешности от топологии графа, что не позволяет однозначно выбрать наилучший метод.
Говоря о двух других подходах к вычислению нижних границ можно сделать следующие выводы об их достоинствах и недостатках:
- Основным недостатком задачи о назначениях является то, что вместо Гамильтонова цикла мы, как правило, получаем множество циклов длины 2 и 3, что значительно ухудшает точность нижней границы. Разбиение всех этих циклов потребует больших временных затрат за счет существенного увеличения числа ограничений. Тем не менее, в случае ориентированной задачи коммивояжера, результаты оказываются значительно лучше. В свою очередь нижние границы, полученные методом 2-neighbor, будут обладать плохим качеством, если входными данными окажутся изолированные кластеры точек. Стоит отметить, что достоинством этого метода является высокая скорость работы, которую можно оценить как
. Список литературы:
Серкова эвристики в задаче коммивояжера // Научно-исследовательская работа обучающихся и молодых ученых. Материалы 68-й Всероссийской (с международным участием) научной конференции обучающихся и молодых ученых, 2016, стр. 363-366. Reinelt G. The Traveling putational Solutions for TSP Applications. Berlin: Springer-Verlag, 1994.