使用 3 种颜色和列表解决图形着色问题 - Prolog

Question

我需要用 Prolog 解决图形着色问题。讲的是 Map of Latin America with 3 colors, 问题描述是用 Coloring 的第 i 个 member 给第 i 个 member of countries 上色，我不是很清楚怎么搭配。

这是目前的程序，

adjacent(brazil, suriname).
adjacent(brazil, guyana).
adjacent(brazil, venezuela).
adjacent(brazil, colombia).
adjacent(brazil, peru).
adjacent(brazil, bolivia).
adjacent(brazil, paraguay).
adjacent(brazil, argentina).
adjacent(brazil, uruguay).
adjacent(frenchguiana, suriname).
adjacent(suriname, guyana).
adjacent(guyana, venezuela).
adjacent(venezuela, colombia).
adjacent(colombia, ecuador).
adjacent(colombia, peru).
adjacent(ecuador, peru).
adjacent(peru, bolivia).
adjacent(bolivia, chile).
adjacent(bolivia, paraguay).
adjacent(chile, argentina).
adjacent(paraguay, argentina).
adjacent(argentina, uruguay).
adjacent(chile, peru).
adjacent(argentina, bolivia).

coloring([red,yellow,green]).

neighbor(X,Y) :- adjacent(X, Y). 
neighbor(X,Y) :- adjacent(Y, X).

conflict(A,Ca,B,Cb) :-
   adjacent(A,B),
   Ca \= Cb.

solve(?, ?) :-

这应该是查询。 solve([brazil,colombia,argentina,peru,venezuela,chile,ecuador,bolivia,paraguay,uruguay,guyana,suriname,frenchguiana],Coloring)

我看过 google 上的示例算法，但似乎与我应该做的方式不同。

Answer 1

我将概述一种解决方案，无需为您编写代码并剥夺您的沉浸式学习体验。 :)

您的 solve 谓词只需要一个参数，即您的国家/地区可以着色的一组颜色。这就引出了一个问题：它的结构是什么样的？它是国家/地区颜色对列表似乎合乎逻辑。在 Prolog 中做对的一个好方法是使用连字符仿函数，例如、uruguay-red.

solve 会这样做：

收集国家列表 - 您可以使用 setof
将颜色列表绑定到一个变量（调用coloring）
调用将构建国家/地区颜色列表的谓词（也许称之为 countries_colors）。它将需要国家列表、颜色选择列表和一个空列表作为确定的国家/地区颜色对的起始列表

countries_colors 会递归地查看国家列表中的每个国家，从颜色列表中选择一种颜色，并检查所选颜色的国家是否与目前确定的任何国家/颜色对冲突（来自确定的国家颜色对列表）。它将：

选择颜色
检查当前国家和颜色是否与当前国家颜色列表中的国家颜色对冲突
如果失败，第 2 步回溯尝试不同的颜色
在国家/地区颜色列表中包含新的国家/地区/颜色对，并根据该列表递归检查其他国家/地区的不同颜色。

如果你正确地实现了这一点，你当前的数据库将没有解决方案。这是因为您的邻接事实在两个维度上都不是真的。如果您只是从数据库中删除，例如 adjacent(argentina, bolivia).，您可以获得解决方案。

使用 3 种颜色和列表解决图形着色问题 - Prolog

Solving the Graph Coloring with 3 color and lists - Prolog

prolog

graph-coloring