Теорема о четырех цветах в Прологе (с использованием динамического предиката) - PullRequest
Новая
       35

Теорема о четырех цветах в Прологе (с использованием динамического предиката)

1 голос
/ 13 июня 2010

Я работаю над раскраской карты в соответствии с теоремой о четырех цветах (http://en.wikipedia.org/wiki/Four_color_theorem) с помощью SWI-Prolog. Пока моя программа выглядит так: 

colour(red).
colour(blue).

map_color(A,B,C) :- colour(A),
         colour(B),
         colour(C),
         C \= B,
         C \= A.

(фактическаяprogam будет более сложным, с 4 цветами и большим количеством полей, но я подумал, что начну с простого случая)

Теперь я хочу избежать двойных решений, имеющих одинаковую структуру. Например, для картыс тремя полями решение «красный, красный, синий» будет иметь ту же структуру, что и «синий, синий, красный», только с разными названиями цветов, и я не хочу, чтобы оба они отображались.

Поэтому я подумал, что у меня будет динамическое предикатное решение / 3, и вызову assert (решение (A, B, C)) в конце моего предиката map_color. Затем, для каждого решения, проверьте, существуют ли они уже как решение /Факт 3. Проблема в том, что мне нужно было бы утверждать что-то вроде решения (Color1, Color1, Color2), то есть с переменными, чтобы выполнить проверку объединения. И я не могу придумать, как этого добиться.

Итак, вопрос в том, что являетсялучший способ утверждать найденное решение, а затем выполнить тест объединения, чтобы «красный, красный, синий» объединялся с «синим, синим, красным»?

Ответы [ 2 ]

1 голос
/ 14 июня 2010

Чтобы построить связь между переменными: 

mask_helper(_, _, [], []).
mask_helper(A, B, [A|_], [B|_]):- !.
mask_helper(A, B, [X|Xs], [_|Ys]):-
    A \= X,
    mask_helper(A, B, Xs, Ys).

mask([], []).
mask([X|Xs], [Y|Ys]):-
    mask_helper(X,Y,Xs,Ys),
    mask(Xs, Ys).

и вы можете создать свою маску: 

?- mask([red,red,blue],X).
X = [_G300, _G300, _G306] .

но: 

?- mask([red,red,blue],X), mask([blue,red,red],Y), X=Y.
X = [_G27, _G27, _G27],
Y = [_G27, _G27, _G27].

т.е. нет никакого отношения к Color1 \= Color2, если вы будете использовать assert (без тела правила).

Вы можете рассмотреть что-то вроде порядка назначения цветов (довольно популярный подход): 

colour(red). colour(green). colour(blue).

colour_order(red, red).
colour_order(red, green).
colour_order(red, blue).
colour_order(green, green).
colour_order(green, blue).

colour_code([]).
colour_code([X]):- colour(X).
colour_code([X|[Y|T]]):-
    colour_order(X,Y),
    colour_code([Y|T]).

map_color(A,B,C):-
    colour_code([A,B,C]),
    C \= B, C \= A.

Но опять же, вы никогда не получите результат "красный, синий, красный", если ваши условия будут A \= B, B \= C.

Подумайте о: 

unify([], [], _).
unify([X|Xs], [Y|Ys], M):-
    member((X=Z), M), !,
    Z = Y,
    unify(Xs, Ys, M).

unify([X|Xs], [Y|Ys], M):-
    % X is not assigned yet
    not(member((_=Y),M)), % Y is not used as well
    unify(Xs, Ys, [(X=Y)|M]).

Чем вы можете сравнить: 

?- unify([red,red,blue],[blue,blue,red],[]).
true.

?- unify([red,red,blue],[blue,blue,blue],[]).
false.

?- unify([red,red,blue],[blue,red,red],[]).
false.
0 голосов
/ 13 июня 2010

Я думаю, что самое простое решение - сказать, что A всегда имеет красный цвет (например).

...