SWI-Prolog 回溯无限循环 [英] SWI-Prolog Backtrace Infinite Loop

问题描述

我有一个玩具模块；

:- module(toys,toy/2).

%toy(TOY_NAME,PRICE).

我有一些玩具元素，

toy(train,5).
toy(doll,6).
toy(car,3).
..ext.

我写了一个函数来计算给定玩具清单的总价，例如

I wrote a function that calculates the total price of given toy list such as

calculatePrice([],0).
calculatePrice([H|T],Result):- toy(H,P),calculatePrice(T,X), Result is X+P.

当我调用 calculatePrice([train,train,doll,train],X) 时它工作正常并返回 21.但是当我调用 calculatePrice(X,21) 时会发生无限循环.

when I called calculatePrice([train,train,doll,train],X) it works fine and returns 21. But when I call calculatePrice(X,21) an infinite loop occurs.

我试图减少用户，但后来我只得到了 1 个答案，我想得到所有可能的答案，例如总价为 21 的所有玩具组合.

I tried to user cut, but then i only got 1 answer, I want to get all possible answers like all combinations of toys that will be total price of 21.

推荐答案

Prolog 深度优先，这意味着它会继续寻找将玩具进一步添加到列表中，并且永远不会看是否已经达到总价，再增加元素没有意义.

Prolog works depth first, so that means that it will keep looking to append the list further with toys into the list, and never looks whether the total price already is reached, and thus adding more elements makes no sense.

我们可以通过反向计算价格来解决这个问题:我们可以使用 library(clpfd) 并定义列表中带玩具的价格和不带玩具的价格之间的关系，以及添加一个约束，如果我们递归，我们正在寻找的价格应该总是大于零，例如:

We can solve this by calculating the price in reverse: we can use the library(clpfd) and define the relation between the price of the list with the toy and the price without the toy, and add a constraint that the price we are looking for should always be larger than zero if we recurse, like:

:- use_module(library(clpfd)).

calculatePrice([], 0).
calculatePrice([H|T], PHT) :-
    PHT #> 0,
    toy(H, PH),
    PHT #= PT + PH,
    calculatePrice(T, PT).

然后我们得到例如:

?- calculatePrice(L, 21).
L = [train, train, train, doll] ;
L = [train, train, train, car, car] ;
L = [train, train, doll, train] ;
L = [train, train, car, train, car] ;
L = [train, train, car, car, train] ;
L = [train, doll, train, train] ;
...

?- calculatePrice([train, train], P).
P = 10.

?- calculatePrice(L, P).
L = [],
P = 0 ;
L = [train],
P = 5 ;
L = [train, train],
P = 10 ;
L = [train, train, train],
P = 15 ;
L = [train, train, train, train],
P = 20 ;
L = [train, train, train, train, train],
P = 25 
...

约束PHT#>0 在这里是必需的.当我们使用例如 calculatePrice(L, 21) 作为我们还剩下花费的金额"进行查询时，您可以看到 PHT.如果金额小于或等于零，我们就不能再花任何钱，因此该约束应该失败.

The constraint PHT #> 0 is necessary here. You can see PHT when we query with for example calculatePrice(L, 21) as the "amount we have left to spend". In case that amount is less than or equal to zero, we can not spent any money anymore, and thus this constraint should fail.

这篇关于SWI-Prolog 回溯无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！