Пролог Внедрение Mergersort не остановит - PullRequest
Новая
       59

Пролог Внедрение Mergersort не остановит

0 голосов
/ 11 июня 2018

Я новый разработчик Prolog и пытаюсь заставить работать сортировку слиянием. Запрос 

mergesort([2,1],T).

Произведет 

T=[1,2];
T=[1,2];
T=[1,2];
...

Так что, похоже, он "правильно" сортируетпоследовательность не останавливается

С другой стороны, если бы у меня был запрос, такой как 

mergesort([2,1],[2,1])

, он попадает в бесконечный цикл.Мне интересно, почему это так? 

append([H|T],LISTB,[H|LISTC]):-
    append(T,LISTB,LISTC).

split(LIST,L1,L2):-
    length(LIST,LENGTH),
    M is div(LENGTH,2),
    append(L1,L2,LIST),
    length(L1,L1LENGTH),
    (L1LENGTH =:= M).

merge(A,[],A).
merge([],B,B).
merge([A|TA],[B|TB],[A|MERGED]) :-
    A =< B,
    merge(TA,[B|TB],MERGED).
merge([A|TA],[B|TB],[B|MERGED]) :-
    B < A,
    merge([A|TA],TB,MERGED).

mergesort([],[]).
mergesort([X],[X]).
mergesort(LIST,OLIST):-
    split(LIST,L1,L2),
    mergesort(L1,OLIST1),
    mergesort(L2,OLIST2),
    merge(OLIST1,OLIST2,OLIST).

Ответы [ 2 ]

0 голосов
/ 11 июня 2018

(append([], L, L). отсутствует)

Во-первых, уменьшите размер ввода!Проблема, с которой вы сталкиваетесь с [2,1], уже может наблюдаться с [2] и даже []! 

?- mergesort([],T).
   T = []
;  T = []
;  T = []
;  T = []
...

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

?- mergesort([], T), <b>false</b>.
*LOOPS*

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

append([], L, L).
<s>append([H|T],LISTB,[H|LISTC]):- <b>false</b></s>,
    <s>append(T,LISTB,LISTC)</s>.

split(LIST,L1,L2):- <b>LIST = []</b>,
    length(LIST,LENGTH),
    M is div(LENGTH,2),
    append(L1,L2,LIST),
    length(L1,L1LENGTH),
    (L1LENGTH =:= M).

<s>mergesort([],[]) :- <b>false</b></s>.
<s>mergesort([X],[X]) :- <b>false</b></s>.
mergesort(LIST,OLIST):- <b>LIST = []</b>,
    split(LIST,L1,L2), <b>L1 = [], L2 = []</b>,
    mergesort(L1,OLIST1), <b>false</b>,
    <s>mergesort(L2,OLIST2)</s>,
    <s>merge(OLIST1,OLIST2,OLIST)</s>.

Я добавил цели false и L = [] , которые все заканчиваются и, таким образом, либо улучшают завершение, либо оставляют его как есть .Этот результирующий фрагмент программы известен как .

Поскольку эта программа выполняет цикл, также ваша исходная программа выполняет цикл.Таким образом, где-то в видимой части должна быть ошибка.Действительно ли имеет смысл, что рекурсивное правило mergesort/2 применяется к пустому списку?

((Кроме того, split довольно неэффективен). *) 1035 *

0 голосов
/ 11 июня 2018

Я уверен, что это хакерское решение, однако это A решение 

mergesort(LIST,OLIST):-
    split(LIST,L1,L2),
    mergesort(L1,OLIST1),
    mergesort(L2,OLIST2),
    merge(OLIST1,OLIST2,OLIST),
    !.
...