ic_global/occurrences/3 的内部运作

Question

对于 QuasiGroup 补全问题，我实现了两个模型。其中之一是仅基于通道约束的模型（基于 Dotu 的一项研究）。另一个是基于每个值都需要在 row/column 中出现这一事实的模型。这是一个小脚本：

flag :- fail.

:- lib(ic).
:- import occurrences/3 from ic_global.

test :-
    O is 9, % Order of the puzzle
    dim(Variables, [O,O]), Variables :: 1..O,
    6 is Variables[1,1], 8 is Variables[6,2],
    dim(Dual1, [O,O]), Dual1 :: 1..O,
    dim(Dual2, [O,O]), Dual2 :: 1..O,
    (flag ->
        (multifor([I,V], 1, O), param(Variables, O) do
            ic_global:occurrences(V, Variables[I,1..O], 1),
            ic_global:occurrences(V, Variables[1..O,I], 1)
        )
    ;
        (multifor([I,J,K], 1, O), param(Variables, Dual1, Dual2) do
            #=(Variables[I,J], K, Bool),
            #=(Dual1[I,K], J, Bool),
            #=(Dual2[J,K], I, Bool)
        )
    ),
    search(Variables, 0, input_order, indomain, complete, [backtrack(Backtracks)]),
    write(Variables), nl,
    write('Backtracks : '), write(Backtracks), nl.

我在一堆基准测试中试用了它（超过 10 个谜题）。回溯的总数大于 500，但令我震惊的是两个模型中的回溯数相同。集合中每个问题的回溯数也相同。

上面的小脚本也报告了相同数量的回溯。我很好奇为什么会这样。 ic_global:occurrences/ 做了什么使它的行为如此相似（虽然它有点慢）？

Answer 1

occurrences/3 constraint achieves arc-consistency，即它急切地从其参数变量的域中删除所有未出现在约束的任何解决方案中的值。

如果你能为你的整个问题建立弧一致性，那么任何搜索过程都会找到具有绝对最小回溯数的解决方案：第一个解决方案有 0 个回溯，第二个解决方案在 1 个回溯之后，第 N 个在 N-1 个回溯之后.这并不经常实现，因为即使您使用约束的结合来建模问题，这些约束都单独实现弧一致性，这并不意味着您对整个问题具有弧一致性。

这些 全局约束 存在的一个主要原因是它们通常可以实现比许多小约束的结合更高级别的一致性。从这个角度来看，值得注意的是，您的 "dual" 公式似乎与基于出现次数的公式表现相同。

我稍微扩展了你的程序，并研究了一些可以使用可用的全局约束轻松编写的替代公式：

:- lib(ic).
:- lib(ic_global).
:- lib(ic_global_gac).

test(Model) :-
    O is 9, % Order of the puzzle
    dim(Variables, [O,O]), Variables :: 1..O,
    6 is Variables[1,1], 8 is Variables[6,2],

    (Model=occ ->
        (multifor([I,V], 1, O), param(Variables, O) do
            ic_global:occurrences(V, Variables[I,1..O], 1),
            ic_global:occurrences(V, Variables[1..O,I], 1)
        )
    ;Model=gcc ->
        (for(V, 1, O), foreach(gcc(1,1,V),Bounds) do true ),
        (for(I, 1, O), param(Variables, O, Bounds) do
            ic_global_gac:gcc(Bounds, Variables[1..O,I]),
            ic_global_gac:gcc(Bounds, Variables[I,1..O])
        )
    ;Model=gcm ->
        (for(V, 1, O), foreach(gcc(1,1,V),Bounds) do true ),
        (for(_, 1, O), foreach(Bounds,RowColBounds), param(Bounds) do true ),
        ic_global_gac:gcc_matrix(RowColBounds, RowColBounds, Variables)
    ;Model=ad(Strength) ->
        (for(I, 1, O), param(Variables,O,Strength) do
            Strength:alldifferent(Variables[1..O,I]),
            Strength:alldifferent(Variables[I,1..O])
        )
    ;Model=adm ->
        ic_global:alldifferent_matrix(Variables)
    ;Model=dual ->
        dim(Dual1, [O,O]), Dual1 :: 1..O,
        dim(Dual2, [O,O]), Dual2 :: 1..O,
        (multifor([I,J,K], 1, O), param(Variables, Dual1, Dual2) do
            #=(Variables[I,J], K, Bool),
            #=(Dual1[I,K], J, Bool),
            #=(Dual2[J,K], I, Bool)
        )
    ),
    search(Variables, 0, input_order, indomain, complete, [backtrack(Backtracks)]),
    ( foreacharg(Row,Variables) do writeln(Row) ),
    write('Backtracks : '), write(Backtracks), nl.

对于您的小型测试实例，这些行为如下：

Goal                    #backtracks until first solution
test(occ)                3 
test(gcc)                0 
test(gcm)                0 
test(ad(ic))            29 
test(ad(ic_global))      0 
test(ad(ic_global_gac))  0 
test(adm)                0 
test(dual)               3

对于更大的问题实例，您可能会发现更多有趣的差异。但是，adm 和 gcm 模型（其中整个问题用单个约束表示）应该始终表现出最小的回溯行为。

ic_global/occurrences/3 的内部运作

Internal workings of ic_global/occurrences/3

prolog

constraint-programming

eclipse-clp