Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).
Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).
Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.
Что касается первого класса, то в нем надо рассмотреть матрицу в табл. 6 с вычеркнутой первой строкой и вторым столбцом.
Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т. к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. |1|3 |4|5 |6| |2|1 |4|1 |0| |3|01|-|1 |3| |4|0 |1|- |0| |5|3 |3|01|-| |табл. 8 | |-|1 |2 |3 |4 |5 |6| |1|- |01|0 |3 |3 |6| |2|01|- |1 |4 |1 |0| |3|1 |2 |- |01|0 |3| |-|1 |3 |4 |5 |6| |2|01|1 |4 |1 |0| |3|1 |- |01|0 |3| |4|4 |01|- |1 |3| |5|4 |0 |1 |- |0| |6|7 |3 |3 |01|-| |-|1 |3 |4 |5 |6| |2|01|1 |4 |1 |0| |3|03|- |01|0 |3| |4|3 |01|- |1 |3| |5|3 |0 |1 |- |0| |6|6 |3 |3 |01|-| |табл. 7 |
табл.6
Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис.6.
Кружки представляют классы: верхний кружок – класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2); нижний правый – класс всех туров, не включающих ребро (1,2). Числа над кружками – оценки снизу.
Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C[1,2] на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть |-|3 |4 |6 | |2|1 |3 |03| |4|03|- |3 | |5|0 |03|0 | |табл. 10 | |- |3 |4 |5 |6 | |2 |1 |3 |1 |0 | |4 |01|- |1 |3 | |5 |0 |02|- |0 | |6 |3 |2 |03|- | |табл. 9 |
35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C(1,2),(3,1) на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2] и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.
Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис.8). |- |3 |4 | |4 |0 |- | |5 |0 |0 | | табл. 11|
Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.
В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.
Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.
Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.
Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.
§6. Применение алгоритма Дейкстры к решению ЗК
Одним из вариантов решения ЗК является вариант нахождения кратчайшей цепи, содержащей все города. Затем полученная цепь дополняется начальным городом – получается искомый тур.
Известно множество простых алгоритмов. Один из них – алгоритм Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую задачу:
В ориентированной, неориентированной или смешанной сети найти кратчайший путь между двумя заданными вершинами.
При небольшой модификации алгоритм Дейкстры позволяет найти кратчайшие пути из данной вершины во все остальные. Матрица расстояний Dik задаёт длины дуг dik между i-ой и k-ой вершинами; если такой дуги нет, то dik присваивается большое число Б, равное “машинной бесконечности”. Алгоритм Дейкстры имеет квадратичную сложность O(n2).
Таким образом, для решения ЗК нужно n раз применить алгоритм Дейкстры следующим образом.
Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро D[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j,…,k. Пусть это расстояние включает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере – для j,m и m,k) удалим соответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшее расстояние не должен входить уже использованный город.
Далее аналогично находим кратчайшее расстояние между парами вершин алгоритмом Дейкстры, до тех пор, пока все вершины не будут задействованы. Соединим последнюю вершину с первой и получим тур. Чаще всего это последнее ребро оказывается очень большим, и тур получается с погрешностью, однако алгоритм Дейкстры можно отнести к приближённым алгоритмам.
§7. Метод выпуклого многоугольника для решения ЗК
Рассмотрим рис. 9-10 и попытаемся найти в них кратчайшие туры. Очевидно, что кратчайший тур не должен содержать пересекающихся ребёр (в противном случае, поменяв вершины при пересекающихся рёбрах местами, получим более короткий тур). В первом случае кратчайшим является тур 1-2-4- 5-3-1, а во втором – тур 1-2-3-4-5-1. Анализируя множество других аналогичных расположении пяти и более городов, можно сделать следующее общее предположение:
Если можно построить выпуклый многоугольник, по периметру которого лежат все города, то такой выпуклый многоугольник является кратчайшим туром.
Однако не всегда можно построить выпуклый многоугольник, по периметру которого лежали бы все города. Велика вероятность того, что некоторые города не войдут в выпуклый многоугольник. Такие города будем называть “центральными”. Так как построить выпуклый многоугольник довольно легко, то задача сводится к тому, чтобы включить в тур в виде выпуклого многоугольника все центральные города с минимальными потерями. Пусть имеется массив T[n+1], содержащий в себе номера городов по порядку, которые должен посетить коммивояжер, т. е. вначале коммивояжер должен посетить город T[1], затем T[2], потом T[3] и т.д., причём T[n+1]=T[1] (коммивояжер должен вернуться в начальный город). Тогда, если выполняется равенство (i[pic] [1,2..n] C[T[i],p]+ C[p,T[i+1]]–C[T[I],T[i+1]] = min, то центральный город с номером p нужно включить в тур между городами T[i] и T[i+1]. Проделав эту операцию для всех центральных городов, в результате получим кратчайший тур. Для задачи, решённой нами методом ветвей и границ, этот алгоритм даёт правильное решение.
Попробуем решить данным алгоритмом ЗК для восьми городов. Пусть имеем восемь городов, расположение которых показано на рис. 11. Матрица расстояний приведена рядом на табл. 13. Промежуточные построения кратчайшего тура показаны пунктирными линиями, цифры – порядок удаления рёбер. Таким образом, имеем для данного случая кратчайший тур 1-3-7-5-4-8-6- 2-1. Длина этого тура: D=6+7+5+2+6+5+ 13+13=57. Этот результат является правильным, т.к. алгоритм лексического перебора, который никогда не ошибается, даёт точно такой же тур. (Следует также отметить, что жадный алгоритм для этого случая ошибается всего на 1 и даёт тур 1-3-4-5-7-8-6-2-1 длиной в 58).
Одним из возможных недостатков такого алгоритма является необходимость знать не матрицу расстояний, а координаты каждого города на плоскости. Если нам известна матрица расстояний между городами, но неизвестны их координаты, то для их нахождения нужно будет решить n систем квадратных уравнений с n неизвестными для каждой координаты. Уже для 6 городов это сделать очень сложно. Если же, наоборот, имеются координаты всех городов, но нет матрицы расстояний между ними, то создать эту матрицу несложно. Это можно легко сделать в уме для 5-6 городов. Для большего количества городов можно воспользоваться возможностями компьютера, в то время как промоделировать решение системы квадратных уравнений на компьютере довольно сложно.
Страницы: 1, 2, 3, 4, 5, 6, 7
