5

Prolog で単純なグラフの色付けアルゴリズムを作成しようとしていますが、言語を理解するのに少し苦労しています。やりたいことはわかっています。頂点に行き、それに接続されている他のすべての頂点を見つけ、頂点の色を確認し、それに応じて他の頂点を異なる色で色付けします。これをPrologに翻訳するのに苦労しています。それが C の方言や Java だったら、私にとっては簡単なことですが、これは私にぴったりです。

これは私がこれまでに持っているものです:

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の下のより多くのコード）

4

2 に答える 2

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 から他の頂点へのエッジがない場合は、可能なすべての色を試してみることを示しています。2 番目の句は、V から V1 へのエッジがある場合、頂点 V は色 C になり、頂点 V1 は色 C1 になることを示しています。ここで、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).ことで、グラフの頂点に可能なすべての色の割り当てを取得できます。

誰かが問題を見つけた場合は、上記の解決策に存在するとほぼ確信しています。お知らせください:)

スピロス

于 2012-05-23T08:10:39.940 に答える