Реалізація деяких методів пошуку в просторі станів у мові Пролог
Простір станів у мові Пролог можна подати як відношення after(x, y). Наприклад, якщо простір станів можна зобразити у вигляді дерева, показаного на рис. 12, то його записують таким чином:
after(a,b).
after(b,c).
after(a,d).
after(d,e).
Рис. 12. Приклад дерева
Пошук углиб реалізований у мові Пролог за допомогою такої ідеї. Для того щоб знайти шлях Solution із певної вершини A в деяку цільову вершину, необхідно:
якщо A – цільова вершина, то встановити Solution = A;
якщо для вихідної вершини A існує вершина-наступник A1, така що можна провести шлях Solution1 із A1 у цільову вершину, то встановити Solution = [A | Solution1].
Мовою Пролог це правило записують так:
solve(A, [A]) :-
destination(A).
solve(A, [A|Solution]) :-
after(A, A1),
solve(A1, Solution).
Ця програма має недолік – вона може зациклитися, якщо в просторі станів є цикли. Для її вдосконалення треба додати механізм виявлення циклів.
Пошук ушир програмувати більш складно, ніж пошук углиб, тому що доводиться зберігати всю множину вершин-кандидатів, а не тільки одну. Крім того, якщо нам треба знайти розв’язувальний шлях, то однієї множини вершин недостатньо. Тому будемо зберігати не множину вершин-кандидатів, а множину шляхів-кандидатів. Простір станів у цьому випадку зручно подавати за допомогою відношення children(x, [y, z]). Наприклад, для дерева, наведеного на рис. 13, можна записати таке:
children(a, [b, e]).
children(b, [c, d]).
children(e, [f]).
Рис. 13. Приклад дерева
Знайдемо відношення пошуку вшир breadth_star(Roads, Answer). Це відношення буде істинним, якщо існує шлях із множини кандидатів Roads, який можна продовжити до цільової вершини. Цей продовжений шлях і є Answer.
У розглядуваній реалізації множина шляхів-кандидатів буде подана як список шляхів, а кожен шлях – як список вершин, перерахованих у зворотному порядку, тобто головою списку буде остання з породжених вершин. Пошук починається з одноелементної множини кандидатів [[Start]].
Загальні принципи пошуку вшир такі. Для того щоб виконати пошук ушир за заданої множини шляхів-кандидатів, необхідно:
якщо голова першого шляху – цільова вершина, то взяти цей шлях як розв’язок;
у противному разі видалити перший шлях із множини кандидатів і створити множину всіх можливих продовжень цього шляху на один крок; множину продовжень додати в кінець множини шляхів-кандидатів, а потім виконати пошук ушир з отриманою новою множиною.
Подана нижче програма реалізує цей алгоритм.
breadth_first(Start,Answer):-
breadth_star([[Start]], Answer).
breadth_star([[H|Road]|_], [H|Road]):-
destination(H).
breadth_star([[H|T]|Roads], Answer) :-
children(H, Children), make_road(Children, [H|T], Child_Roads),
append1( Roads, Child_Roads, New_Roads),!,
breadth_star( New_Roads, Answer).
breadth_star(Roads, Answer). % випадок, якщо у Н немає наступника
Множину продовжень шляху породжують два відношення – children(H, Children) і make_road(Children, [H|T], Child_Roads), перше відношення спочатку породжує список вершин-наступників Children вершини H, а друге – список шляхів-спадкоємців Child_Roads, які ведуть із вершини H. Предикат make_road можна реалізувати так:
make_road([], _, []).
make_road([H|T], L, [New_L|T1]):-
append([H], L, New_L),
make_road(T, L,T1).
Предикат append1(Roads, Child_Roads, New_Roads) додає множину шляхів-продовжень у кінець множини шляхів-кандидатів:
append1([],L,L).
append1([X|L1],L2,[X|L3]):-
append1(L1,L2,L3).
Якщо у вершини H немає вершин-наступників і відношення children(H, Children) неуспішне, відбувається альтернативний запуск процедури breadth_star(Roads, Answer).