4. Поиск гамильтоновых циклов
Задача о поиске гамильтонова цикла на неориентированном графе — классическая задача теории графов и классическая NP-полная задача с точки зрения классификации задач по степени их вычислительной сложности.
Преобразуем предыдущую программу в программу поиска всех гамильтоновых циклов графа (рис 8.2). Воспользуемся тем, что мы умеем находить на графе все пути от A до Z. Добавим к нашей программе процедуру верхнего уровня gami, в которой будет проверяться, замкнется ли найденный путь в гамильтонов цикл.
Единственный недостаток такой программы то, что каждый цикл будет находиться и печататься дважды. Например, цикл 1-2-5-4-3-1 будет найден как замыкание пути 1-2-5-4-3 и при замыкании пути 1-3-4-5-2. Чтобы существенно не усложнять программу, смиримся с двойной печатью каждого цикла.
По определению, гамильтонов цикл проходит через все вершины графа ровно один раз, кроме вершины, являющейся одновременно и началом, и концом. Так как гамильтонов цикл содержит все вершины, то поиск его можно начать с любой вершины. Выберем некоторую вершину A и будем генерировать все пути, начинающиеся в A и заканчивающиеся в произвольной вершине. Процедура way будет генерировать путь, состоящий из различных вершин, поэтому останется проверить, замыкается ли он в полный цикл, то есть, содержит ли он все вершины графа, и существует ли ребро, соединяющее конец пути с вершиной A.
gami(A, Solution):-
% путь выходит из A и заканчивается в любой вершине
way(_, [A], Solution),
% замкнется ли он в гамильтонов цикл ?
full_cycle(A, Solution).
/* Программа 9.4 «Гамильтоновы циклы» */
domains
uzl=integer
list=uzl*
predicates
show_cycle
num_uzl(integer)
graph(list)
gami(uzl,list)
way(uzl,list,list)
full_cycle(integer,list)
full(integer,list)
sosed(uzl,uzl)
member(uzl,list)
goal
show_cycle.
clauses
num_uzl(5).
graph([1,2,3,4]).
graph([2,1,3,5]).
graph([3,1,2,4]) .
graph([4,1,3,5]).
graph([5,2,4]).
show_cycle:-
write("Начало цикла "),readint(A),nl,
gami(A, Solution), write(Solution),
nl, fail.
gami(A, Solution):-
way(_, [A], Solution),
full_cycle(A, Solution).
way(Z, [Z|Was1],[Z|Was1]).
way(Z, [X|Was1], Sol):-
sosed(X,Y),
not(member(Y,Was1)),
way(Z, [Y,X|Was1], Sol).
full_cycle(A, [H|S]):-
sosed(H, A),!, % путь замыкается в цикл,
num_uzl(N), % N — число вершин графа,
full(N, [H|S]).% в цикле все вершины графа
full(0,[]):-!. % в пустом пути 0 вершин
full(N, [_|T]):- % в цикле ровно N вершин
N1=N-1,
full(N1, T).
sosed(X,Y):-
graph([X|T]),
member(Y,T).
member(H,[H|_]).
member(X,[_|T]):-
member(X,T).
/* Конец программы */
5. Поиск пути минимальной стоимости
Будем искать пути на графе, ребрам которого приписаны веса, указанные в скобках (рис. 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) будет согласован.