首先:

要了解正在发生的事情,以下是 让我们 可视化 搜索:

/n 5 def

340 n div dup scale
-0.9 0.1 translate % leave room for line strokes

/Palatino-Roman 0.8 selectfont

/coords { n exch sub translate } bind def

/num { 3 1 roll gsave coords 0.5 0.2 translate
    5 string cvs dup stringwidth pop -2 div 0 moveto show
    grestore } bind def

/clr { gsave coords 1 setgray 0 0 1 1 4 copy rectfill
     0 setgray 0.02 setlinewidth rectstroke grestore} bind def

1 1 n { 1 1 n { 1 index clr } for pop } for

• clr 清理广场
• num 在正方形上显示数字。

tour.ps 然后调用PostScript解释器 鬼书

gs -r72 -g350x350 tour.ps

然后输入以下说明:

1 2 3 num
1 2 clr
2 3 4 num

PostScript是一种用于可视化搜索过程的优秀编程语言,我也建议您查看 postscript 了解更多信息。

constrain_entries([], _Square, _X, _Y).
constrain_entries([E|Es], Square, X, Y) :-
    freeze(E, postscript(X, Y, E)),
    constrain_entry(E, Square, X, Y),
    X1 #= X + 1,
    constrain_entries(Es, Square, X1, Y).

postscript(X, Y, N) :- format("~w ~w ~w num\n", [X,Y,N]).
postscript(X, Y, _) :- format("~w ~w clr\n", [X,Y]), false.

我也自由地改变了 (is)/2 到 (#=)/2 使程序更加通用。

假设您在中保存了PostScript定义 还有你的Prolog程序 tour.pl ,以下调用SWI Prolog和Ghostscript说明了这种情况:

swipl -g "number_puzzle_(_, Vs), label(Vs)" tour.pl | gs -g350x350 -r72 tour.ps -dNOPROMPT

所有高亮显示的方块都不是有效的移动!

无法完成 找到解决办法!这是 坏消息 ^8. 152587890625 部分解决方案,然后仅从板中的第二个位置重新开始。

在约束文献中,这种回溯称为 痛击 由于同样的原因 .

这怎么可能?您的模型似乎是正确的,可以用来检测解决方案。太好了!然而,一个好的约束公式不仅能识别解决方案,而且还能 部分赋值 不能 reifiedconstraints 您正在使用的。特别是,考虑下面的查询:

?- (X + 1 #= 3) #<==> B, X #\= 2.

直觉上,我们期望 B = 0 . 但事实并非如此!相反,我们得到:

X in inf..1\/3..sup,
X+1#=_3840,
_3840#=3#B,
B in 0..1.

因此,解算器不会大力传播具体化的等式。 也许应该如此! 只够 从Prolog中,实践者将知道是否应该更改约束求解器的这一区域,可能需要以一点速度换取更强的传播。这种反馈的高度相关性是我建议在您有机会时,即每次进行推理时,使用CLP(FD)约束的原因之一 .

解决核心问题

我们应该消除回溯的原因 核心 . 要删减搜索,我们必须尽早识别不一致(部分)的分配。

直觉上,我们正在寻找一个 联网旅游 ,并希望在明确无法按预期方式继续旅行后尽快返回。

要实现我们的目标,我们至少有两种选择:

1. 更改分配策略以考虑连通性
2. 对问题进行建模时,应更充分地考虑连通性。

备选案文1:分配战略

分离 搜索中的任务描述。当使用CLP(FD)约束时,我们通常通过 label/1 或 labeling/2 以我们想要的任何方式 . 如果我们像您一样遵循将“constraintposting”部分放入其自己的谓词(称为 核心关系 .

例如,这里有一个 确保巡演始终保持连接的分配策略:

allocation(Vs) :-
        length(Vs, N),
        numlist(1, N, Ns),
        maplist(member_(Vs), Ns).

member_(Es, E) :- member(E, Es).

通过此策略,我们可以从头开始为5×5实例提供解决方案:

?- number_puzzle_(Square, Vars), time(allocation(Vars)).
% 5,030,522 inferences, 0.907 CPU in 0.913 seconds (99% CPU, 5549133 Lips)
Square = square(row(1, 8, 5, 2, 11), ...),
Vars = [1, 8, 5, 2, 11, 16, 21, 24, 15|...] 

剩余域元素 正方形的一部分。我把尝试这样的改进当作一种挑战。

从标准标签策略来看 min 在这种情况下,标签选项实际上与此策略非常相似,而且它也为5×5的情况找到了解决方案:

?- number_puzzle_(Square, Vars), time(labeling([min], Vars)).
% 22,461,798 inferences, 4.142 CPU in 4.174 seconds (99% CPU, 5422765 Lips)
Square = square(row(1, 8, 5, 2, 11), ...),
Vars = [1, 8, 5, 2, 11, 16, 21, 24, 15|...] .

然而,即使是合适的分配策略也不能完全补偿弱约束传播。对于10×10实例,在使用 闵 选项:

请注意,我们还必须调整 n

理想情况下,我们应该以这样一种方式制定任务,即我们从强大的传播中获益,然后 也 使用良好的分配策略。

备选方案2:改建

一个好的CLP配方可以推广 尽可能强烈地 (在可接受的时间内)。因此,我们应该努力使用约束,使解算器能够更容易地对任务的最重要需求进行推理。在这个具体的例子中,这意味着我们应该尝试为当前表示为具体化约束的析取找到一个更合适的公式,如上所示,它不允许太多的传播。理论上,约束求解器可以自动识别这些模式。然而,这对于许多用例来说是不切实际的,因此我们有时必须手动尝试几种有前途的配方。不过,在这种情况下也是如此:有了应用程序程序员的充分反馈,这种情况更有可能得到改进和改进!

我现在使用CLP(FD)约束 circuit/1 明确表示我们正在寻找 在特定的图形中。图形表示为整数变量列表,其中每个元素表示其位置 在列表中。

?- Vs = [_,_,_], circuit(Vs), label(Vs).
Vs = [2, 3, 1] ;
Vs = [3, 1, 2].

电路/1 近距离 . 这意味着,如果我们找到了这样一个解决方案,那么我们可以通过有效的移动从发现的巡更中的最后一个方块重新开始:

n_tour(N, Vs) :-
        L #= N*N,
        length(Vs, L),
        successors(Vs, N, 1),
        circuit(Vs).

successors([], _, _).
successors([V|Vs], N, K0) :-
        findall(Num, n_k_next(N, K0, Num), [Next|Nexts]),
        foldl(num_to_dom, Nexts, Next, Dom),
        V in Dom,
        K1 #= K0 + 1,
        successors(Vs, N, K1).

num_to_dom(N, D0, D0\/N).

n_x_y_k(N, X, Y, K) :- [X,Y] ins 1..N, K #= N*(Y-1) + X.

n_k_next(N, K, Next) :-
        n_x_y_k(N, X0, Y0, K),
        (   [DX,DY] ins -2 \/ 2
        ;   [DX,DY] ins -3 \/ 0 \/ 3,
            abs(DX) + abs(DY) #= 3
        ),
        [X,Y] ins 1..N,
        X #= X0 + DX,
        Y #= Y0 + DY,
        n_x_y_k(N, X, Y, Next),
        label([DX,DY]).

元素 ,减少了限制的数量,完全消除了具体化的需要。最重要的是,搜索过程中的每个点都会自动考虑并强制实现预期的连接。谓词 n_x_y_k/4 (X,Y) 列出索引的坐标。您可以通过更改,轻松地将此程序调整为其他任务(例如,骑士之旅) n_k_next/3 . 我把这个概括留给我自己 打开 旅游是一项挑战。

下面是让我们 打印 更具可读性的解决方案:

:- set_prolog_flag(double_quotes, chars).

print_tour(Vs) :-
        length(Vs, L),
        L #= N*N, N #> 0,
        length(Ts, N),
        tour_enumeration(Vs, N, Es),
        phrase(format_string(Ts, 0, 4), Fs),
        maplist(format(Fs), Es).

format_(Fs, Args, Xs0, Xs) :- format(chars(Xs0,Xs), Fs, Args).

format_string([], _, _) --> "\n".
format_string([_|Rest], N0, I) -->
        { N #= N0 + I },
        "~t~w~", call(format_("~w|", [N])),
        format_string(Rest, N, I).

tour_enumeration(Vs, N, Es) :-
        length(Es, N),
        maplist(same_length(Es), Es),
        append(Es, Ls),
        foldl(vs_enumeration(Vs, Ls), Vs, 1-1, _).

vs_enumeration(Vs, Ls, _, V0-E0, V-E) :-
        E #= E0 + 1,
        nth1(V0, Ls, E0),
        nth1(V0, Vs, V).

ff 搜索策略通常是一个很好的策略。事实上,它可以让我们在几秒钟内在商品机器上解决整个任务,即原始的10×10实例:

?- n_tour(10, Vs),
   time(labeling([ff], Vs)),
   print_tour(Vs).
% 5,642,756 inferences, 0.988 CPU in 0.996 seconds (99% CPU, 5710827 Lips)
   1  96  15   2  97  14  80  98  13  79
  93  29  68  94  30  27  34  31  26  35
  16   3 100  17   4  99  12   9  81  45
  69  95  92  28  67  32  25  36  33  78
  84  18   5  83  19  10  82  46  11   8
  91  23  70  63  24  37  66  49  38  44
  72  88  20  73   6  47  76   7  41  77
  85  62  53  86  61  64  39  58  65  50
  90  22  71  89  21  74  42  48  75  43
  54  87  60  55  52  59  56  51  40  57
Vs = [4, 5, 21, 22, 8, 3, 29, 26, 6|...] 

还要注意的是,这决不是任务的唯一有前途的Prolog甚至CLP(FD)公式,我把思考其他公式作为一个挑战。