КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Належить(Вузол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; Просмотров: 364; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |