Избегайте переполнения findall с проблемой n-дробей - PullRequest
Новая
       39

Избегайте переполнения findall с проблемой n-дробей

0 голосов
/ 16 февраля 2019

Я пытаюсь распечатать все решения проблемы n-фракций для n = 4: 

:- lib(ic).

fractions(Digits) :-
   Digits = [A,B,C,D,E,F,G,H,I,J,K,L],

   Digits #:: 1..9,

   ic:alldifferent(Digits),

   X #= 10*B+C,
   Y #= 10*E+F,
   Z #= 10*H+I,
   V #= 10*K+L,

   A*Y*Z*V + D*X*Z*V + G*X*Y*V + J*X*Y*Z #= X*Y*Z*V,

   A*Y #=< D*X,
   D*Z #=< G*Y,
   G*V #=< J*Z,

   search(Digits,0,input_order,indomain,complete,[]).

Когда я запускаю запрос: 

?- findall(Digits,fractions(Digits),List).

Я получаю следующее исключение: 

*** Overflow of the local/control stack!
You can use the "-l kBytes" (LOCALSIZE) option to have a larger stack.
Peak sizes were: local stack 105728 kbytes, control stack 25344 kbytes

Я думаю, есть ли способ выполнить цикл внутри программы и напечатать одно решение каждый раз, или я не могу этого сделать, потому что у проблемы слишком много решений

Ответы [ 3 ]

0 голосов
/ 17 февраля 2019

Многие реализации предлагают global_cardinality ограничения, которые я использую в этом примере.Далее я использую SICStus Prolog 4.5.0: 

:- use_module(library(clpfd)).

fractions(Digits) :-
   Digits = [A,B,C,D,E,F,G,H,I,J,K,L],
   domain(Digits, 1, 9),
   global_cardinality(Digits, [1-N1,2-N2,3-N3,4-N4,5-N5,6-N6,7-N7,8-N8,9-N9]),
   domain([N1,N2,N3,N4,N5,N6,N7,N8,N9], 1, 2),
   X #= 10*B+C,
   Y #= 10*E+F,
   Z #= 10*H+I,
   V #= 10*K+L,
   Z*V #= ZV,
   X*Y #= XY,
   A*Y*ZV + D*X*ZV + G*XY*V + J*XY*Z #= XY*ZV,
   X #=< Y, X #= Y #=> A #=< D,                   % break some symmetries
   Y #=< Z, Y #= Z #=> D #=< G,
   Z #=< V, Z #= V #=> G #=< J.

Пример использования: 

| ?- n_fractions(4,Zs), labeling([enum],Zs).
Zs = [2,1,2,9,1,8,7,3,5,6,4,5] ? ;
Zs = [2,1,3,7,1,8,9,2,6,5,4,5] ? ;
Zs = [2,1,3,7,1,8,9,2,6,6,5,4] ? ;
...
no

Использование для сбора всех решений работает нормальнотоже: 

?- findall(Zs,(n _fractions(4,Zs), labeling([enum],Zs)), Zss),
   length(Zss, N_sols).
Zss = [[2,1,2,9,1,8,7,3,5|...],
       [2,1,3,7,1,8,9,2,6|...],
       [2,1,3,7,1,8,9,2|...],
       [2,1,3,8,1,5,7|...],
       [2,1,3,8,1,6|...],
       [2,1,3,9,1|...],
       [2,1,3,9|...],
       [2,1,4|...],
       [2,1|...],
       [...|...]|...],
N_sols = 1384 ? ;
no
0 голосов
/ 21 февраля 2019

Как уже указывалось, ваш код завершается ошибкой, поскольку ограничение alldifferent(Digits) слишком ограничительно.Цифры должны появляться от 1 до 2 раз.В вы можете использовать такие ограничения, как atleast / 3 , максимум / 3 , вхождений / 3 или gcc / 2 , чтобы выразить это.

Немного не по теме: поскольку вы используете ECLiPSe ic-solver (который может обрабатывать непрерывные домены), вы можете использовать модель гораздоближе к исходной спецификации , без большого количества умножений: 

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

fractions4(Digits) :-

    Digits = [A,B,C,D,E,F,G,H,I,J,K,L],
    Digits #:: 1..9,

    A/(10*B+C) + D/(10*E+F) + G/(10*H+I) + J/(10*K+L) $= 1,

    ( for(I,1,9), param(Digits) do
        occurrences(I, Digits, NOcc), NOcc #:: 1..2
    ),

    lex_le([A,B,C], [D,E,F]),       % lex-ordering to eliminate symmetry
    lex_le([D,E,F], [G,H,I]),
    lex_le([G,H,I], [J,K,L]),

    labeling(Digits).

Помимо основного ограничения равенства (используется $= вместо #=, потому что мы не хотимздесь требуется целостность), я использовал вхождений / 3 для ограничений вхождений и лексикографического порядка ограничений в качестве более стандартного способа устранения симметрии.Результат: 

?- findall(Ds, fractions4(Ds), Dss), length(Dss, NSol).
Dss = [[1, 2, 4, 3, 5, 6, 8, 1, 4, 9, 2, 7], [1, 2, 6, 5, 3, 9, 7, 1, 4, 8, 2, 4], [1, 2, 6, 5, 3, 9, 7, 8, 4, 9, 1, 2], [1, 2, 6, 7, 3, 9, 8, 1, 3, 9, 5, 4], [1, 2, 6, 8, 7, 8, 9, 1, 3, 9, 5, 4], [1, 3, 4, 5, 4, 6, 8, 1, 7, 9, 2, 3], [1, 3, 4, 7, 5, 6, 8, 1, 7, 9, 2, 4], [1, 3, 4, 8, 1, 7, 8, 5, 2, 9, 2, ...], [1, 3, 5, 6, 2, 8, 7, 1, 4, 9, ...], [1, 3, 6, 5, 2, 4, 7, 1, 8, ...], [1, 3, 6, 5, 3, 6, 7, 8, ...], [1, 3, 6, 5, 4, 5, 8, ...], [1, 3, 6, 5, 6, 3, ...], [1, 3, 6, 6, 5, ...], [1, 3, 6, 7, ...], [1, 3, 9, ...], [1, 3, ...], [1, ...], [...], ...]
NSol = 1384
Yes (82.66s cpu)

Дополнительным преимуществом этой модели является то, что ее можно довольно легко превратить в универсальную модель для произвольного N .

0 голосов
/ 17 февраля 2019

Просто ваш предикат не работает.Если вы удалите все ограничения, кроме alldifferent/1 и search/6 (просто, чтобы понять проблему) и вызовете ?- fractions(Digits)., вы получите false, потому что невозможно иметь список из 12 элементов (Digits = [A,B,C,D,E,F,G,H,I,J,K,L]) с доменом для каждогоэлемент Digits #:: 1..9 и ограничить все эти элементы, чтобы они были разными (ic:alldifferent(Digits)).9 вариантов для 12 элементов: неразрешимые.Если вы расширяете домен до 12 (Digits #:: 1..12), вы получаете решение: 

?- fractions(Digits).
Digits = [2, 3, 4, 9, 7, 10, 12, 8, 5, 11, 1, 6]
Yes (94.00s cpu, solution 1, maybe more)

Тогда вы можете применить findall/3 и посмотреть другие решения ...

...