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

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

Очевидно, что задача коммивояжера — это задача отыскания кратчайшего га-мильтонова цикла в полном графе.

Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все р\ возможных перестановок вершин полного графа, подсчи­тать для каждой перестановки длину маршрута и выбрать из них кратчайший. Очевидно, такое вычисление потребует О(р\) шагов.

Как известно, р\ с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем У (см. раздел 5.2). Таким образом, решение задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р. Более того, известно, что задача коммиво­яжера принадлежит к числу так называемых NP-полных задач, подробное об­суждение которых выходит за рамки этого учебника. Вкратце суть проблемы NP-полноты сводится следующему. В различных областях дискретной матема­тики, комбинаторики, логики и т. п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффек­тивных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует.

ОТСТУПЛЕНИЕ -

Полезно сопоставить задачи отыскания эйлеровых и гамильтоновых циклов, рассмотрен­ные в этом и предыдущем разделах. Внешне формулировки этих задач очень похожи, однако они оказываются принципиально различными с точки зрения практического при­менения. Уже давно Эйлером получено просто проверяемое необходимое и достаточное условие существования в графе эйлерова цикла. Что касается гамильтоновых графов, то для них не известно необходимых и достаточных условий. На основе необходимого и до-сточного условия существования эйлерова цикла можно построить эффективные алгорит­мы отыскания такого цикла. В то же время задача проверки существования гамильтонова цикла оказывается NP-полной (также как и задача коммивояжера). Далее, известно, что почти нет эйлеровых графов, и эффективный алгоритм отыскания эйлеровых циклов ред­ко оказывается применимым на практике. С другой стороны , можно показать, что почти все графы гамильтоновы, то есть

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

Комментарии

Из вопросов, рассмотренных в этой главе, наибольшее внимание в литературе уделено задаче коммивояжера. Анализ различных подходов к ее решению см., например, в [11]. Алгоритм 10.1 описан в [14], в других источниках (например в [6]) можно найти другие варианты решения этой задачи.

Упражнения

Доказать, что кодерево связного графа является максимальным подграфом, не содержащим коциклов.

Доказать, что эйлеров граф не имеет мостов.

Доказать, что если в связном графе G(V,E) Vu,v e V d(u) + d(v) ^ р, то граф G гамильтонов.