Методы решения ЗК

Жадный алгоритм

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

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

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

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB — настоящий минимум, а fA — тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB?1, но это — тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

fA/fB ?1+ nе (5),.

где, как обычно в высшей математике, е?0, но, против обычая, может быть очень большим. Величина е и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность е.

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

С[i, j]={ 1, если ребро (i, j) принадлежит Е или 1+nе в противном случае}.

Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и fB = n. Если алгоритм, А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, непереборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм, А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nе. Но тогда.

fAі(n-1)+(1+nе) так что.

fA/fB=1+nе.

т.е. превосходит погрешность е на заданную неравенством (5). О величине е в нашем рассуждении мы не договаривались, так что е может быть произвольно велик.

Таким образом доказана следующая теорема.

Либо алгоритм, А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность, А при решении ЗК может быть произвольно велика.

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (4).

Если оно соблюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде, чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно ли начертить одной линией открытый конверт? Рис. 2 показывает, что можно (цифры на отрезках показывают порядок их проведения). Закрытый конверт (рис. 3.) одной линией нарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья — вершинами.

Когда через точку проводится линия, то используется два ребра — одно для входа в вершину, одно — для выхода. Если степень вершины нечетна — то в ней линия должна начаться или кончиться. На рис. 3 вершин нечетной степени две: в одной линия начинается, в другой — кончается. Однако на рис. 4 имеется четыре вершины степени три, но у одной линии не может быть четыре конца. Если же нужно прочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четную степень.

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

Если при этом нарисована вся фигура, то нужное утверждение доказано; если нет, удалим уже нарисованную часть. После этого от графа останется одна или несколько связных компонент; пусть — одна из таких компонент. В силу связности исходного графа и имеют хоть одну общую вершину, скажем, v. Если в удалены какие-то ребра, то по четному числу от каждой вершины. Поэтому — связный и все его вершины имеют четную степень. Построим цикл в (может быть, не нарисовав всего) и через v добавим прорисованную часть' к. Увеличивая таким образом прорисованную часть, мы добьемся того, что G' охватит весь .

Эту задачу когда-то решил Эйлер, и замкнутую линию, которая покрывает все ребра графа, теперь называю эйлеровым циклом. По существу была доказана следующая теорема.

Эйлеров цикл в графе существует тогда и только тогда, когда (1) граф связный и (2) все его вершины имеют четные степени.