7.2. Пример

Найти решение задачи коммивояжера с матрицей весов 1 2 3 4 5 6 7 8

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

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

D) г 1,7,8)(2,4,6,5,3)

(1,4,3,2,7,8,6,5)

(1,4,2,7,8)(3,6,5) j Cl,6,5,3,2,4,7,8) (1,7,8,3,2,4,6,5) (1,7,8,2,4,3,6,5) (1,7,6,5,3,2,4,8)

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

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

19 н. Кристофидес

(1,4,3,2,7,8,6,5) 264

(1,7, 8), (2,4), (3,6, 5) 248

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

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

(1, 7, 8), (2, 4,6, 5,3) 250

ние, продолжая процесс ветвления. Наименьшая из нижних границ есть L = min (248, 250) = 248, и она соответствует узлу С, поэтому процесс ветвления следует продолжать с этого узла, исключая цикл (2, 4). Теперь возникают две другие подзадачи, показанные узлами Е и F на рис. 10.19. Их матрицы весов, решения задач о назначениях и веса таковы:

(3, 6, 5), (1,4, 2, 7,8) 280