Неизвестно - Prolog

собрать( или : _, Дер, да, Дер, да).

означает: в случае, когда список деревьев - это ИЛИ-список и при только что проведенном расширении получено решающее дерево, считать, что задача, соответствующая всему списку деревьев, также решена, а ее решающее дерево и есть само дерево Дер. Остальные случаи легко понять из текста процедуры собрать.

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре отобр(рис. 13.8). Оставляем это читателю в качестве упражнения

.

13. 4. 3. Пример отношений, определяющих конкретную задачу: поиск маршрута

Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И / ИЛИ-графе, причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой и_илирис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения

связь( Гор1, Гор2, Р)

означающего, что между городами Гор1и Гор2существует непосредственная связь, а соответствующее расстояние равно Р. Далее, мы допустим, что существует отношение

клпункт( Гор1-Гор2, Гор3)

имеющее следующий смысл: для того, чтобы найти маршрут из Гор1в Гор2, следует рассмотреть пути, проходящие через Гор3( Гор3- это "ключевой пункт" между Гор1и Гор2). Например, на карте рис. 13.1 f и g - это ключевые пункты между а и z :

клпункт( a-z, f). клпункт( a-z, g).

Мы реализуем следующий принцип построения маршрута:

Для того, чтобы найти маршрут между городами X и Z, необходимо:

(1) если между X и Z имеются ключевые пункты Y1, Y2, ..., то найти один из путей:

путь из X в Z через Y1, или

путь из X в Z через Y2, или

...

(2) если между X и Z нет ключевых пунктов, то найти такой соседний с X город Y, что существует маршрут из Y в Z.

Таким образом, мы имеем два вида задач, которые мы будем представлять как

(1) X-Z найти маршрут из X в Z

(2) X-Z через Y найти маршрут из X в Z, проходящий через Y

Здесь 'через' - это инфиксный оператор более высокого приоритета, чем '-', и более низкого, чем '--->'. Теперь можно определить соответствующий И / ИЛИ-граф явным образом при помощи следующего фрагмента программы:

:- ор( 560, xfx, через)

% Правила задачи X-Z, когда между X и Z

% имеются ключевые пункты,

% стоимости всех дуг равны 0

X-Z ---> или : СписокЗадач

:- bagof( ( X-Z через Y)/0, клпункт( X-Z, Y),

СписокЗадач), !.

% Правила для задачи X-Z без ключевых пунктов

X-Z ---> или : СписокЗадач

:- bagof( ( Y-Z)/P, связь( X, Y, Р), СписокЗадач).

% Сведение задачи типа ''через" к подзадачам,

% связанным отношением И

X-Z через Y---> и : [( X-Y)/0, ( Y-Z)/0].

цель( Х-Х) % Тривиальная задача: попасть из X в X

Функцию h можно определить, например, как расстояние, которое нужно преодолеть при воздушном сообщении между городами.

Упражнение

13. 4. Напишите процедуру

отобр2( РешДер)

для отображения решающего дерева, найденного программой и_илирис. 13.12. Формат отображения пусть будет аналогичен тому, что применялся в процедуре отобр(рис. 13.8), так что процедуру отобр2можно получить, внеся в отобризменения, связанные с другим представлением деревьев. Другая полезная модификация - заменить в отобрцель write( Верш)на процедуру, определяемую пользователем

печверш( Верш, H)

которая выведет Вершв удобной для пользователя форме, а также конкретизирует Н в соответствии с количеством символов, необходимом для представления Вершв этой форме. В дальнейшем Н будет использоваться как величина отступа для поддеревьев.

Резюме

И / ИЛИ-граф - это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером могут служить игры.

Вершины И / ИЛИ-графа бывают двух типов: И- вершины и ИЛИ-вершины.

Конкретная задача определяется стартовой вершиной и целевым условием. Решение задачи представляется решающим деревом.

Для моделирования оптимизационных задач в И / ИЛИ-граф можно ввести стоимости дуг и вершин.

Процесс решения задачи, представленной И / ИЛИ-графом, включает в себя поиск в графе. Стратегия поиска в глубину предусматривает систематический просмотр графа и легко программируется. Однако эта стратегия может привести к неэффективности из-за комбинаторного взрыва.