Внутренняя работа ic_global / вхождения / 3 - PullRequest
Новая
       35

Внутренняя работа ic_global / вхождения / 3

2 голосов
/ 29 апреля 2019

Для задачи завершения 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/, что заставляет его вести себя так же (хотя и немного медленнее)?

1 Ответ

1 голос
/ 30 апреля 2019

Ограничение вхождения / 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 (где вся проблема представлена ​​одним ограничением) всегда должны демонстрировать минимальное поведение при возврате.

...