时间戳

首页 > 解决方案 > Solving the Graph Coloring with 3 color and lists - Prolog

prolog - Solving the Graph Coloring with 3 color and lists - Prolog

问题描述

I need to solve graph-coloring problem with Prolog. It's about Map of Latin America with 3 colors, and the problem description says the i-th member of Coloring should be used to Color the i-th member of countries, which is not very clear to me how to match them.

Here's the program so far,

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(?, ?) :-

and this should the query. solve([brazil,colombia,argentina,peru,venezuela,chile,ecuador,bolivia,paraguay,uruguay,guyana,suriname,frenchguiana],Coloring)

I've seen the example algorithms on google, but seems different from the way i should do it.

标签： prologgraph-coloring

解决方案

我将概述一种解决方案的方法，而无需为您编写代码并剥夺您身临其境的学习体验。:)

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

solve会这样做：

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

countries_colors将递归查看国家/地区列表中的每个国家/地区，从颜色列表中选择一种颜色，并检查该所选颜色的国家/地区是否与迄今为止确定的任何国家/地区颜色对（从已确定的国家/地区颜色对列表中）冲突。它会：

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

如果您正确实施此操作，您当前的数据库将没有解决方案。这是因为您的邻接事实在二维上不可能是真实的。adjacent(argentina, bolivia).例如，如果您只是从数据库中删除，您可以获得解决方案。

推荐阅读