prolog - CLP(FD)、 map 着色

Question

我正在尝试在 prolog CLP 中编写 map 着色程序。这是到目前为止的代码。请任何人帮助我。这里有什么问题。我想在这里替换maplist函数。任何帮助表示赞赏。

:- use_module(library(clpfd)).
regions(Rs):-
        Rs = [R1,R2,R3,R4,R5,R6],

        % neighbouring regions have different 
        dif(R1, R2),
        dif(R1, R3),
        dif(R1, R4),
        dif(R1,R6),
        dif(R2, R3),
        dif(R2, R5),
        dif(R3, R4),
        dif(R3,R5),
        dif(R3, R6),
        dif(R4, R5),
        dif(R4, R6),
        maplist(color, Rs).

color(red).
color(green).
color(blue).
color(yellow).

Answer 1

确实如此:发布的代码已经可以在任何提供dif/2的Prolog系统中工作。

但是，在此类组合任务中使用CLP(FD) 约束具有明显的优势。

让我告诉你我的意思。首先，这是该任务的直接 CLP(FD) 表述:

regions(Rs):-        Rs = [A,B,C,D,E,F],        Rs ins 0..3,        A #\= B, A #\= C, A #\= D,        A #\= F, B #\= C, B #\= E,        C #\= D, C #\= E, C #\= F,        D #\= E, D #\= F.

我只有:

• 更改了变量以提高可读性(R1 → A、R2 → B 等)
• 将 dif/2 替换为 CLP(FD) 约束 (#\=)/2
• 所有原因都基于整数 0..3 而不是原子，因此 CLP(FD) 约束完全适用。请注意，有限域上的任何问题都可以映射到整数，因此 CLP(FD) 约束始终是此类任务的合适选择。

首先，让我们尝试一下最通用的查询，看看原则上答案是什么样的:

?- regions(Rs).Rs = [_640, _646, _652, _658, _664, _670],_640 in 0..3,_640#\=_670,_640#\=_658,_640#\=_652,_640#\=_646,etc.

这看起来很不错。约束求解器以剩余目标进行响应。此外，我们看到我们的关系终止并且实际上是确定性，这很高兴知道。 标记变量将保留终止行为，因此我们不会意外地陷入程序其他部分的循环中。

通过标记变量，我们可以轻松获得具体的解决方案:

?- regions(Rs), label(Rs).Rs = [0, 1, 2, 1, 0, 3] .

这里，每个整数对应一种唯一的颜色。我把让这些解决方案变得更好读作为一项简单的练习。

现在是重点!

或者更确切地说:点!

CLP(FD) 约束提供了一个 dif/2 没有的功能，即约束传播。

在这种情况下，我们最初有以下情况:

这里，每个小点代表一种颜色，我们仍然可以将其用于它所在的区域。首先，约束求解器没有排除任何颜色，因此我们找到所有区域中的每个选项。

如果我们仅将一个区域指定为固定颜色，情况就会发生巨大变化:

?- regions([A,B,C,D,E,F]), F = 0.F = 0,A in 1..3,A#\=D,A#\=C,A#\=B,D in 1..3,D#\=E,C#\=D,E in 0..3,C#\=E,B#\=E,C in 1..3,B#\=C,B in 0..3.

我只添加了单个统一(F = 0)，这导致约束求解器从所有修剪此选项邻近地区:

现在，我只发布一个附加统一:

?- regions([A,B,C,D,E,F]), F = 0, C = 1.C = 1,F = 0,A in 2..3,A#\=D,A#\=B,D in 2..3,D#\=E,E in 0\/2..3,B#\=E,B in 0\/2..3.

这又会自动(即约束求解器为您完成)删除许多其他可能的分配:

只需再执行一项战略任务(我将其作为练习来找出哪一项)，我们就会遇到以下情况:

现在，唯一剩下的选择是如何为尚未分配任何固定颜色的单个剩余区域着色。很容易看出，现在两种允许的颜色都解决了整个任务。

dif/2 也会修剪搜索空间。然而，CLP(FD) 约束对变量的实际域执行这种强大的修剪。这意味着许多值根本不需要尝试。此外，基于这种推理，约束求解器可以更智能地选择标记为next的变量，这在许多情况下进一步提高了性能。