为什么Prolog在过滤列表时会找到许多解决方案?

问题描述 投票:0回答:1

我编写了一个谓词,该谓词过滤了所有6以下的数字的列表,但是prolog找到了多个解决方案。

谓词看起来像这样:

sift([], []).
sift([H | T], [H | Res]):- H > 6,
    sift(T, Res).
sift([_ | T], Res):-
    sift(T, Res).

我问这个:?- sift([1, 7, 2, 13], X).

将导致:

X = [7, 13]
X = [7]
X = [13]
X = []

我只期望X = [7, 13],所以为什么Prolog会找到所有这些额外答案?

prolog
1个回答
1
投票

回溯。

当您键入sift([1,10], X).时,Prolog可以对sift([H | T], [H | Res])sift([_ | T], Res)进行模式匹配。这意味着Prolog离开choicepoint,选择一个选项,然后稍后再返回其他谓词。

序言与第一个谓词sift([7, 2, 13], [H | Res])匹配,进一步调用sift([1, 13], Res)

但是,它也与第二个谓词sift([_ | [2, 13]], Res)相匹配,稍后将回溯到此谓词,跳过7。

我们可以仅通过过滤掉元素来解决此问题。

sift([], []).
sift([H | T], [H | Res]) :-
    H >= 6,
    sift(T, Res).
sift([H | T], Res) :-
    H < 6,
    sift(T, Res).

这给:

?- sift([1, 7, 2, 13], X).
X = [7, 13] ;
false.

一种替代方法是使用Prolog if

sift2([], []).
sift2([H | T], [H2 | T2]) :-
    H >= 6 ->
    (H2 = H,
    sift2(T, T2)
    ); sift2(T, [H2 | T2]).

此谓词表示'列出清单和可能的答案。如果第一个元素等于或大于6,则列表的第一个元素和答案应匹配,并且过滤后的尾部应与答案的尾部匹配。否则,列表的尾部需要能够产生整个答案。

这避免了回溯,并且将在第一个之后停止搜索解决方案。

?- sift2([1, 7, 2, 13], X).
X = [7, 13].

[打开trace.来查看两个谓词以进行进一步描述。

热门问题
推荐问题
最新问题