Поиск в ширину

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

Рис. 11.7. Простое пространство состояний: a — начальный узел, f и j — целевые узлы.

Порядок, е котором программа, реализующая стратегию поиска в ширину, посещает узлы с этом пространстве состояний, является сле­дующим: а, с. с, d. е. f. Более короткое реше­ние, la, с, f ], обнаруживается прежде, чем длинное, [a,b,e,j]

Составление программы поиска в ширину сложнее по сравнению с поиском в глу­бину. Причина такого усложнения состоит в том, что необходимо сопровождать це­лое множество возможных альтернативных узлов, а не рассматривать только один узел, как при поиске в глубину. Такое множество возможных узлов представляет со­бой целую грань дерева поиска, которая постепенно сдвигается вниз. Но даже такое множество узлов является недостаточным, если в процессе поиска необходимо также выделить путь к решению. Поэтому вместо сопровождения множества возможных узлов приходится сопровождать множество возможных путей. Таким образом, отно­шение breadth first (Faths, Solution)

принимает истинное значение, если некоторый путь из множества возможных путей Paths может быть продлен до целевого узла. Таким продленным путем является путь Solution.

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

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

[ (StartHode] ]

Общая схема поиска в ширину приведена ниже.

Для осуществления поиска в ширину по заданному множеству возможных пу­тей необходимо выполнить следующие действия:

• если голова первого пути представляет собой целевой узел, то считать этот путь
решением задачи;

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

Применительно к примеру задачи, приведенному на рис. 11.7, этот процесс раз­вивается, как описано ниже.

1. Начать с первоначального множества возможных путей: Па])

2. Сформировать продолжения пути [а]:

[ [Ь,а], [с,*] ]

(Обратите внимание, что узлы во всех путях представлены в обратном порядке.)

3. Удалить из множества первый возможный путь, [Ь,а], и сформировать про­
должения этого пути:

[ [d,b,a], te,b,a])

Добавить список продолжений к концу множества возможных путей: [ [с, a] _r (d,b,a), [e,b,a] ]

4. Удалить путь [с,а) и добавить его продолжения к концу множества возмож­
ных путей, что приводит к получению следующего множества:

[ [d,b,a], [e,b,a], [f,c,a], [g,c,a] ]

На последующих этапах продлеваются пути [d,b,a] и [е,Ь,а] и модифициро­ванное множество возможных путей приобретает вид

[ [f,c,s], [g,c,a], [h,d,b,aj, Ji,e,b,a], [j,e,b,a) i

Теперь процесс поиска находит путь [f,c,a], который содержит целевой узел, f, Поэтому данный путь возвращается как решение.

Программа, которая осуществляет указанный процесс, приведена в листинге 11.3. В этой программе все одношаговыо продолжения вырабатываются с использованием встроенной процедуры ЬадоЕ. Выполняется также проверка для предотвращения об­разования циклических путей. Обратите внимание, что в том случае, если продолже­ние пути невозможно, процедура bagof завершается неудачей и поэтому предусмот­рен альтернативный вызов процедуры bresdthfirst. Здесь member и cone, соответ­ственно, представляют собой отношения проверки принадлежности к списку и конкатенации списков.

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

 

Листинг 11.3. Реализация алгоритма поиска в ширину

% solve(Start, Solution):

Решение Solution представляет собой путь (узлы в котором представлены в обратном порядке) от узла Start до целевого узла

solve(Start, Solution):-

breadthfirst([ [Start] ], Solution).

* breadthfirstt [ Pathl, Path2,...], Solution):

Решение Solution представляет собой результат продления одного иэ путей до целевого узла

breadthfirstt [ [Node | Path] _], [Node l Path]):-goal(Mode).

breadthfirstI [Path j Paths], Solution):-extend; Path, KewPaths), concl Paths, NewPaths, Pathsl), breadthfirst! Pathsl, Solution).

extend! [Node I Path], NewPaths):-bagoft [NewNode, Node [ Path],

(s< Node, NewNode), not member С NewNode, [Node I Path} }),

NewPathsi,

% Предложение, выполняемое после неудачного завершения вызова предиката bagof, % который означает, что узел Node не имеет преемников extend (Path, [] >.

Один иэ недостатков этой программы обусловлен низкой эффективностью опера­ции сспс. Этот недостаток можно устранить с помощью способа представления спи­сков в виде разностных пар (см. главу 8). В таком случае множество возможных пу­тей представляется в виде пар списков, Paths и Z, как показано ниже. Paths - г

Применив этот способ представления в программе, приведенной в листинге 11.3, ее можно постепенно преобразовать в программу, показанную в листинге 11.4. Ос­тавляем самостоятельное выполнение этого преобразования в качестве упражнения для читателя.

Листинг 11.4. Более эффективная программа поиска в ширину по сравнению с приведенной в листинге 11.3; это усовершенствование основано на использовании способа представления списка возможных путей в виде разностных пар. Процедура extandприведена в листинге 11.3

* soivef Start, Solution):

Ч Решение Solution представляет собой путь (узлы в котором заданы

% в обратном г.срядке) от узла Start до целевого узла

solve{ Start, Solution):-

breadthfirst! [ [Start] I Z] - Z, Solution).

breadthfirstt ((Node I Path] I _] - _, [Node I Path]):-goal (Node >.

breadthfirst: [Path Paths] - Z, Solution) extend! Path, NewPaths;,

cone NewPaths, SI, Z), % Добавить список NewPaths к концу списка

Paths \— Zl, I Множество возможных путей - не пустое

breadthfirstt Paths - Zi, Solution).

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

Упражнения

11.6. Предположим, что пространство состояний представляет собой дерево с едино­образным ветвлением Ь, а путь к решению имеет длину а. Для частного слу­чая, Ъ = 2 и d = 3, определите, сколько узлов формируется в наихудшем случае при поиске в ширину и при итеративном углублении (учитывая также повторно формируемые узлы). Обозначьте как K(b,d> количество узлов, фор­мируемых при итеративном углублении в общем случае. Найдите рекурсивную формулу, позволяющую получить значение N(b, d] с помощью значения N[ b, a - 1).

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

Paths s~ z:

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

11.8. Как можно воспользоваться программами поиска, приведенными в данном разделе, для проведения поиска от множества начальных узлов, а не от одного начального узла?

11.9. Как можно применить программы поиска, приведенные в этой главе, для по­иска в обратном направлении, при котором поиск начинается с целевого узла и продолжается в направлении начального узла (или одного из начальных уз­лов, при наличии нескольких начальных узлов)? Подсказка: переопределите отношение s. В каких ситуациях обратный поиск является более выгодным по сравнению с прямым?

 

11.10. Иногда имеет смысл проводить двунаправленный поиск; т.е. двигаться с обоих концов — от начального и от целевого узлов. Поиск оканчивается, когда оба пути соединяются. Определите пространство поиска (отношение s) и целевое отношение для заданного графа таким образом, чтобы рассматриваемые проце­дуры поиска, по сути, выполняли двунаправленный поиск.

11.11. В трех процедурах поиска, final, find2 и find3, которые определены ниже, используются разные стратегии поиска. Определите эти стратегии.

findK Mode, [Mode]):-

goal(Node).

findN Mode, [Node | Path]):-

find2< Node, Path):-

conc( Path, ,_ \, Ч Обычная процедура conc/3 для конкатенации списков find:: Node, Pa~th).

find3(Node,- Path):-goal! Goal), find3: Node, [Goal], Path).

finds (Node, [Mode | Path], [Node I Path]).

finds(Node, [Node2 |?athZ], Path):-s(Nodel, Node2), find3(Node, [Nodel, Kode2 [ Path2], Path}.

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

11.12. Изучите следующую программу поиска и опишите используемую в ней страте­
гию поиска:

% search* Start, Pathl - Fath2): найти гл-ть от начального узла S до целевого Путь решения Solution представлен в виде двух списков - Pathl и Path2 search С S, PI - Р2) ■-

similar length[ PI, P2>, % Списки имеют приблизительно равную длину

goal С G),

path2 (G, Р2, Н),

pathl [ S, PI, 8).

pathl (N, [H], N).

pathl (First, [First [ Rest], Last):-s (First, Second), pathl; Second, Rest, Last). path2(к, [N], N).

path2(First, [First I Rest], Last):-s(Second, First), path2 (Second, Rest, Last).

similar_length{ Listl, List2}:- % Списки приблизительно равной длины
equalJLength! List2, List), i Списки равной длины

{ Listl = List; Listl = [_ I List]!.

equal_length([],[]).

equal_length[ [xl | Li), [X2 | L2]):-equal_length'[Ll, L2 i.

11.13. Проведите эксперименты по использованию различных стратегий поиска для решения задачи плакирования в мире кубиков.

11.14. Программы поиска в ширину, приведенные в этой главе, предусматривают проверку только повторяющихся узлов, которые появляются в одном и том же возможном пути. В графах один и тот же узел может быть достигнут с помо­щью разных путей. Такая ситуация данными программами не обнаруживает­ся, поэтому они повторно осуществляют поиск на уровнях ниже тех, на кото­рых находятся подобные узлы. Измените программы, приведенные в листин­гах 11.3 и 11.4, для предотвращения такой ненужной работы,