Целевой узел

Рис. 11.6. Отношение depthfirst (

Path, Node, Solution)

Соответствующая программа поиска в глубину приведена в листинге 11,1,

Листинг 11,1. Программа поиска в глубину, которая позволяет предотвратить возникновение циклов

% solve[ Node, Solution);

% Решение solution представляет собой ациклический путь (узлы в котором * указаны в обратном порядке) между узлом Node и целью

solve { Mode, Solution):-

depthfirst ([], Mode, Solution).

Хрешение 'Solution o формируется "в результате продления пути (Node | Path] % до целевого узла

depthfirst(Path, Node, [Node i Path]):-goal; Node).

depthfirstl Path, Node, Sol}:-

s; Node, Nodel),

not member(Nodel, Path), % Предотвращение цикла
... depthfirst.(_.[Node |....Path],...Nodel, Sol).............................................................................................

Благодаря применению механизма обнаружения циклов рассматриваемая проце­дура поиска в глубину позволяет находить пути решения в пространствах состояний, подобных приведенному на рис. 11.5. Тем не менее есть такие пространства состоя­ний, в которых эта программа вполне может потерпеть неудачу. В частности, многие пространства состояний являются бесконечными. В подобном пространстве состоя­ний программа поиска в глубину может пропустить целевой узел, проходя по беско­нечной ветви графа. Затем программа неопределенно долго будет исследовать эту бесконечную часть пространства, не приближаясь к цели. На первый взгляд может показаться, что причиной возникновения ловушки такого рода может стать про­странство состояний задачи с восемью ферзями, которое определено в этом разделе. Но по стечению обстоятельств данное пространство является конечным, поскольку максимальное количество вариантов выбора координат Y клеток, на которых могут быть безопасно расставлены восемь ферзей, является ограниченным.

Для предотвращения бессмысленного прохождения по бесконечным (нецикличес­ким) ветвям можно ввести еще одно усовершенствование в основную процедуру по­иска в глубину: ограничить глубину поиска. В таком случае процедура поиска в глу­бину будет иметь следующие параметры: depthfirst2{ Node, Solution, Maxdepth)

Глава 11, Основные стратегии решения проблем

 

Поиск не должен проводиться в глубину, превышающую Maxdepth. Это ограни­чение можно запрограммировать путем уменьшения предельного значения глубины при каждом рекурсивном вызове и контроля над тем, чтобы этот предел оставался положительным. Результирующая программа приведена в листинге 11.2.

Листинг 11.2. Программа поиска в глубину с ограничением глубины поиска

% depthfirst2 [ Node, Solution, Maxdepth):

% Решение Solution представляет собой путь от узла Node до целевого узла, % длима которого не превышает Maxdepth

de_Pthfirst2C Node, [Node], _):-goal (Node).

depthfirst2(Node, [Node. Sol], Maxdepth):-Maxdepth > 0, s(Node, Model],

Maxl is Maxdenth - 1, depthfirst2(Model, Sol, Maxl).

При использовании программы поиска в глубину (см. листинг 11.2) возникает оп­ределенное затруднение, связанное с тем, что подходящий предел необходимо уста­навливать заранее. Если этот предел будет установлен слишком низким {т.е. мень­шим по сравнению с длиной любого пути решения), поиск завершится неудачей. А если предел будет установлен слишком высоким, поиск потребует лишних затрат времени. Для преодоления этой сложности можно выполнять поиск в глубину итера­тивно, постепенно изменяя предел глубины, начиная с очень низкого предела глуби­ны и постепенно увеличивая этот предел до тех пор, пока не будет найдено решение. Этот метод называется итеративным углублением. Его можно реализовать путем модификации программы, приведенной в листинге 11.2, следующим образом: преду­смотреть вызов процедуры depthf irst2 из другой процедуры, которая при каждом рекурсивном вызове будет увеличивать предел на 1.

Тем не менее существует более изящная реализация, которая основана на исполь­зовании следующей процедуры; pathf Model, Mode?, Path)

где Path - ациклический путь в обратном порядке между узлами Nodel и Node2 в про­
странстве состояний. Предположим, что этот путь представлен как список узлов в обрат­
ном порядке. В таком случае процедуру path можно записать следующим образом:
path! Bode, Node, [Node]). % Путь с одним узлом

path; FirstNcde, LastNode, [LastHode I Path]):-

path! FirstNode, OneButLMt, Path), % Путь, который включает все _yaJM,

* кроме предпоследнего
К CneSutLast, LastNode), % Последний этап пути

not member; LastNode, Path). % Отсутствие цикла

Попытаемся найти некоторые пути, начинающиеся с узла а в пространстве со­стояний, приведенном на рис. 11.4, как показано ниже.

?- path(a, Last, Path).

Last = а

Path - [а];

Last - b

Path = [b,a],*

Last = с

Path = [c,a];

Last = d

Path = [d,b,aj;

Часть II, Применение языка Prolog в области искусственного интеллекта

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

depth first iterative deepening С Node, solution):-path(Mode, GoalKodi, Solution), goal GoalNode].

Такая процедура действительно является очень удобной с точки зрения практики, при условии, что комбинаторная сложность рассматриваемой задачи не требует ис­пользования эвристик, характерных для этой задачи. Данная процедура проста, и, даже притом что она не выполняет каких-либо достаточно "разумных" действий, ее использование не требует больших ресурсов времени или пространства. По сравне­нию с некоторыми другими стратегиями поиска, такими как поиск в ширину, ос­новным преимуществом итеративного углубления является то, что для реализации этой стратегии необходим относительно небольшой объем памяти. На любом этапе выполнения программы требования к памяти, по сути, ограничиваются необходимо­стью хранить данные об одном пути, между начальным узлом поиска и текущим уз­лом. Пути формируются, проверяются и отбрасываются, в отличие от некоторых других процедур поиска (таких как поиск в ширину), при которых во время поиска одновременно хранится информация о многих возможных путях. Недостаток страте­гии итеративного углубления является продолжением ее основного достоинства; при увеличении предела глубины во время каждой итерации ранее вычисленные пути необходимо перевычислять и продлевать до нового предела. Но при решении типич­ных задач поиска такое повторное вычисление не слишком сильно влияет на общую продолжительность вычислений. Как правило, основной объем вычислений выполня­ется на самых низких уровнях поиска, поэтому повторные вычисления на верхних уровнях занимают относительно небольшую часть в общем объеме времени.