Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ЧАСТЬ II

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

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

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

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

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

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

Найти величины минимизирующие

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

(для всех )

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление