Упражнения. 13.4. Допустим, что некоторый граф AND/OR определен следующим образом:

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.