Належить(Вузол1, Вузли),

Решитьвсе(Вузли).

Решитьвсе(Вузли).

Належить(Вузол1, Вузли),

% Вибір спадкоємця Вузол1 вузла Вузол

розв'язати(Bузол1).

розв'язати(Вузол):-

Вузол ---> і: Вузли, % Вузол - І-Вузол

% Розв'язати всі задачі-спадкоємці

решитьвсе([ ]).

решитьвсе([Вузол | Вузли]):-розв'язати(Вузол),

Тут належить - звичайне відношення приналежності елемента до списку. Ця програма усе ще має недоліки:

· вона не породжує вирішуюче дерево, і

· вона може зациклюватись, якщо І/Або-Граф має циклічну структуру.

Щоб програма породжувала вирішуюче дерево, до відношення розв'язати додається ще один аргумент:

розв'язати(Вузол, Решдер).

Вирішуюче дерево згідно до трьох випадків представляють так:

· Якщо Вузол - цільовий, то відповідне вирішуюче дерево і є саме цей вузол Вузол.

· Якщо Вузол - Або-Вузол, то вирішуюче дерево має вигляд

Вузол ---> Піддерево

де Піддерево - це вирішуюче дерево для одного зі

спадкоємців вузла Вузол.

· Якщо Вузол - І-Вузол, то вирішуюче дерево має вигляд

Вузол ---> і: Піддерева

де Піддерева - список вирішуючих дерев для всіх спадкоємців вузла Вузол.

% Пошук вглиб для І/Або-Графів

розв'язати(Вузол, Вузол):- % Вирішуюче дерево для

цільового вузла - це сам вузол

ціль(Вузол).

розв'язати(Вузол, Вузол ---> Дер):-

Вузол ---> або: Вузли, % Вузол - Або-Вузол

% Вибір спадкоємця Вузол1 вузла Вузол

розв'язати(Bузол1, Дер).

розв'язати(Вузол, Вузол ---> і: Дерева):-

Вузол ---> і: Вузли, % Вузол - І-Вузол

решитьвсе(Вузли, Дерева).

% Розв'язати всі задачі-спадкоємці

решитьвсе([ ], [ ]).

решитьвсе([Вузол|Вузли], [Дер|Дерева]):-

розв'язати(Вузол, Дер),

решитьвсе(Вузли, Дерева).

% Відобразити вирішуюче дерево з відступом 0

отобр(Дер):- отобр(Дер, 0),!.

% Відобразити вирішуюче дерево з відступом Н

отобр(Вузол ---> Дер, Н):- write(Вузол), write('--->'),

H1 = H + 7, отобр(Дер, H1),!.

% Відобразити І-Список вирішуючих дерев

отобр(і: [Д], Н):- отобр(Д, Н).

отобр(і: [Д | ДД], Н):- отобр(Д, Н), tab(H),отобр(і: ДД, Н),!.

отобр(Вузол, Н):- write(Вузол), nl.

Ця програма може зациклюватись. Процедура розв'язати(Вузол, РешДер) знаходить вирішуюче дерево для деякого вузла в І/Або-Графі, а процедура отобр показує його користувачу. (У процедурі отобр вважається, що на вивід вузла витрачається лише один символ.)

Наприклад дерево, що вирішує рис. 2, буде видрукувано процедурою отобр у наступному виді:

а ---> b ---> d

е ---> h

Наведена програма усе ще зберігає схильність до входження в нескінченні цикли. Один із простих способів уникнути нескінченних циклів - це стежити за поточною глибиною пошуку й не давати програмі заходити за межі деякого обмеження по глибині. Це можна зробити, увівши у відношення розв'язати ще один аргумент:

розв'язати(Вузол, Решдер, Максглуб)

Як і раніше, вузлом Вузол представлено розв'язувану задачу, а РешДер - це розв'язок цієї задачі, що має глибину, не більшу за МаксГлуб. МаксГлуб - це припустима глибина пошуку в графі. Якщо МаксГлуб = 0, то рухатись далі заборонено, якщо ж МаксГлуб > 0, то пошук поширюється на спадкоємців вузла Вузол, причому глибиною МаксГлуб - 1 на одиницю меншу попереднього обмеження. Це доповнення легко вводиться в останню програму. Наприклад, друге твердження процедури розв'язати прийме вид:

розв'язати(Вузол, Вузол ---> Дер, МаксГлуб):-

МаксГлуб > 0,

Вузол ---> або: Вузли, % Вузол - Або-Вузол

Дата добавления: 2014-01-04