Prolog递归不会按预期停止-Java 学习之路

大家好，这是我的第一篇文章，所以如果你有任何关于如何提问的建议我试着用递归对数字列表进行排序，我有一个 my_max/2 谓词，它返回一个列表的最大值，所以在返回后我选择那个列表中的值，然后将其添加到我的排序列表中 . 然后我用新列表递归 .

我的问题是谓词似乎工作并找到正确的列表，但是当谓词退出时，它将所有列表恢复到原始状态，基本上撤消了谓词所做的所有工作 . 我认为这与Prolog如何回溯有关？

%finds the max of a list, if the list is empty return int_min

my_max([],-2147483647).
my_max(L,M):-select(M,L,Rest), \+ (member(E,Rest),E>M).

%calls the my_max predicate store it in X, combines x and sorted and appends 
%it to sorted2,then it takes X out of unsorted and creates Unsorted2 then  
%recurse with unsorted2 and sorted2 should stop and output when unsorted is 
%empty or []

my_sort([],S).
%my_sort([],S):-write(S). for test    
my_sort(Unsorted,Sorted):-
   my_max(Unsorted,X),
   append(Sorted,[X],Sorted2),
   select(X,Unsorted,Unsorted2),
   my_sort(Unsorted2,Sorted2).

我添加了写只是为了表明它对列表进行了排序 . 输出应为 S=[3,2,1,1] .

Output from the trace

1 回答

2
首先，在加载文件时，我得到：
```
Warning: Singleton variables: [S]
```
由于基本情况：
```
my_sort([],S).
```
问题是基本情况表明空列表与单例变量S匹配，所以尝试：
```
?- my_sort([],[1,2]).
true ;
false.

?- my_sort([],hello).
true ;
false.
```
在任何情况下都不应该成功 . 所以你的基本情况应该是空列表：
```
my_sort([],S).
```
而不是在基本情况下构建完整的排序列表，您可以通过递归构建它，并在基本情况下留下一个空列表：
```
my_sort([],[]).
my_sort(Unsorted,Sorted):-
   my_max(Unsorted,X),
   select(X,Unsorted,Unsorted2),
   my_sort(Unsorted2,Sorted2),  %  <- continue to find the sorted sublist
   append(Sorted2,[X],Sorted).  %  <-place max at the end of sorted
```
在上面，Sorted2是Sorted的 sublist ，因此您可以递归地找到子问题的列表Sorted2，然后添加max . 这是在每个步骤中递归完成的，在基本情况下，您将有空列表 .

所以在这里更好地理解它是一个例子 - 解释：
假设你要排序 [2,1,3] 列表 .
- 查找 max = 3 find为 [2,1] 排序（稍后将在所有递归调用后添加3）
- 查找 max = 2 找到排序 [1]
- 查找 max = 1 找到排序 [] which is []
- 添加 max = 1 - > Sorted = [1]
- 添加 max = 2 - > Sorted = [2]
- 最后添加 max = 3 - > Sorted = [1,2,3] 示例：
？ - my_sort（[4,1,3,2]，L） . L = [1,2,3,4];假 .

一些优化

在每个步骤中，您通过遍历未排序的列表找到O（n）步的最大值，其中n是未排序列表的长度 . 再次附加O（n） . 再次选择O（n） . 因此，在每个步骤中总共执行3次O（n）计算 .

为避免这种情况，您可以按降序构建列表，这样就不需要在O（n）中使用append .

此外，您的最大谓词可以返回Rest列表，因此您可以避免sort谓词中的select / 3来减少另外N个步骤：
```
my_sort([],[]).

my_sort(Unsorted,[X|Sorted]):-
   my_max(Unsorted,X,Unsorted2),
   my_sort(Unsorted2,Sorted).
```
例：
```
?- my_sort([4,1,3,2],L).
L = [4, 3, 2, 1] ;
false.
```
现在要获得升序使用reverse / 2：
```
?- my_sort([4,1,3,2],L),reverse(L,L1).
L = [4, 3, 2, 1],
L1 = [1, 2, 3, 4] ;
false.
```
这样做O（N）步骤来反转列表，但每次递归调用只有一次！
回复于 2024-04-29T22:00:11+08:00

Prolog递归不会按预期停止

1 回答

相关问题