13.4. Допустим, что некоторый граф AND/OR определен следующим образом:
а --> or:[Ь/1,с/2]. b ---> and:[d/l,e/l].
с------ > and: [e/1, f/1].
d------ > or: fli /G].
e — > or:[h/2].
f —> oc:ih/4,i/2].
goal(h). goal(i).
Нарисуйте все деревья решения и рассчитайте их стоимости. Предположим, что поиск в этом графе осуществляется с помощью алгоритма АО*, где начальным узлом является а, а все эвристические h-значения узлов Ь, а, е, h и i равны 0. Задайте интервалы для значений h(c) и h(f), которые позволяют найти оптимальное решение с помощью алгоритма АО*.
13.5. Напишите процедуру
showZ(SolutionTree)
для отображения дерева решения, найденного программой andor {см. листинг 13.2). Допустим, что формат отображения является аналогичным применяемому в процедуре show (см. листинг 13.1), чтобы show2 можно было написать как модификацию show с использованием другого представления дерева. Еще одной полезной модификацией может оказаться замена цели write (Node) в процедуре show определяемой пользователем процедурой writenodet Node, В)
которая выводит узел Node в некоторой подходящей форме и конкретизирует переменную к значением количества символов, которое потребуется для выво-
Глава 13. Декомпозиция задач и графы AND/OR
да узла Node в этой форме. Таким образом, К используется для вывода обозначений поддеревьев с подходящим отступом.
Резюме
• Графы AND/OR применяются в качестве формального способа представления задач. Они естественным образом подходят для тех задач, которые могут быть разложены на независимые подзадачи. Примерами таких задач могут служить задачи поиска выигрыша в играх.
• Узлы в графе AND/OR относятся к двум типам: AND и OR.
Каждая конкретная задача определяется начальным узлом и целевым состоянием. Решение задачи представляется с помощью дерева решения.
■ На графе AND/OR можно показать стоимости дуг и узлов для моделирования задач оптимизации.
• Решение любой задачи, представленной с помощью графа AND/OR, сводится к поиску в графе. Стратегия поиска в глубину предусматривает систематическое обследование графа и может быть легко реализована в программе. Но такая программа может характеризоваться низкой эффективностью из-за комбинаторного роста количества вариантов.
• Для обозначения сложности задач могут быть введены эвристические оценки, а для управления поиском может применяться эвристический принцип поиска по заданному критерию. Реализация такой стратегии является более трудной.
• В данной главе приведены программы Prolog для поиска в глубину, поиска в глубину с итеративным углублением и поиска по заданному критерию в графах AND/OR.
• В данной главе введены следующие понятия:
• графы AND/OR;
• дуги AND, дуги OR;
• узлы AND, узлы OR;
• граф решения, дерево решения;
• стоимость дуги, стоимость узла;
• эвристические оценки в графах AND/OR, резервные копии оценок;
• поиск в глубину в графах AND/OR;
• итеративное углубление в графах AND/OR;
• поиск по заданному критерию в графах AND/OR.
