集成电路全局/事件/3的内部工作

Question

对于QuasiGroup完成问题，我实现了两个模型。其中之一是基于渠道约束的模型(基于Dotu的一项研究)。另一个是基于这样一个事实的模型，即每个值都需要出现在任何行/列中。下面是一个小脚本：

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

事件/3约束实现了弧一致性，即它急切地从其参数变量的域中移除约束的任何解决方案中没有出现的所有值。

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

这些全局约束存在的一个主要原因是，它们通常能够达到比许多小约束相结合的更高的一致性水平。在这种情况下，值得注意的是，你的“双重”配方的行为似乎与事件为基础的一个。

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

:- 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模型(其中整个问题用单个约束表示)应该始终表现出最小的回溯行为。