Задача коммивояжера. Сравнение задач отыскания эйлеровых и гамильтоновых циклов.

Если в р -вершинном графе зафиксировать одну вершину, то перебором (р -1)! перестановок можно найти гамильтонов цикл (в этом случае перебирать все перестановки придется лишь при максимальном невезении) или убедиться в его отсутствии. На практике не пользуются столь бесхитростным способом, а применяют различные алгоритмы частичного перебора. Однако и там наблюдается тот же эффект – негамильтоновость установить, как правило, труднее, чем гамильтоновость. В этой ситуации были бы полезны необходимые условия гамильтоновости. Но к сожалению, для графов общего вида необходимые условия гамильтоновости неизвестны, за исключением банального факта, что гамильтонов граф должен быть двухсвязным, т.е. не иметь разделяющей вершины.

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

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

Как известно, р! с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем 2 ^p, поскольку . Таким образом, решение задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р. Более того, известно, что задача коммивояжера принадлежит к числу так называемых NP-полных задач, подробное обсуждение которых происходит в курсе “Алгоритмы и анализ сложности”. Вкратце суть проблемы NP-полноты сводится следующему. В различных областях дискретной математики известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует.

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

Дата добавления: 2015-10-13