ЧАСТЬ II

5. Задача коммивояжера

Задача коммивояжера тесно связана с несколькими другими задачами теории графов, обсуждаемыми в других частях этой книги. Здесь мы изучим две такие связи - с задачей о назначениях (см. гл. 12) и с задачей о кратчайшем остове (см. гл. 7). Обе эти задачи могут быть решены намного прош;е, чем задача коммивояжера, и можно исследовать эти связи для того, чтобы разработать эффективный метод решения последней задачи.

5.1. Нижняя граница из задачи о назначениях

Линейную задачу о назначениях для графа с произвольной матрицей весов С = [сц] можно сформулировать так (см. гл. 12).

Пусть - (тг X 7г)-матрица, в которой = 1, если вершина Х( назначена к вершине xj, и = О, если xt не назначена к Xj. Такую же схему можно использовать и в задаче коммивояжера, полагая = 1, если коммивояжер едет непосредственно из Х( в Xj, и I;; = О в противном случае. В этой последней задаче можно положить Сц - со (г = 1, . . ., тг), чтобы устранить бессмысленные решения с = 1.

Теперь задача о назначениях формулируется так.

Найти величины tj, минимизируюш;ие

=Yicijbj, (10.4)

при условии, что

Slu=Slu = l (10.5)

(для всех i, i = I, 2, . . . , п)

lij = 0 или 1. (10.6)

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

Уравнения (10.4) - (10.6) вместе с дополнительным ограничением, состояш;им в том, что решение должно давать единственный цикл (гамильтонов), а не просто некоторое число несвязных циклов также могут быть использованы для формулировки задачи коммивояжера. Заметим, что дополнительное условие Сц = оо

можно интерпретировать как ограничение, устраняющее возможность появления в решении задачи о назначениях циклов длины 1. Так как добавление любого ограничения в задаче о назначениях не может увеличить минимального значения z, определяемого из уравнений (10.4) - (10.6), то это значение z является нижней границей веса решения задачи коммивояжера для графа с матрицей весов [cij].

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

Для графа с симметричной матрицей весов (расстояний) С, т. е. для неориентированного графа, нижнюю границу для решения задачи коммивояжера можно получить по кратчайшему остову графа следующим образом. Пусть установлено, что ребро (xi, Х2) входит в оптимальный цикл задачи коммивояжера. Если это ребро удалить из цикла, то получится цепь, состоящая из п - 1 ребер, проходящая через все вершины, начиная с вершины Xi, и оканчивающаяся в х^. Так как вес кратчайшего остова, скажем L, является нижней границей для веса этой цепи, то длина кратчайшего остова плюс с {xi, х^) будет нижней границей для веса оптимального решения задачи коммивояжера.

В общем случае заранее не известно, какие ребра содержатся в оптимальном цикле, но самое длинное ребро в цикле должно быть [15] не короче, чем шах [с (х;, s)\. Здесь s - вторая ближайшая вершина к вершине Xj. Таким образом, величина

L-m&x\c{Xi, s)\ (10.7)

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

5.3. Двойственность

Определим G(TSP) как остовный подграф неориентированного графа G, образованный вершинами и теми ребрами графа

которые использованы в оптимальном цикле коммивояжера. Аналогично определим графы G(AP) и G (SST), образованные теми же вершинами, но ребра которых берутся из оптимальных решений задачи о назначениях и задачи о кратчайшем остове соответственно.

Граф G(TSP) обладает следующими свойствами:

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

(2) степень каждой вершины равна 2, т. е. каждая вершина лнцидентна двум ребрам.

На рис. 10.9 (а) приведен пример 5-вершинного графа G (TSP).

Граф G(AP) не обязательно обладает свойством (1), как это видно из рис. 10.9 (б), но по определению обладает свойством (2). Если, однако, окажется, что для решения задачи о назначениях выполняется и свойство (1), то это решение будет также решением задачи коммивояжера.

Для графа G(SST) свойство (1) выполняется по определению, но он может не иметь свойства (2). Если же окажется, что для кратчайшего остова свойство (2) выполняется - за исключением двух конечных вершин (скажем, Xi и Х2), которые необходимо

Рис. 10.9. Графы задач коммивояжера, о назначениях и о кратчайшем остове, (а) G(TSP). (б) G(AP). (в) G (SST).

имеют степень 1,- то кратчайший остов будет также кратчайшей депью, проходящей через все п вершин. Если, кроме того, ребро {xi, Х2) входит в оптимальный цикл задачи коммивояжера, то ребра иратчайшего остова вместе с ребром (х^, х^) дают решение задачи иоммивояжера. (Если же {х^, х^) не обязательно принадлежит птима-льному циклу задачи коммивояжера, то необходима небольшая модификация; см. разд. 6.)

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

(I) Использовать решение задачи о назначениях (для которого выполняется свойство (2)) и добиться, чтобы это решение подчинялось свойству (1). (II) Использовать решение задачи о кратчайшем остове (для которого выполняется свойство (1)) и добиться выполнения свойства (2).