Эта программа сортировки на прологе переполняет стек просто из-за своей сложности или потому, что она неверна?

В предыдущий пост, в конце концов я понял, как написать программу gprolog, которая проверяет, является ли один список перестановкой другого. Насколько я знаю, это работает.

Теперь я создаю предикат mysort, который объединяет предикат перестановки с этим (насколько я могу судить, тоже работает):

sorted([]).   
sorted([L]) :- !.  
sorted([L|[T|TT]]) :- L @=< T, sorted([T|TT]).

Поскольку мой первоначальный предикат perm был разработан таким образом, чтобы заканчиваться !, как только он достигает ответа, я внес некоторые изменения, чтобы позволить mysort проверять возможные варианты. Вот mysort, его особый backtrack_perm и перекрытие со старым perm (которое я просто изменил как небольшое изменение на backtrack_perm):

perm([],[]).
perm([LH|LT],R) :-
   backtrack_perm([LH|LT],R),
   !.

perm_recurse([],X). 
perm_recurse([LH|LT],R) :-
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X,Y),
   !. 

mysort(L,M) :-
   backtrack_perm(L,M),
   sorted(M),
   !.  

backtrack_perm([],[]).
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B),
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).

Хотя его компоненты, как уже упоминалось, работают нормально, mysort вызывает переполнение стека для некоторых входных данных, таких как mysort([5,3,2],X). В уже отсортированном списке, таком как mysort([2,3,5],X), или даже частичном, таком как mysort([3,2,5],X), трассировка может быть длинной, но она дает ответ. Из-за этого - и поскольку меньший полностью обратный список, такой как [2,1], работает нормально - я думаю, проблема в том, что сам процесс занимает слишком много места/времени со всеми этими перестановками.

Не углубляясь слишком в более длинные трассировки, можно ли с уверенностью предположить, что дело обстоит именно так? Или Пролог/компьютер должен справиться с этим без проблем, то есть мне нужно переосмыслить алгоритмы?


prolog failure-slice
person norman    schedule 05.07.2013    source источник
comment
Вы понимаете, что делает length(R,B), когда R и B изначально не связаны?   -  person Fred Foo    schedule 06.07.2013
comment
По общему признанию, нет... Я думал об исходном perm, для которого R будет известно и связано, а B будет "вычислено" и затем использовано в сравнении с A.   -  person norman    schedule 06.07.2013
comment
Но я полагаю, что он найдет список R и длину B, которые его удовлетворят... что приведет к серьезным проблемам с точки зрения возможностей :/?   -  person norman    schedule 06.07.2013

Ответы (1)


arrow_upward
5
arrow_downward

@Will Ness уже дал вам точное определение для perm/2. Но давайте посмотрим на вашу программу. На самом деле у вас очень странное поведение: иногда вроде работает, а иногда нет. Как мы можем сузить это? Отслеживание не представляется возможным, как вы испытали на себе.

Вот особая техника отладки, называемая нарезкой. Я изменю вашу программу, чтобы увидеть, что происходит, вставив цели false. Полученная программа называется неудачным фрагментом. И я буду использовать запрос:

?- mysort([1],[2|_]).
Fatal Error: global stack overflow

Ясно, что список с одним элементом 1 не может соответствовать списку, начинающемуся с 2. Так что в идеале это должно потерпеть неудачу. И это не может быть этот комплекс. Может это?

@larsmans уже дал вам подсказку, но я попробую сам. Я добавлю в вашу программу следующие цели false. Таким образом, определенные части никогда не будут вызываться, они перечеркнуты. А некоторые предикаты вообще не будут вызываться, поэтому я их больше показывать не буду:

?- mysort([1],[2|_]).

mysort(L,M) :-
   backtrack_perm(L,M), false,
   sorted(M),
   !.  

backtrack_perm([],[]) :- false.
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B), false,
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).

Этот фрагмент отказа в некотором смысле так же плох, как и ваша программа: опять же, он не завершается. Но он меньше. Чтобы решить проблему, вы должны что-то сделать в этом фрагменте. Поскольку, пока эта часть остается как есть, проблема будет сохраняться.

В данном случае виновником является цель length(R,B): переменная B встречается здесь впервые, поэтому она не конкретизирована. А также R не конкретизирован. Каковы ответы на цель length(R, B). Попробуйте!

| ?- length(R, B).

B = 0
R = [] ? ;

B = 1
R = [_] ? ;

B = 2
R = [_,_] ? ;

B = 3
R = [_,_,_] ? ;

B = 4
R = [_,_,_,_] ? ;

B = 5
R = [_,_,_,_,_] ? ...

Так что ответов бесконечно много. Поэтому ваша программа не завершается.

Эту проблему можно легко решить, заменив length(R, B), A == B на length(R, A).

| ?- mysort([9,1,2,3,4,5,6,7,8],L).

L = [1,2,3,4,5,6,7,8,9]

(21841 ms) yes

Еще несколько замечаний: ! в ваших программах — это красные вырезы, они могут доставить вам массу неприятностей. И потом, время выполнения не такое уж большое: 21 секунда на сортировку 9 элементов звучит не очень круто. Но, пожалуйста, имейте в виду, что ваше описание, по сути, говорит: я хочу перестановку, то есть по возрастанию. Вы не говорите больше, чем это. Учитывая эту очень скудную информацию, Пролог, по крайней мере, способен находить правильные ответы. И это даже довольно компактно.

Как превратить эту программу в более эффективную, см. этот ответ.

person false    schedule 06.07.2013