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

В отличие от стратегии поиска в глубину, стратегия поиска в ширину предусмат­ривает посещение в первую очередь гех узлов, которые являются ближайшими к на­чальномуузлу. Это приводит к осуществлению процесса поиска, который, как пра­вило, развивается в большей степени в ширину, чем в глубину (рис. 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,для предотвращения такой ненужной работы,