Поиск с возвратами

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

Стратегия поиска, в которой происходит возвращение назад и применяется другое правило, если применение правила оказывается неподходящим, называется поиск с возвратами^[1] (Backtracking).

Рассмотрим процедуру Backtracking (алгоритм 2.5).

Алгоритм 2.5. Процедура поиска с возвратами для системы продукций

proc Backtracking (d, R, t).

if t (d) then return (OK) end if if Deadend (d) then return (fail) end if R' := SelectAll (d, R) for Г € R' do.

if Backtracking (r.f (d), R, t) = OK then return (OK).

end if end for return (fail) end proc.

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

В данную процедуру целесообразно включить функцию Deadend — обрыв «мертвых» путей (тупиков), иначе может произойти зацикливание программы.

Процедура Deadend может проверять самые разные условия, например:

• • совпадение текущего состояния базы данных D с уже построенным ранее;
• • ограничение глубины поиска и т. д.

Пример поиска с возвратами для задачи о волке, козе и капусте представлен на рис. 2.7. На этом рисунке серым отмечены узлы, из которых происходит возврат, потому что они идентичны уже построенным узлам. Отдельно следует упомянуть узел 0001. Это тупиковый узел — продолжение поиска из него невозможно. Но продолжение и не нужно, так как к этому моменту алгоритм находит целевой узел 1111.

Рис. 2.7. Поиск возвратами для задачи о волке, козе и капусте.

Здесь в качестве функции Deadend используется проверка совпадения нового состояния базы с построенным ранее на этом пути.

Известны различные модификации поиска с возвратами. Например, когда в процессе поиска сохраняются не все, а только ключевые состояния БД, и возврат выполняется не на один шаг, а на несколько шагов назад к последнему сохраненному состоянию.

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

Рис. 2.8. Фрагмент дерева поиска с возвратами для задачи о ходе конем.

Ставим коня на произвольное иоле доски. В данном случае в качестве первого поля взято угловое иоле а_х. Поочередно переставляя коня на различные поля, ищем такое, на котором ранее конь не был. Если таких полей вообще нет, то возвращаемся на предыдущее поле, и т. д.

Заметим, что сама структура правил предполагает хранение информации о тех полях доски, на которых конь уже побывал (см. и. 2.1.7). Поэтому здесь в функции Deadend нет нужды проверять совпадение нового состояния базы с построенным ранее на этом пути. Ценой хранения некоторой дополнительной информации в БД можно уменьшить вычислительную нагрузку на процедуру поиска с возвратами.

• [1] Иногда применяют неудачный термин «обратное прослеживание». Этот термин является точным переводом с английского, но плохо отражает суть дела.