11.1. depthf irstl ([Node I PathJ, [Node I Path]):-goal(Node). depthfirstK [Node I Path], Solution):-s[ Node, Nodel), not member] Nodel, Path), depthfitstll [Nodel, Node I Path], Solution).
113 * Процедура поиска с итеративным углублением, в которой
% глубина перестает увеличиваться, если отсутствует путь % на текущую глубину iterative_deepening(Start, Solution):-
id_path[ Start, Mode, [], Solution),
goal[ Node). i path[ First, Last, Path): переменная Path представляет % собой список узлов от First до Last path[ First, First, [First]). path(First, Last, [First, Second I Rest]):-
s(First, Second),
path[ Second, Last, [Second I Rest]). % Процедура формирования пути с итеративным углублением % idj>ath(Fir3t, Last, Template, Path): переменная Path % представляет собой путь от узла First до узла Last, длина h которого не превышает длину применяемого в качестве i образца списка Template. Альтернативные пути % вырабатываются в порядке возрастания длины id_path(First, Last, Template, Path):-
Path - Template,
path! First, Last, Path)
copy_term(Template, P),
path(First, _, P),!, % По меньшей мере один путь % с длиной, равной длине списка Template idjpathf First, Last, [_ I Template], Path). % Путь 4 с длиной, превышающей длину списка Template
11.6. Поиск в ширину - 15 узлов; итеративное углубление - 26 узлов.
N(b, 0) = 1
N(b, d) = К { b, d - 1) + (b" + 1 - l)/(b - 1) при d > 0
11.8. solve! StartSet, Solution):- £ StartSet - это список
% начальных узлов bagof((Node), member! Mode, StartSet), CandidatePaths), breadthfirst[ CandidatePaths, Solution),
11.9. Поиск в обратном направлении является более выгодным, если коэффициент ветвления в об-
ратном направлении меньше, чем в прямом. Поиск в обратном направлении применим, только если целевой узел явно определен.
% Предположим, что origs(Model, Node2) - первоначальное i отношение с определением пространства состояний $ Определите новое отношение s следующим образом: s{ Nodel, Node2):-origs(Node2, Nodel).
11.10. % Состояниями для двунаправленного поиска являются пары
% узлов StartNode-EndNode из первоначального пространства
% состояний, обозначающие качало и цепь поиска
s(Start - End, NewStart - NewEnd) :-
origs{ Start, MewStart), % Шаг в прямом направлении origs (NewEnd, End)..* Шаг в обратном направлении % goal(Start - End) для двунаправленного поиска
goal! Start - Start). h Качало совпадает с концом
goal(Start - End):-
origs(Start, End). % До конца остался один шаг
Решения к отдельным упражнениям
It. 11. find l - поиск в глубину; f i n d 2 - итеративное углубление (предикат cone (Path, _,_)
формирует шаблоны списков все возрастающей длины, которые вынуждают предикат f i n d l перейти в режим итеративного углубления); f i n d 3 - поиск в обратно» направлении.
11.12. Двунаправленный поиск с итеративным углублением с обоих концов.
