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

Question

В предыдущем посте я в конце концов выяснил, как написать программу 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/ компьютер должен быть в состоянии справиться с этим без проблем, то есть мне нужно переосмыслить алгоритмы?

Answer 1

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

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

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

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

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

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

Мисорт (L, M): -
   backtrack_perm (L, M), false,
   отсортировано (M),
   !,  

backtrack_perm([],[]):- неверно.
backtrack_perm([LH|LT],R):-
   Длина ([LH | LT], А),
   длина (R,B), ложь,
   A == B,
   член (LH, R),
   выберите (LH, [LH | LT], X),
   выберите (LH, R, Y),
   perm_recurse (X, Y).  

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

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

|? - длина (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 мс) да

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

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