IV. Алгоритмы решения

Существует несколько разных алгоритмов для решения задачи коммивояжера. Все эти алгоритмы не являются абсолютно верными и в 5-10 процентов случаев дают ошибку, т.е. находят не самый оптимальный путь. К тому же эти алгоритмы сложны для вычисления и требуют большого количества машинного времени. Число требуемых для получения решения операций интенсивно возрастает с увеличением числа вершин. Так, если генерировать все n! различных последовательностей вершин и для каждой из них проверить, определяет ли она гамильтонов путь, то это потребует n!*n шагов. Для случая с тремя вершинами потребуется 18 шагов, для пяти вершин уже 600 шагов. В различных ситуациях целесообразно использовать различные алгоритмы решения.

IV.1. Поиск с возвращением

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

Как видно из рассмотрения дерева поиска, в данном графе существует ровно 4 гамильтоновых цикла.

IV.2. “Жадный” алгоритм решения зк.

Жадный алгоритм - алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. "Жадным" этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь алгоритм превратится в стратегию "иди в ближайший, в который еще не входил, город". Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм "иди вы ближайший город" выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

В пользу процедуры "иди в ближайший" можно сказать лишь то, что при старте из одного города она не уступит стратегии "иди в дальнейший".

Как видно, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно что полученный им тур хуже минимального, положим, в 1000 раз? Этого доказать нельзя, причем не только для жадного алгоритма, а для алгоритмов гораздо более мощных. Оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации будем следующим образом. Пусть f_B - настоящий минимум, а f_A - тот квазиминимум, который получен по алгоритму. f_A/ f_B ≠ 1, но это - тривиальное утверждение о том, что может быть погрешность. Чтобы оценить её, нужно «зажать» отношение оценкой сверху:

f_A/f_B ≤ 1+nδ (8)

где, как обычно в высшей математике, δ ≥ 0, но, против обычая, может быть очень большим. Величиина δ и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (8), мы будем говорить, что он имеет погрешность δ. Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G(V,E) и по нему составим входную матрицу ЗК:

С[i,j]= 1, если ребро (i,j) принадлежит Е

1+nδ, в противном случае

Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и f_B = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако переборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nδ. Но тогда f_A ≥ (n - 1) + (1 + nδ) так что f_A/f_B = 1+nδ, т.е. превосходит погрешность δ на заданную неравенством (8). О величине δ в нашем рассуждении мы не договаривались, так что δ может быть произвольно большим. Таким образом доказана следующая теорема. Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика. Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (7).