Лекции.Орг


Поиск:




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





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 324 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Если президенты не могут делать этого со своими женами, они делают это со своими странами © Иосиф Бродский
==> читать все изречения...

991 - | 930 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.