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