7.2. Пример

Найти решение задачи коммивояжера с матрицей весов

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

Решение задачи о назначениях с матрицей состоит из двух циклов (2, 4, 3) и (1, 7, 8, 6, 5) с весом 232. Это соответствует узлу А дерева решений, показанного на рис. 10.19.

Рис. 10.19. Поиск, использующий дерево решений из примера 7.2.

Исключение цикла (2, 4, 3) по правилу ветвления В приводит к трем подзадачам, изображаемых на рис. 10.19 узлами Матрицы весов

этих подзадач, решения задач о назначениях для них и веса этих решений равны соответственно

(см. скан)

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

решение, продолжая процесс ветвления. Наименьшая из нижних границ есть и она соответствует узлу С, поэтому процесс ветвления следует продолжать с этого узла, исключая цикл Теперь возникают две другие подзадачи, показанные узлами на рис. 10.19. Их матрицы весов, решения задач о назначениях и веса таковы:

(см. скан)

Следует отметить, что на этом этапе решение подзадачи является гамильтоновым циклом с весом 254. Этот вес меньше, чем вес предыдущего лучшего решения (с весом 264), и, следовательно, лучшим текущим решением будет решение подзадачи Два узла ( все еще дают решения с негамильтоновыми циклами и являются поэтому кандидатами на продолжение процесса ветвления. Однако для уэла нижняя граница равна (текущее значение наилучшего решения), и, значит, ветвление в этом узле не может привести к лучшему результату. Поэтому

(см. скан)

узел с нижней границей является единственным узлом, ветвление в котором может привести к улучшению. Исключение цикла (1, 7, 8) из решения для узла приводит к трем подзадачам, обозначенным на рис. 10.19 как Соответствующие этим подзадачам матрицы весов и решения задач о назначениях таковы:

(см. скан)

На этом этапе мы замечаем, что решение подзадачи является гамильтоновым циклом с весом 251, что меньше чем предыдущее

лучшее значение 254. Поэтому решение подзадачи т. е. (1, 7, 6, 5, 3, 2, 4, 8), заменяет предыдущее лучшее решение. Кроме того, значение 251 меньше, чем нижняя граница в любом конечном узле дерева, и, следовательно, найдено оптимальное решение леей задачи. (Решения во всех концевых узлах — за исключением узла ветвление в котором было прекращено ранее, — являются на самом деле гамильтоновыми циклами, и здесь безотносительно к границам весов этих решений не нужно бы было производить дальнейшее ветвление.)