Prolog 中的地图着色

2025年3月17日 | 阅读 3 分钟

在数学中，著名的难题是为相邻的平面区域着色。无论我们选择什么颜色，两个相邻的区域都不能使用相同的颜色。共享边界线的两个区域被认为是彼此相邻的。在下图中，该区域由一些数字名称显示。

上面的数字名称显示了哪些区域是相邻的。现在我们将考虑以下图表

在上图中，原始边界被擦除。现在，我们在两个区域名称之间有一条弧。该弧线表明这两个区域在原始绘图中是相邻的。所有原始的邻接信息都由邻接图传达。使用以下事实或单位子句，邻接信息可以在 Prolog 中表示。

adjacent(1,2).         adjacent(2,1). 
adjacent(1,3).         adjacent(3,1). 
adjacent(1,4).         adjacent(4,1). 
adjacent(1,5).         adjacent(5,1). 
adjacent(2,3).         adjacent(3,2). 
adjacent(2,4).         adjacent(4,2). 
adjacent(3,4).         adjacent(4,3). 
adjacent(4,5).         adjacent(5,4). 

在 Prolog 中，如果加载这些子句，我们将获得以下某些目标的行为。

?- adjacent(2, 3)
yes
?- adjacent(5, 3)
no
?- adjacent(3, 1)
no
?- adjacent(3,2)
no

在 Prolog 中，可以为区域声明着色。它也将使用单位子句。

color(1, orange, x). 	color(1, orange, y).
color(2, pink, x). 	color(2, pink, y).
color(3, purple, x).	color(3, purple, y).
color(4, red, x).	color(4, pink, y).
color(5, pink, x).	color(5, purple, y).

这里编码了“x”和“y”着色。在 Prolog 中，两个相邻区域具有相同的颜色显示了冲突着色的定义。以下示例显示了 Prolog 规则或子句以达到该效果。

conflict(R1, R2, Coloring) :-
adjacent(R1, R2),
color(R1, Color, Coloring),
color(R2, Color, Coloring).

Prolog 区分了“冲突”的两个定义。 1^st 定义定义了 1 个逻辑参数。 2^nd 定义定义了 3 个参数。现在我们有，

?- conflict(R1, R2, y)
R1=2	R2=4	
?- conflict(R1, R2, y), color(R1, Z, y).
R1= 2	R2=4	Z = blue

上面的例子表明区域 2 和区域 4 都是相邻的。它还表明区域 2 和 4 都是蓝色的。 Prolog 程序的后果由实例 conflict(2, 4, y) 表示。演示这种结果的一种方法是绘制一个程序子句树。在该树中，树的根包含结果，为了分支树，它使用程序的子句，最后，它将生成一个有限树，该树具有所有真叶。使用子句的完全实例，我们可以构造子句树，如下所示

在上面的树中，最左下方的分支对应于单位子句。

adjacent(2,4)

在 Prolog 中，此分支等效于子句
adjacent(2,4) :- true

在 Prolog 中，程序的结果不会显示为“conflict(1, 3, b)”，因为我们可以使用包含所有“true”叶子的 P 的实例来构造一个有限子句树。同样，程序的结果显示为“conflict(a)”。为了计算所有可能的着色，我们将在 Prolog 中开发一个程序。著名的四色猜想指出，为了对树的区域进行着色，我们不需要超过四种颜色。以下示例表明我们需要至少四种颜色