а ---> b ---> и : [d, c ---> h]
Три формы представления решающего дерева соответствуют трем предложениям отношения решить. Поэтому все, что нам нужно сделать для изменения нашей исходной программы решить, - это подправить каждое из этих трех предложений, просто добавив в каждое из них решающее дерево в качестве второго аргумента. Измененная программа показана на рис. 13.8. В нее также введена дополнительная процедура отобр для отображения решающих деревьев в текстовой форме. Например, решающее дерево рис. 13.4 будет отпечатано процедурой отобр в следующем виде:
а ---> b ---> d
е ---> h
Программа рис. 13.8 все еще сохраняет склонность к вхождению в бесконечные циклы. Один из простых способов избежать бесконечных циклов - это следить за текущей глубиной поиска и не давать программе заходить за пределы некоторого ограничения по глубине. Это можно сделать, введя в отношение решить еще один аргумент:
решить( Верш, РешДер, МаксГлуб)
Как и раньше, вершиной Верш представлена решаемая задача, а РешДер - это решение этой задачи, имеющее глубину, не превосходящую МаксГлуб. МаксГлуб -это допустимая глубина поиска в графе. Если МаксГлуб = 0, то двигаться дальше запрещено, если же МаксГлуб > 0, то поиск распространяется на преемников вершины Верш, причем для них устанавливается меньший предел по глубине, равный МаксГлуб -1. Это дополнение легко ввести в программу рис. 13.8. Например, второе предложение процедуры решить примет вид:
решить( Верш, Верш ---> Дер, МаксГлуб) :-
МаксГлуб > 0,
Верш ---> или : Вершины, % Верш - ИЛИ-вершина
принадлежит ( Верш1, Вершины),
% Выбор преемника Верш1 вершины Верш
Глуб1 is МаксГлуб - 1, % Новый предел по глубине
решить( Bepш1, Дер, Глуб1).
% Решить задачу-преемник с меньшим ограничением
Нашу процедуру
поиска в глубину с ограничением
можно также использовать для имитации
поиска в ширину
.
Идея состоит в следующем
: многократно повторять поиск в глубину каждый раз все с большим значением ограничения до тех пор, пока решение не будет найдено, То есть попробовать решить задачу с ограничением по глубине, равным 0, затем - с ограничением 1, затем - 2 и т.д. Получаем следующую программу:
имитация_в_ширину( Верш, РешДер) :-
проба_в_глубину( Верш, РешДер, 0).
% Проба поиска с возрастающим ограничением, начиная с 0
проба_в_глубину( Верш, РешДер, Глуб) :-
