SWI-Пролог Backtrace Infinite Loop

Question

У меня есть игрушечный модуль;

:- module(toys,toy/2).

%toy(TOY_NAME,PRICE).

и у меня есть несколько игрушечных элементов,

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

Я написал функцию, которая вычисляет общую стоимость данного списка игрушек, например

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

когда я вызывал CalculatePrice ([поезд, поезд, кукла, поезд], X), он работает нормально и возвращает 21. Но когда я вызываю CalculatePrice (X, 21), возникает бесконечный цикл.

Я попытался сократить пользователь, но затем я получил только 1 ответ, я хочу получить все возможные ответы, как и все комбинации игрушек, общая стоимость которых равна 21.

Answer 1

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

:- module(calculatePrice,
          [calculatePrice/2
          ]).

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

calculatePrice(L, P) :-
    length(L, _N),
    maplist(toy, L, Ps),
    sumlist(Ps, P).

доходность

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

Осторожно, это не заканчивается.Можете ли вы определить, почему?И исправить это?В противном случае обратитесь за помощью:)

Если вы хотите узнать больше об итеративном углублении и Прологе, см. эту страницу или этот документ ...

Answer 2

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

Мы можем решить эту проблему, вычислив цену в обратном порядке: мы можем использовать library(clpfd) и определить соотношение между ценой списка с игрушкой и ценой без игрушки, и добавитьограничение на то, что искомая цена всегда должна быть больше нуля, если мы повторяем, например:

<b>:- use_module(library(clpfd)).</b>

calculatePrice([], 0).
calculatePrice([H|T], PHT) :-
    <b>PHT #> 0,</b>
    toy(H, PH),
    <b>PHT #= PT + PH,</b>
    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 равнонеобходимо здесь.Вы можете видеть PHT, когда мы запрашиваем, например, calculatePrice(L, 21) как «сумму, которую мы оставили потратить».В случае, если эта сумма меньше или равна нулю, мы не можем больше тратить деньги, и, таким образом, это ограничение не будет выполнено.