ПОИСК ГАМИЛЬТОНОВЫХ ЦИКЛОВ

Задача о поиске гамильтонова цикла на неориентированном графе — классическая задача теории графов и классическая 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).

/* Конец программы */