2

QuasiGroup 補完問題では、2 つのモデルを実装しました。そのうちの 1 つは、チャネリング制約のみに基づくモデルです (Dotu による調査に基づく)。もう 1 つは、すべての値がすべての行/列で発生する必要があるという事実に基づくモデルです。ここに小さなスクリプトがあります：

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/これほど似たような動作をさせるにはどうすればよいでしょうか (少し遅くなりますが)。

4

1 に答える 1

1

発生数/3制約は弧の一貫性を実現します。つまり、その引数変数のドメインから、制約のどの解にも現れないすべての値を積極的に削除します。

問題全体の弧の一貫性を確立できる場合、どの検索手順でもバックトラックの絶対最小数でソリューションを見つけることができます: バックトラックが 0 の最初のソリューション、バックトラックが 1 の後の 2 番目のソリューション、バックトラックが N-1 の後の 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モデル (問題全体が 1 つの制約で表される) は、常に最小限のバックトラッキング動作を示す必要があります。

于 2019-04-30T15:44:02.150 に答える