Алгоритмы с возвратом (back-tracking)

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

Рис. 2.10:
а) Гамильтонов путь в графе;
б) Граф, в котором не существует гамильтонова пути.

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

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

Вернемся к конкретной задаче существования гамильтонова пути. Очевидный алгоритм, который мы можем применить, это "полный перебор всех возможностей":

• генерируем все n! различных последовательностей вершин;
• для каждой из них проверяем, определяет ли она гамильтонов путь.

Такие действия требуют по меньшей мере n! n шагов, но функция от n подобного вида растет быстрее, чем произвольный многочлен, и даже быстрее, чем произвольная экспоненциальная функция вида a ⁿ,a > 1, ибо

n! n > [ n /2]^{[ n /2]} = a ^{[ n /2]log}_a^{[ n /2]}

Опишем теперь общий метод, позволяющий значительно сократить число шагов в алгоритмах типа полного перебора всех возможностей. Чтобы применить этот метод, искомое решение должно иметь вид последовательности {x₁,..., x_n}. Основная идея метода состоит в том, что мы строим наше решение последовательно, начиная с пустой последовательности e (длины 0). Вообще, имея данное частичное решение {x₁,..., x_i},мы стараемся найти такое допустимое значение x_i+1, относительно которого мы не можем сразу заключить, что {x₁,..., x_i, x_i + 1} можно расширить до некоторого решения (либо {x₁,..., x_i+1} уже является решением). Если такое предполагаемое, но еще не использованное значение x_i+1 существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности {x₁,..., x_i, x_i+1}. Если его не существует, то мы возвращаемся к нашему частичному решению {x₁,..., x_i-1} и продолжаем процесс, отыскивая новое, еще не использованное допустимое значение x_i^' - отсюда название "алгоритм с возвратом" (англ.: backtracking).

Точнее говоря, мы предполагаем, что для каждого k > 0 существует некоторое множество A_k, из которого мы будем выбирать кандидатов для k -й координаты частичного решения. Очевидно, что множество A_k должны быть определены таким образом, что для каждого целочисленного решения {x₁,..., x_n} нашей задачи и для каждого k <= n множество A_k содержало элемент x_k (на практике мы не можем вообще исключить ситуацию, когда множество A_k содержит некоторые "лишние" элементы, не появляющиеся а k -й координате ни одного целочисленного решения). Мы предполагаем также, что существует некоторая простая функция, которая произвольному частичному решению {x₁,..., x_i} ставит в соответствие значение P(x₁,..., x_i) (истина либо ложь) таким образом, что если P(x₁,..., x_i) = ложь, то последовательность {x₁,..., x_i} несомненно, нельзя расширить до решения. Если P(x₁,..., x_i) = истина, то мы говорим, что значение x_i допустимо (для частичного решения {x₁,..., x_i-1}), но это отнюдь не означает, что {x₁,..., x_i-1},обязательно расширяется до полного решения. Этот процесс можно записать в виде следующей схемы:

Дата добавления: 2014-01-07