Чтение онлайн

встав( Д, [Д1 | ДД], [Д, Д1 | ДД] ) :-

f( Д, F), f( Д1, F1), F=< F1, !.

встав( Д, [Д1 | ДД], [ Д1 | ДД1] ) :-

встав( Д, ДД, ДД1).

% "оценка" находит "возвращенную" F-оценку И / ИЛИ-списка деревьев

оценка( или :[Дер | _ ], F) :-

% Первое дерево ИЛИ-списка - наилучшее

f( Дер, F), !.

оценка( и :[ ], 0) :- !.

оценка( и : [Дер1 | ДД], F) :-

f( Дер1, F1),

оценка( и : ДД, F2),

F is F1 + F2, !.

оценка( Дер, F) :-

f( Дер, F).

% Отношение выбор( Деревья, Лучшее, Остальные, Предел, Предел1):

% Остальные - И / ИЛИ-список Деревья без его "лучшего" дерева

% Лучшее; Предел - ограничение для Списка Деревья, Предел1 -

% ограничение для дерева Лучшее

выбор( Оп : [Дер], Дер, Оп : [ ], Предел, Предел) :- !.

% Только один кандидат

выбор( Оп : [Дер | ДД], Дер, Оп : ДД, Предел, Предел1) :-

оценка( Оп : ДД, F),

( Оп = или, !, мин( Предел, F, Предел1);

Оп = и, Предел1 is Предел - F).

мин( А, В, А) :- А < В, !.

мин( А, В, В).

Рис. 13. 12. Программа поиска с предпочтением в И / ИЛИ-графе.

Еще одна процедура

собрать( ОстДер, НовДер, ЕстьРеш1, НовДеревья, ЕстьРеш)

связывает между собой несколько объектов, с которыми работает расширспис. НовДер– это расширенное дерево, взятое из списка деревьев процедуры расширспис, ОстДер– остальные, не измененные деревья из этого списка, а ЕстьРеш1 указывает на "решающий статус" дерева НовДер. Процедура собрать имеет дело с несколькими случаями в зависимости от значения ЕстьРеш1, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение

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

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

Для отображения решающего дерева можно определить процедуру, аналогичную процедуре отобр (рис. 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, Р), СписокЗадач).