How to - Graph Coloring in Prolog

Question

Я пытаюсь сделать простой алгоритм раскраски графа в Prolog, но мне немного сложно понять язык. Я знаю, что хочу сделать - хочу перейти к вершине, найти все другие вершины, связанные с ней, проверить цвет моей вершины и, в зависимости от этого, окрасить другие вершины разными цветами. Мне просто сложно перевести это на Prolog. Если бы это был диалект С или Ява, для меня это был бы кусок пирога, но это придает мне припадки.

Это то, что я до сих пор:

main:- graph_coloring. 

%color_list([blue, red, green, yellow, white], colors). 
%vertex_list([a, b, c, d], vertices). 
%edge_list([(a,b),(b,c),(c,d)], edges). 

%Our graph 
color(blue). 
color(red). 
color(green). 
color(black). 
color(white). 

%graph([a-b, b-c, b-d, c-d]). 

vertex(a). 
vertex(b). 
vertex(c). 
vertex(d). 

%Subject to changing, so are asserted into listener at runtime. 
init_dynamic_facts:- 
    assertz(vertex_color(a, none)), 
    assertz(vertex_color(b, none)), 
    assertz(vertex_color(c, none)), 
    assertz(vertex_color(d, none)), 
    assertz(location(a)). 

edge(a,b). 
edge(b,c). 
edge(b,d). 
edge(c,d). 

is_connect(A,B):- 
    edge(A,B). 
is_connect(A,B):- 
    edge(B,A). 

connections(Vertex):- 
    edge(Vertex,X). 
connections(Vertex):- 
    edge(X,Vertex). 

move(Vertex):- 
    retract(location(_)), 
    asserta(location(Vertex)). 

paint_vertex(Vertex, Color):- 
    retract(vertex_color(Vertex,_)), 
    asserta(vertex_color(Vertex, Color)). 

find_vertex_color(Vertex):- 
    vertex_color(Vertex, X). 


graph_coloring:- 

    location(Current_vertex), 
    vertex_color(Current_vertex, Curr_color), 
    (Curr_color =:= none -> 
     connections(Current_vertex, Others), 
     vertex_color(Others, Other_colors), 
     paint_vertex(Current_vertex, 

Как я могу завершить этот алгоритм?

(отредактирован: больше кода под graph_coloring)

Answer 1

Я думаю, что вы пытаетесь думать таким образом, что это не естественно для программ Prolog; то есть вы пытаетесь не использовать рекурсию :) То, что я придумал, следующее: это может быть не совсем правильно (уже поздно, и у меня нет хорошей репутации, когда вы пытаетесь иногда думать это ... :))

Давайте предположим, что у вас есть график, описываемый следующими фактами:

edge(a,b). 
edge(b,c). 
edge(b,d). 
edge(c,d). 

и доступные цвета

color(blue). 
color(red). 
color(green). 

(вам нужно только 3 цвета для цветного планарного графика, так что давайте просто используем 3 здесь). Предположим также, что вы хотите получить ответ в виде списка [Vertex-Color], в котором список будет содержать цвет для каждой вершины вашего графика. Я считаю, что следующее является правильным решением:

coloring([V-C]) :- 
     color(C), 
     \+ edge(V,_). 
coloring([V-C,V1-C1|Coloring]) :- 
     color(C), 
     edge(V,V1), 
     V \== V1, 
     coloring([V1-C1|Coloring]), 
     C1 \== C. 

Первый пункт говорит, что если нет края от V до любой другой вершины, просто перепробовать все возможные цвета. Второе предложение гласит, что вершина V получит цвет C, а вершина V1 получит цвет C1, если есть ребро от V до V1, где V! = V1 и C! = C1. (Я также предположил, что ваш граф связан, т. Е. Нет вершин, которые не связаны с другими вершинами).

И так как нам нужны только решения, в которых все вершины имеют цвета, мы будем вести только списки длины | V |, где V - множество вершин, которые у вас есть. Вы можете реализовать это ограничение различными способами; Я предпочитаю использовать «FindAll/3»:

colors(X) :- 
     coloring(X), 
     findall(V,edge(V,_),List), 
     length(List,Len), 
     length(X,Len). 

Теперь, обратившись эту программу и просить |?- colors(X). вы получите все возможные цветовые задания для вершин вашего графика.

Если кто-то находит проблему, я почти уверен, что существует в указанном выше растворе, пожалуйста, дайте нам знать :)

Спирос

Answer 2

Я хотел бы упомянуть эту проблему является типичным ограничения удовлетворения проблема и может быть эффективно решена с использованием модуля CSP SWI-Prolog.Вот полный алгоритм:

:- use_module(library(clpfd)). 

color(red). 
color(blue). 
color(green). 

vertex(a). 
vertex(b). 
vertex(c). 
vertex(d). 
vertex(e). 

edge(a,b). 
edge(a,c). 
edge(b,c). 
edge(b,d). 
edge(c,d). 


colorGraph(ColorList) :- 
    findall((X, Y), edge(X, Y), Edges), 
    findall(X, vertex(X), Vertexes), 
    findall(hasColor(X, _), member(X, Vertexes), ColorList), 
    createConstraint(Edges,ColorList), 
    colorNodes(ColorList). 

createConstraint([],_). 
createConstraint([(V1,V2)|RL],ColorList):- 
    member(hasColor(V1,C1),ColorList), 
    member(hasColor(V2,C2),ColorList), 
    dif(C1,C2), 
    createConstraint(RL,ColorList). 

colorNodes([]). 
colorNodes([hasColor(_,C)|Nodes]) :- 
    color(C), 
    colorNodes(Nodes). 

color/1 показывает цвета, доступные, vertex/1 показывает вершины на графике и edge/2 определяет пары между вершинами. Кроме того, colorGraph(?List) определяет цвет вершин, где List - это список hasColor(Vertex, Color), Vertex - цветная вершина с использованием Color.

Давайте рассмотрим каждую часть алгоритма выше, чтобы понять, что происходит.

:- use_module(library(clpfd)). 

Это указывает на то, чтобы SWI-Prolog загрузить модуль, содержащий предикаты для задач удовлетворения ограничений.

colorGraph(ColorList) :- 
    findall((X, Y), edge(X, Y), Edges), 
    findall(X, vertex(X), Vertexes), 
    findall(hasColor(X, _), member(X, Vertexes), ColorList), 
    createConstraint(Edges,ColorList), 
    colorNodes(ColorList). 

предикат colorGraph/1 является точкой входа алгоритма. Он преобразует классы ребер/вершин в списки, ограничивает ColorList, чтобы иметь список определенных вершин и, наконец, создавать ограничения на цвета и назначать цвета (это две отдельные операции).

createConstraint([],_). 
createConstraint([(V1,V2)|RL],ColorList):- 
    member(hasColor(V1,C1),ColorList), 
    member(hasColor(V2,C2),ColorList), 
    dif(C1,C2), 
    createConstraint(RL,ColorList). 

predictate createConstraint/2 просто заявляет, что два связанных Вершины должны иметь другой цвет. Стоит отметить, что dif/2 является предикатом CSP.

colorNodes([]). 
colorNodes([hasColor(_,C)|Nodes]) :- 
    color(C), 
    colorNodes(Nodes). 

Предикат colorNodes/1 присваивает правильный цвет вершин. Prolog собирается позаботиться о назначении правильных цветов на основе ограничений, определенных выше.

Наконец, результаты могут быть найдены с помощью вызова предиката colorGraph/1, такие как:

?- colorGraph(L). 
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, red)] ; 
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, blue)] ; 
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, green)] ; 
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, red)] ; 
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, blue)] ; 
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, green)] ; 
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, red)] ; 
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, blue)] ; 
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, green)] ; 
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, red)] ; 
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, blue)] ; 
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, green)] ; 
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, red)] ; 
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, blue)] ; 
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, green)] ; 
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, red)] ; 
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, blue)] ; 
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, green)] ;