没有断言/收回的分支定界

Question

这个练习要求我找到三种产品的最佳组合，给定价格和要避免的特定组合。教科书使用 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]),
  \+ incompatible(A, C),
  \+ incompatible(B, C),
  price(C, PC),
  P is PA + PB + PC,
  P =< Bound,
  retractall(bound(_)),
  assertz(bound(P)).

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

Answer 1

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

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

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

只是把它们作为参数传递出去。如果需要，您可以使用 Global Variables if supported. See also: Database in SWI-Prolog. To keep argument lists small-ish, you may want to consider using associative arrays (SWI-Prolog dicts, library(assoc)) 作为“参数包”。但像往常一样，这会影响效率。

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

显然，争论是局部的，但遗憾的是，除此之外别无他法。我想要“本地可见性范围”，特别是对于谓词，以便明确地将“辅助谓词”与其“父谓词”相关联，但“模块”（以各种方式实现）是我们拥有的最好的。（这并没有因为发现模块大小巨大大小可以接受的传统而变得更好，对此我会毫不含糊地斥责实习生，就像写一个几千行的对象一样，但我离题了）

Answer 2

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

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

但也要考虑使此搜索更通用。据推测，您所指的教科书是在 call/N.

被普遍接受之前编写的

Answer 3

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

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

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

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

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

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

样本运行：

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

没有断言/收回的分支定界

Branch and bound without assert / retract

prolog

branch-and-bound