Как пометить график

Question

У меня возник вопрос, описанный ниже:

Написать пролог программу, которая окрашивает график. Цвета определяются предикатом цвета/1 и графиком с помощью края предложения/2. Вы должны написать окраску предикатов (Coloring), которая находит раскраску узлов node_1, ..., node_n графика. Раскраска - это список [node_1/color_1, ..., node_n/color_m], где color_1, ..., color_m - это цвета, которые удовлетворяют тому, что узлы каждого ребра имеют разные цвета.

Давайте посмотрим на пример. Пусть цвет и край являются предикатами ниже.

% 2 colors 
color(blue). 
color(red). 
% the edges 
edge(1,2). 
edge(1,3). 
edge(2,4). 
edge(5,2). 

Для этой информации окраска (C) выполнена. Одним из решений является

C = [ 1/blue, 2/red, 3/red, 4/blue, 5/blue]. 

Напишите цвет предиката ниже.

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

Answer 1

Вам нужно знать имена узлов. Один из способов сделать это является использование setof/3:

setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN) 

X^Y означает, что X и Y должны быть использованы в поиске, но не для результата.

Теперь мы создали список ассоциаций Node/Color с использованием предиката set_color (List_of_nodes, List_of_association).

Пустой список узлов дает пустой список ассоциаций!

set_color([], []) 

Теперь процесс:

% we work with the current element of the list of nodes 
set_color([H | T], [H/C | TC]) :- 
    % we create the association for the rest of the list 
    set_color(T, TC), 
    % we choose the color 
    color(C), 
    % we check that two adjacent nodes of different colors 
    forall(member(Node/Color, TC), 
      ( (edge(Node, H) -> Color \= C; true), 
      (edge(H, Node) -> Color \= C; true))). 

Таким образом, вы получите:

% 2 colors 
color(blue). 
color(red). 
% the edges 
edge(1,2). 
edge(1,3). 
edge(2,4). 
edge(5,2). 

coloring(L) :- 
    setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN), 
    set_color(LN, L). 


set_color([], []). 

set_color([H | T], [H/C | TC]) :- 
    set_color(T, TC), 
    color(C), 
    forall(member(Node/Color, TC), 
      ( (edge(Node, H) -> Color \= C; true), 
      (edge(H, Node) -> Color \= C; true))). 

Я забыл сказать, что Пролог с BackTrack делает работу!