Будем искать пути на графе, ребрам которого приписаны веса, указанные в скобках (рис. 8.4).
рис. 8.4
Естественно возникает задача о поиске минимального пути от A до Z, если под длиной (стоимостью) пути понимать сумму весов входящих туда ребер. Такой граф будем хранить в виде утверждений базы данных — списков инцидентности graph1.
Процедура поска пути way, кроме нахождения пути, должна будет вычислять еще его стоимость. Поэтому к ней нужно будет добавить еще два аргумента — стоимость текушего пути (SW) и стоимость окончательного решения (S). Ей будет соответствовать описание
way1(uzl,list,integer,list,integer)
и первый вызов из процедуры верхнего уровня show_min
way1(Z, [A], 0, Solution, S),
где 0 — стоимость начального пути и S — стоимость решения.
Аналогично, процедуры sosed1 и member1 должны иметь в качестве аргументов стоимость соответствующего ребра и список стоимостей ребер к вершинам — соседкам.
sosed1(uzl,uzl,integer)
member1(uzl,list,list1,integer)
Процедура member1, выбирая очередную соседку из списка соседок, будет выбирать стоимость соответствующего ребра из списка стоимостей:
member1(Y,[Y|_],[Stoim|_],Stoim)
Затем они (соседка Y и стоимость Stoim) будут передаваться в процедуру sosed1. Процедура way1, получив их из процедуры sosed1, после соответствующей проверки, добавит Y к текущему пути, а вес ребра — к текущей стоимости.
way1(Z, [X|Was],SW, Sol,S):-
sosed1(X,Y,St), % St — вес ребра (X-Y).
not(member(Y,Was)),
SW1=SW+St,
way1(Z, [Y,X|Was],SW1, Sol,S).
SW1 — стоимость текущего пути, S — стоимость решения.
Нетрудно, немного изменив программу поиска пути, находить всевозможные пути от A до Z с их стоимостями. Но нам нужен один-единственный путь — путь минимальной стоимости.
Обычный алгоритмический способ — запоминать текущий минимум, сравнить с ним каждый свеженайденный путь и, в случае необходимости, менять минимум, — здесь неприемлем. Пути мы получаем за счет возвратов, а глобальной переменной, чтобы запоминать текущий минимум, у нас пока нет (пока мы не умеем работать с динамической базой данных).
Реализуем декларативную идею поиска минимального пути. Словами ее можно выразить так:
«мы сгенерировали путь, который будет минимальным, потому что невозможно сгенерировать путь меньшей стоимости». На Прологе это можно записать примерно так:
show_min:-
way1(Z, [A], 0, Solution, MinS),
not(way1(Z, [A], 0, _, S),
S < MinS).
Анонимная переменная стоит на месте НЕСУЩЕСТВУЮЩЕГО пути, вид которого нас не интересует.
Это правило будет работать следующим образом:
вначале way1 найдет некий путь Solution. Затем правило not будет генерировать пути и проверять, что их стоимость больше стоимости MinS. Если найдется путь меньшей стоимости, not даст отказ, и произойдет возврат к way1, которая сгенерирует новый путь Solution и т.д.
Наконец, будет найден такой путь Solution, для которого not сгенерирует ВСЕ пути, но ни один не окажется меньше. not даст успех, и все правило show_min окончится успехом.
В случае большого количество путей (например, для полного графа) выполнение этого правила приведет к КОМБИНАТОРНОМУ ВЗРЫВУ. В следующей главе будет показано, как существенно уменьшить число переборов.
Поскольку встроенный предикат not не может иметь в качестве аргумента более одного предиката, конъюнкцию way1(Z, [A], 0, _, S), S < MinS
нужно записать в виде отдельного правила:
min_way(Z, A, MinS):-
way1(Z, [A], 0, _, S),
S < MinS.
/* Программа 8.5 «Поиск пути от A до Z */
/* минимальной стоимости» */
domains
uzl=integer
list=uzl*
list1=integer*
predicates
num_uzl(integer)
graph1(list,list1)
show_way1
min_way(uzl,uzl,integer)
show_min
way1(uzl,list,integer,list,integer)
sosed1(uzl,uzl,integer)
member1(uzl,list,list1,integer)
member(uzl,list)
goal
show_min.% показать путь минимальной стоимости
clauses
num_uzl(5). % число вершин графа
graph1([1,2,3,4],[3,0,2]).
graph1([2,1,3,5],[3,4,5]).
graph1([3,1,2,4],[0,4,0]).
graph1([4,1,3,5],[2,0,1]).
graph1([5,2,4],[5,1]).
show_min:-
write("Начало пути "), readint(A),
write("Конец пути "), readint(Z),
way1(Z, [A], 0, Solution, MinS),
not(min_way(Z, A, MinS)),
% не существует пути стоимости меньшей, чем MinS
write("MIN ", Solution," ст.= ", MinS).
min_way(Z, A, MinS):-
way1(Z, [A], 0, _, S),
S < MinS.
% находим путь стоимости S меньшей, чем MinS.
way1(Z, [Z|Was],S, [Z|Was],S).
way1(Z, [X|Was],SW, Sol,S):-
sosed1(X,Y,St), % St — вес ребра (X-Y).
not(member(Y,Was)),
SW1=SW+St,
way1(Z, [Y,X|Was],SW1, Sol,S).
sosed1(X, Y, St):-
graph1([X|T], LS),
member1(Y, T, LS, St).
member1(H,[H|_],[S|_],S).
member1(X,[_|T],[_|ST],S):-
member1(X,T,ST,S).
% детерминированная процедура
% отыскивает первое вхождение H
member(H,[H|_]):-!.
member(X,[_|T]):-
member(X,T).
/* Конец программы */
В заключение рассмотрим более подробно свойства предиката not. Этот предикат определяется следующим образом:
not(P):-
P,!,fail.
not(P):- true.
Пусть P — детерминированный предикат. Если P истинен, то комбинация ! и fail вызывают отказ цели not(P), без возможности ее повторного передоказательства. Если P ложен, то второе правило согласует not(P) как истину.
В нашей программе P(min_way) недетерминированный предикат.
Если P истинен, то аналогично детерминированному P not(P) дает отказ.
Если P ложен, то прежде, чем произойдет переход на второе правило и согласование not(P), система переберет всевозможные способы передоказательства P (в нашей программе min_way сгенерирует всевозможные пути и сравнит их стоимости с минимальной). Если ВСЕ эти решения окажутся ложными, то только тогда not(P) будет согласован.
