На этом шаге мы приведем общие сведения об алгоритмах с возвратом.
До сих пор мы рассматривали только такие алгоритмы на графах, в процессе работы которых нам никогда не приходилось возвращаться назад. Если, например, при обходе графа вершина была просмотрена, то она и оставалась в списке просмотренных вершин до окончания работы алгоритма. Однако существует большой класс задач, для которых неизвестны такие алгоритмы.
Пожалуй, наиболее известной такой задачей является задача коммивояжера (см., например, [1]) - задача о поиске кратчайшего маршрута между N городами, при этом лишь некоторые из городов непосредственно соединены дорогами.
Ниже мы рассмотрим задачу о поиске такого марщрута, который начинается и заканчивается в одном и том же городе и, кроме того, не заходит в один и тот же город дважды. Эта задача известна как задача поиска гамильтонова цикла в графе.
В отличие от эйлеровых путей не известно ни одного простого необходимого и достаточного условия для существования гамильтоновых путей и это несмотря на то, что эта задача - одна из центральных в теории графов. Не известен также алгоритм, который проверял бы существование гамильтонова пути в произвольном графе, используя число шагов, ограниченное многочленом от переменной n (число вершин в графе). Имеются некоторые основания, но нет математического довазательства того, чтобы предполагать, что такое положение вещей вызвано не столько нашим незнанием, а скорее тем фактом, что такого алгоритма не существует.
Проблема существования гамильтонова пути принадлежит к классу так называемых 2NP-полных задач [2, с.109]. Это широкий класс задач, включающий фундаментальные задачи из теории графов, логики, теории чисел, дискретной оптимизации и других дисциплин, ни для одной из которых неизвестен полиномиальный алгоритм (т.е. с числом шагов, ограниченным полиномом от размерности задачи), причем существование полиномиального алгоритма для хотя бы одной из них автоматически влекло бы за собой существование полиномиальных алгоритмов для всех этих задач. Именно факт фундаментальности многих NP-полных задач в различных областях и то, что, несмотря на независимые друг от друга усилия специалистов в этих областях, не удалось найти полиномиального алгоритма ни для одной из этих задач, склоняет к предположению, что такого алгоритма не существует.
(1) Рейнгольд Э., Hивергельт Ю., Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
(2) Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.
На следующем шаге мы рассмотрим построение алгоритма с возвратом.
