Глава 11. 11.1. Depthf irstl ( [Node I PathJ, [Node I Path]) :-goal( Node)

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. Двунаправленный поиск с итеративным углублением с обоих концов.