没有断言/撤回的分支和边界

这个练习要求我找到三种产品的最佳组合，给出价格和要避免的特定组合。教科书使用 assertz 和 retractall 来模拟状态变量。


price(a1,1900).
price(a2,750).
price(a3,900).
price(b1,300).
price(b2,500).
price(b3,450).
price(b4,600).
price(c1,700).
price(c2,850).

incompatible(a2,c1).
incompatible(b2,c2).
incompatible(b3,c2).
incompatible(a2,b4).
incompatible(a1,b3).
incompatible(a3,b3).

:- dynamic bound/1.
bound(5000).

solution(A,B,C,P) :-
  member(A,[a1,a2,a3]),price(A,PA),member(B,[b1,b2,b3,b4]),\+ incompatible(A,B),price(B,PB),P0 is PA + PB,bound(Bound),write('Current bound: '),writeln(Bound),P0 =< Bound,member(C,[c1,c2]),C),\+ incompatible(B,price(C,PC),P is PA + PB + PC,P =< Bound,retractall(bound(_)),assertz(bound(P)).

是否可以在 Prolog 中使用分支定界而不使用动态谓词？
是否对 Prolog 中的状态变量达成共识？
有没有办法将状态变量（或任何代理）的范围限制为单个规则？

这段代码最大的问题是它不可重入。它隐含地假设在任何时间点都只有一个搜索实例。但是如果内部的某个部分想要自己使用类似的搜索，则没有警告没有错误可以防止这种情况发生。

对于精确的机制应该是什么样子没有太多的共识，现有的系统都不同。要理解这一点，请查看 findall/3 或 call_nth/2 的实现，其中有针对 SICStus、SWI 和 Eclipse 的特定解决方案。正是这里也需要这种机制。

但也要考虑使此搜索更通用。据推测，您所指的教科书是在 call/N 被普遍接受之前编写的。

是否可以在 Prolog 中使用分支定界而不诉诸动态谓词？

是的，您只需将边界作为递归调用的附加参数（如函数式编程中所做的那样）。恕我直言，这实际上是一个比断言到 Prolog 数据库更干净的解决方案。更改数据库然后执行重做的技巧令人困惑，因为它正在重做的不是同一个程序。不过，将其放入教科书是一个“巧妙的技巧”。

Prolog 中的状态变量是否有共识？

只需将它们作为参数传递即可。如果需要，您可以使用 Global Variables（如果支持）。另见：Database in SWI-Prolog。为了保持参数列表小，您可能需要考虑使用关联数组 (SWI-Prolog dicts,library(assoc)) 作为“参数包”。但像往常一样，这会影响效率。

有没有办法将状态变量（或任何代理）的范围限制为单个规则？

显然，争论是局部的，但遗憾的是，没有任何超越。我想要“局部可见性范围”，特别是对于谓词，以便明确地将“辅助谓词”与其“父谓词”相关联，但“模块”（以不同方式实现）是我们拥有的最好的。（传统认为巨大大小的模块大小是可以接受的，对此我会毫不含糊地斥责实习生，就像编写几千行的对象一样，这并没有使这一点变得更好，但是我离题）

您的解决方案并不总是在回溯时使用正确的 Bound。问题是变量被绑定得太快，然后即使事实被 assertz/retract 更新，变量仍将绑定到先前的值。您可以通过让顶层回溯所有解决方案来查看效果。有一些解决方案的成本高于以前的解决方案。

这里有一个针对您的问题定制的迭代解决方案，尽管您可以通过使用 call/N 而不是对 price/2 和 any_incompatible/2 的固定调用使其更通用

solution2(Bound,Best):-
  branch_and_bound([[a1,a2,a3],[b1,b2,b3,b4],[c1,c2]],Bound,[],Best).

branch_and_bound([[]|_],_,Best,Best).
branch_and_bound([[Item|Layer]|Layers],CurrentBest,Best):-
  price(Item,ItemPrice),(  ItemPrice >= Bound
  ->  Bound1-CurrentBest1=Bound-CurrentBest
  ;   branch_and_bound(Layers,Bound1,current(ItemPrice,[Item]),CurrentBest1)
  ),branch_and_bound([Layer|Layers],CurrentBest1,Best).

branch_and_bound([],CurrentPrice,current(CurrentPrice,Items),PreviousBest,[best(CurrentPrice,RItems)|OtherBest]):-
  reverse(Items,RItems),( CurrentPrice==Bound -> OtherBest=PreviousBest ; OtherBest=[] ).
branch_and_bound([[]|_],Bound2,NewPrice is CurrentPrice + ItemPrice,(
     ( NewPrice > Bound ; any_incompatible(Items,Item) )
  ->   Bound1-CurrentBest1=Bound-CurrentBest
  ;    branch_and_bound(Layers,current(NewPrice,[Item|Items]),Best).

any_incompatible([OneItem|Items],Item):-
  incompatible(OneItem,Item) -> true ; any_incompatible(Items,Item).

它将列出所有最佳解决方案，并使用当前找到的最佳解决方案定义的当前 Bound 修剪搜索空间。

样品运行：

?- solution2(5000,Best).
Best = [best(1900,[a3,b1,c1]),best(1900,[a2,c2])].

没有断言/撤回的分支和边界

winsomil 回答：没有断言/撤回的分支和边界

大家都在问