Застревание в бесконечном цикле в прологе

Я хочу, чтобы моя программа находила мне все подмножества размера K целых чисел 1,2, ..., N.Застревание в бесконечном цикле в прологе

Для этого я написал следующие подводные лодки (N, X, Y) означает, что Х представляет собой подмножество размера N множества Y. Я определил следующее:

subs(0,[],X). 
subs(N,[A|R1],[A|R2]):-N>0, N1 is N-1, subs(N1,R1,R2). 
subs(N,[A|R1],[B|R2]):-subs(N,[A|R1],R2). 
subs(N,[A|R1],[B|R2]):-subs(N,R1,[B|R2]).

И затем, как я проверил sub (2, X, [1,2,3,4]).

У меня был первый ответ [1,2], но он не дал второго ответа, поскольку он застрял в бесконечном цикле. Я попытался проследить его, и кажется, что после нахождения первого ответа он делает:

Redo: (8) subs(0, _G613, [3, 4]) ? creep 
^ Call: (9) 0>0 ? creep 
^ Fail: (9) 0>0 ? creep 
    Redo: (8) subs(0, _G613, [3, 4]) ? creep 
    Call: (9) subs(0, [_G618|_G619], [4]) ? creep 
^ Call: (10) 0>0 ? creep 
^ Fail: (10) 0>0 ? creep 
    Redo: (9) subs(0, [_G618|_G619], [4]) ? creep 
    Call: (10) subs(0, [_G618|_G619], []) ? creep 
    Fail: (10) subs(0, [_G618|_G619], []) ? creep 
    Redo: (9) subs(0, [_G618|_G619], [4]) ? creep 
    Call: (10) subs(0, _G619, [4]) ? creep 
    Exit: (10) subs(0, [], [4]) ? creep 
    Exit: (9) subs(0, [_G618], [4]) ? creep 
    Exit: (8) subs(0, [_G618], [3, 4]) ? creep 
    Exit: (7) subs(1, [2, _G618], [2, 3, 4]) ?

Так я вижу, что я застрял с subs(0, _G619, [4]). Кто-то имеет представление о том, как преодолеть эту проблему?

Thanks

источник

2015-03-17 TheEmeritus

У вашего 4-го предложения есть недостаток. Глава второго аргумента (подмножество) имеет переменную 'A', которая является одноточечной. В этом разделе в основном говорится: '' [A | R1] 'является подмножеством значений' N' из '[B | R2]', если 'R1' является подмножеством значений' N' из '[B | R2]', для любой переменной 'A' *. Это не будет правильным правилом для подмножества. Неясно, какова цель этого правила. – lurker

Ваш 4-й пункт имеет недостатки. Глава второго аргумента (подмножество) имеет переменную A, которая является одноэлементной. Предложение в основном читает, [A|R1] является подмножеством N значений из [B|R2] если R1 является подмножеством N значений из [B|R2], для любой переменной A. Это не было бы правильным правилом для подмножества и приводило бы к бесконечному циклу, поскольку в конечном итоге оно не сводится к основному случаю. Неясно, какова цель этого правила. Вероятно, вы можете просто удалить его, поскольку первые 3 адекватно определяют подмножество.

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

Это плюс немного переменная очистки делает ваш предикат в:

subs(0, [], _). 
subs(N, [A|R1], [A|R2]) :- N > 0, N1 is N-1, subs(N1, R1, R2). 
subs(N, R1, [_|R2]) :- N > 0, subs(N, R1, R2).

источник

2015-03-17 14:32:54 lurker

Спасибо! Но теперь, когда это работает, я заметил что-то: если я попрошу subs (K, [1,2], [1,2,3]), я получаю следующую ошибку: ОШИБКА: Необработанное исключение:>/2: Аргументы: не достаточный экземпляр , но если я попрошу субподрядки (2, X, [1,2,3]), все работает нормально (я получаю X = [1,2], X = [1,3] и X = [ 2,3]). Кажется, странная ошибка? – TheEmeritus

@ TheEmeritus, потому что числовые реляционные операторы, такие как '>/2', требуют, чтобы все аргументы были полностью созданы. Для этого не может быть никаких переменных. Если вы хотите, чтобы ваш предикат 'subs' был полностью реляционным и допустил, что первый аргумент является переменной, его нужно будет немного переработать, чтобы обработать этот случай. В Prolog часто бывает легко сделать предикатную работу для подмножества аргументов с переменными аргументами, но сделать ее полностью реляционной может быть серьезной проблемой. – lurker

@ ответ Lurker находится на семантическом уровне предиката. Хорошо. Но есть еще более простой способ определения проблемы - просто используя следующие failure slice.

 
subs(0,[],_X) :- false. 
subs(N,[A|R1],[A|R2]):- false, N>0, N1 is N-1, subs(N1,R1,R2). 
subs(N,[A|R1],[_B|R2]):- false, subs(N,[A|R1],R2). 
subs(N,[_A|R1],[B|R2]):- subs(N,R1,[B|R2]), false.

Уже этот фрагмент не прекращает для subs(2,X,[1,2,3,4]). Однако он должен это сделать. Таким образом, в оставшейся видимой части есть проблема, с которой вам нужно обратиться.

Существует единственный критерий, чтобы найти этот фрагмент отказа: (универсальное) неисполнение запроса. Для определения этого фрагмента дополнительная информация о фактическом предполагаемом значении не используется.

источник

2015-03-17 16:55:34 false

Застревание в бесконечном цикле в прологе

ответ

Смежные вопросы