8.7 Алгоритмы с возвратом

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

а) Гамильтонов путь в графе б) Гамильтонов путь не существует

Рис. 31 Различные типы графов

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

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

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

< xj,..., x > . Идея метода состоит в следующем.

Строим наше решение последовательно, начиная с пустой последовательности, т.е. последовательности длины 0. Имея некоторое частичное решение < xj,..., x_i >, стараемся найти такое допустимое значение x_i+1,

относительно которого мы не можем сразу заключить, что < xj,..., x_i, x_i+1 > можно расширить до некоторо­го решения (а может быть < xj,...,x_i,x_i+1 > уже является решением). Если такое предполагаемое, но еще не использованное значение x_i+i существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности < xj,..., x_i, x_i+1 > . Если его не существует, то мы возвращаемся к частично­му решению < xj,..., x_i _j > и продолжаем наш процесс, отыскивая новое, еще не использованное допустимое значение x_i/ . Такие алгоритмы называются алгоритмами с возвратом (backtracking).

Точнее говоря, мы предполагаем, что для каждого к > 0 существует некоторое множество А_к, из которого мы будем выбирать кандидатов для k-й координаты частичного решения. Очевидно, что множества А_к должны быть определены таким образом, что для каждого целочисленного решения < xj,..., x_n > нашей задачи и для

каждого k<n множество А_к содержало бы элемент x_k (на практике А_к может содержать и "лишние" элементы,

не появляющиеся в к-й координате ни одного целочисленного решения).

Предполагаем также, что существует некоторая простая функция Р, которая произвольному частичному решению < xj,..., x_i > ставит в соответствие

P\x\,..., x i) = если последовательность < xj,..., x i > нельзя

false, расширить до решения и

P(xj,...,xi) = если значение x_i допустимо для частичного

^true' решения < xj,..., x i_j > . Это не означает, что

< xj,..., x i_i > обязательно расширяется до

полного решения. Этот процесс можно записать в виде следующей схемы алгоритма BEGIN k := 1; WHILE k > 0 DO

IF существует еще неиспользованный элемент ye A_k,

такой, что Р(х[1], ..., x[k-l], у) THEN BEGIN

x[k] := у; {элемент у использован} IF <х[1], ..., х[к]> является целочисленным решением THEN write(x[l], ..., х[к]); к:=к+1; END

ELSE {возврат на более короткое частичное решение; все элементы множества А_к вновь становятся неиспользованными} к:=к-1 END. Этот алгоритм находит все решения в предположении, что множества А_к - конечны, и что существует п

такое, что P\x\ -, ■ ■ ■ -, xi) = i^e для всех xj Е Ay,..., x_n Е A_n . Последнее условие означает, что

все решения имеют длину меньше п.

Можно доказать и более общее свойство, а именно.

Пусть S > 0 и пусть < Xj,...,X j > - некоторое частичное решение, построенное алгоритмом. Тогда, начиная с итерации цикла 3, для которого k = s, X[i] = х_ъ 1 < i < s, алгоритм генерирует все целочисленные ре­шения, являющиеся расширением последовательности < Xj,..., X_s_^ >, и приходит к состоянию, когда k = s -

1.

Последнее свойство приводит непосредственно к рекурсивному варианту алгоритма с возвратом.

1 PROCEDURE AP(k);

{генерирование всех решений, являющихся расширением по­следовательности Х[1], ..., Х[к-1]; массив X - глобальный}

2 BEGIN

3. FOR yeА_к такого, что Р(х[1], ..., х[к-1], у) DO

4. BEGIN Х[к] := у;

5. IF х[1], ..., Х[к] есть целочисленное решение

6. THEN write(X[l], ..., Х[к]);

7. АР(к+1)

8 END

9 END;

Применим алгоритм с возвратом для нахождения гамильтонова цикла в графе G = <V, Е>. Каждый такой цикл можно представить последовательностью < Xj,X2,...,x_w+1 > такой, что Xj = х_и+1 = Vq , где Vg- неко­торая фиксированная вершина графа и х_г ^ X, для 1 < / < j <п. В соответствии с этим можно положить

A_k=V.

Граф G = <V, Е> представим списками инцидентности СПИСОК[v], ve V. Тогда процедура для нахожде­ния всех гамильтоновых циклов, являющихся расширением последовательности < Xj,..., x^._j > :

1. PROCEDURE гамильт(К); {массив X - глобальный}

2. BEGIN

3 FOR уеСПИСОК[х[к-1]] DO

4. IF (k = n+l) and (y = vO)

5. THEN write(x[l], ..., x[n], vO)

6. ELSE IF DOP[y] THEN

7 BEGIN

8. x[k] := y; DOP[y] := false;

9. гамильт(к+1);

10. DOP[y] := true

11 END

12 END;

Главная программа: BEGIN

FOR veV DO DOP[v] := true; {инициализация}

X[l] := vO; {vO - произвольная фиксированная вершина графа}

DOP[v0] := false;

гамильт(2) END.

Следует отметить, что для большинства приложений число шагов алгоритма с возвратом хотя и будет меньше, чем в случае полного перебора, однако же в наихудшем растет по экспоненте с возрастанием размер­ности задачи. Это справедливо и для случая, когда мы ищем только одно, а не все решения.