связывает между собой несколько объектов, с которыми работает
расширспис
.
НовДер
— это расширенное дерево, взятое из списка деревьев процедуры
расширспис
,
ОстДер
— остальные, не измененные деревья из этого списка, а
ЕстьРеш1
указывает на "решающий статус" дерева
НовДер
. Процедура
собрать
имеет дело с несколькими случаями в зависимости от значения
ЕстьРеш1
, а также от того, является ли список деревьев И-списком или ИЛИ-списком. Например, предложение
собрать( или : _, Дер, да, Дер, да).
означает: в случае, когда список деревьев — это ИЛИ-список и при только что проведенном расширении получено решающее дерево, считать, что задача, соответствующая всему списку деревьев, также решена, а ее решающее дерево и есть само дерево
Дер
. Остальные случаи легко понять из текста процедуры
собрать
.
Для отображения решающего дерева можно определить процедуру, аналогичную процедуре
отобр
(рис. 13.8). Оставляем это читателю в качестве упражнения.
13.4.3. Пример отношений, определяющих конкретную задачу: поиск маршрута
Давайте теперь сформулируем задачу нахождения маршрута как задачу поиска в И/ИЛИ-графе, причем сделаем это таким образом, чтобы наша формулировка могла бы быть непосредственно использована процедурой
и_или
рис. 13.12. Мы условимся, что карта дорог будет представлена при помощи отношения
связь( Гор1, Гор2, P)
означающего, что между городами
Гор1
и
Гор2
существует непосредственная связь, а соответствующее расстояние равно
P
. Далее, мы допустим, что существует отношение
клпункт( Гор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
Здесь '
через
' — это инфиксный оператор более высокого приоритета, чем '
–
', и более низкого, чем '
– -->
'. Теперь можно определить соответствующий И/ИЛИ-граф явным образом при помощи следующего фрагмента программы:
:- op( 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, P), СписокЗадач).
% Сведение задачи типа "через" к подзадачам,
% связанным отношением И
X-Z через Y---> и : [( X-Y)/0, ( Y-Z)/0].
цель( X-X) % Тривиальная задача: попасть из X в X
Функцию h можно определить, например, как расстояние, которое нужно преодолеть при воздушном сообщении между городами.
Упражнение
13.4. Напишите процедуру
отобр2( РешДер)
для отображения решающего дерева, найденного программой
и_или
рис. 13.12. Формат отображения пусть будет аналогичен тому, что применялся в процедуре
отобр
(рис. 13.8), так что процедуру
отобр2
можно получить, внеся в
отобр
изменения, связанные с другим представлением деревьев. Другая полезная модификация — заменить в