Теперь мы находимся в блоке 6. Является ли текущая матрица С матрицей 2x2? Так как С -матрица 3x3, переходим в блок 9. Подалгоритм блока 9 выполняется следующим образом:

Шаг 1. S=U2, 1}, (4, 5}, (4, 5}}. Шаг 2. w{{2, 1})=62

w{{A, 5})=68

w{{A, 5})=53

Следовательно, Х={4, 5}.

о о h=11 d

h = 62 В

Рис. 3.4.8. Дополнительные приведенные матрицы стоимостей для задачи, сформулированной на рис. 3.4.1.

В блоке 10 2о=оо, поэтому идем дальше. В блоке 11 нам повезло, и мы выходим на шаге 1. Опять переходим в блок 3 с Х={4, 5}, w(X) =53, и матрица С представлена на рис. 3.4.8, а.

Еще один раз, и цель может быть достигнута! Подалгоритм блока 3 дает следующее:

Шаг 1. S={(1, 4), (3, 4), (5, 2), (5, 3)}.

Шаг 2. Di4=12+0=12 D34=ll+0=11 Z),a=ll+0=11 Z),3=12+0=12

Шаг 3. Z)=Di4=Dgg=12. Мы произвольно выбираем (k, 4).

Теперь F={1, 4} и

w{Y) = w{{A, 5}) +1)1*4 = 53 + 12 = 65.

Поскольку Y={1, 4}, из С вычеркиваем строку 1 и столбец 4. Ребро (1, 4) вместе с ребрами (2, 1) и (4, 5) образует путь. Поэтому р=2 и =5. Полагаем с=оо и приводим текущую матрицу С. Находим, что /1=11 и w{Y)=53+h=64:. На рис. 3.4.8, б показана приведенная матрица С.

Теперь мы находимся в блоке 6 с матрицей С размеров 2x2. Блок вырабатывает тур со следующим порядком городов:

3 2 14 5 3

и стоимостью г=64 (проверьте это). В блоке 8 полагаем Zo=64; теперь это текущий лучший тур.

Все ли мы сделали? Нам не надо рассматривать вершины, следующие за вершинами {4, 5} и {1, 4}, так как их нижние границы больше чем 64. Однако в блоке 10 мы видим, что у конечной вершины {2, 1} нижняя граница равна 62<64. Следовательно, возможно, что тур из этого подмножества может быть несколько лучше, чем тот, который мы получили. Таким образом, надо еще кое-что сделать.

Мы находим, что Х={2, 1}, w(X)=62, а матрица С, откорректированная с помощью подалгоритма блока И, имеет вид, как на рис. 3.4.8, в. Затем в блоке 3 выбирается ребро (4, 1) с Z)=12 в качестве следующего ребра ветвления. В блоках 4 и 5 вычисляются w({i, 1})- =62+12=74 и ffii({4, 1})=62. Необходима еще одна итерация. Оставим это в качестве упражнения. Существует ли тур со стоимостью 62 или 63?

Хотя кажется, что только что построенный алгоритм работает очень долго на нашем маленьком примере с пятью городами, на самом деле это достаточно мощный инструмент. Тщательно выполненная программа обычно решает задачу коммивояжера с 20-30 городами существенно быстрее чем за одну минуту на серийных машинах CDC 6000 или IBM 360/lxx. Задачи с 40-50 городами часто могут быть решены за вполне доступное время (меньше 10 мин времени работы центрального процессора). Сопоставьте это с безобразньши результатами работы алгоритма исчерпывающего поиска ETS (см. разд. 1.3) для задачи с 20 городами, решаемой на суперкомпьютере.

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

Алгоритм GTS2 можно использовать как начальный этап для алгоритма ветвей и границ из данного раздела. Как мы видели при построении этого последнего алгоритма, может понадобиться некоторое время, прежде чем будет найден первый полный тур и Zo станет реалистической оценкой стоимости оптимального тура. Если в начале работы алгоритма известен довольно хороший тур, скажем полученный алгоритмом GTS2, тогда Zo с самого начала устанавливается на достаточно низкий уровень. В этом случае любая вершина на дереве поиска, нижняя граница которой оказывается больше или равной 2о, сразу может считаться исследованной. Таким образом, можцо в значительной мере избел<ать бесполезного поиска при работе точного алгоритма.

Этот алгоритм считался одним из лучших для задачи коммиво-

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

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

Упражнения 3.4

3.4.1. Завершите решение примера с пятью городами из этого раздела.

3.4.2. Используя алгоритм ветвей и границ этого раздела, решите следующую задачу коммивояжера с шестью городами:

1 2 3 4 5 6

» 21 42 31 6 24

11 « 17 7 35 18 25 5 ю 27 14 9

12 9 24 00 30 12 14 7 21 15 00 48 39 15 16 5 20 со

3.4.3. Начальный подалгоритм. Разработайте детальный подалгоритм для шага инициализации (блок 1) блок-схемы, изображенной на рис. 3.4.5.

3.4.4. Подалгоритм начального приведения. Разработайте детальный подалгоритм для шага начального приведения (блок 2) блок-схемы на рис. 3.4.5.

3.4.5. Процесс ветвления для мноокества Y. Разработайте детальный подалгоритм генерации Y (блок 4) для блок-схемы на рис. 3.4.5.

3.4.6. Подалгоритм исчерпывающего поиска. Разработайте детальный подалгоритм для шагов исчерпывающего исследования (блоки 6, 7 и 8) на рис. 3.4.5.

1,3.4.7. Полное изложение алгоритма коммивояжера. Дайте полное, детальное изложение всего алгоритма ветвей и границ, построенного в этом разделе. Организуйте алгоритм так, чтобы он был готов для непосредственной реализации в качестве программы для ЭВМ. См. упр. 3.4.3 - 3.4.6.

*3.4.8. Правильность. Докажите правильность алгоритма, построенного в этом разделе.

*3.4.9. Симметричный случай. Какие улучшения могут быть внесены в алгоритм этого раздела, если матрица стоимостей симметрична?

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

*L3.4.10. Реализация. Реализуйте алгоритм этого раздела (см. упр. 3.4.7) как машинную программу. Внимательность в процессе разработки и написания программы поможет избежать многих неприятностей на стадии отладки. Особая тщательность требуется для правильной обработки различных матриц стоимостей.