1

This exercise asked me to find the best combination of three products, given the prices and specific combinations to avoid. The textbook employs assertz and retractall to emulate a state variable.


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)).
  1. Is it possible to use branch and bound in Prolog without resorting to dynamic predicates?
  2. Is there a consensus on state variables in Prolog?
  3. Is there a way to restrict the scope of a state variable (or whatever the proxy would be) to a single rule?
vasily
  • 2,850
  • 1
  • 24
  • 40
  • 2
    Of interest: [Prolog planning using retract and assert](https://stackoverflow.com/q/55512086/1243762) - The accepted answer does not use the predicates assert/1 or retract/1 but the concept of updating state is used. – Guy Coder Jul 16 '21 at 09:03
  • 2
    Of interest: [Coding Guidelines for Prolog](https://arxiv.org/pdf/0911.2899.pdf) - This is also referenced in [Useful Prolog References](https://swi-prolog.discourse.group/t/useful-prolog-references/1089) – Guy Coder Jul 16 '21 at 09:22

3 Answers3

5

The biggest problem with this code is that it is not re-entrant. It implicitly assumes that at any point in time there is exactly one instance of searching. But if some part inside wants to use a similar search all by themselves, no warning no error prevents this from happening.

There is not much consensus on how the precise mechanism should look like, existing systems all differ. To understand this, look at the implementation of findall/3 or call_nth/2 where there are specific solutions for SICStus, SWI, and Eclipse. Precisely this mechanism would be needed here too.

But also consider to make this search more generic. Presumably the textbook you are referring to was written prior to the general acceptance of call/N.

false
  • 10,264
  • 13
  • 101
  • 209
3

Is it possible to use branch and bound in Prolog without resorting to dynamic predicates?

Yes, you just hand the bounds around as additional arguments across recursive calls (as is done in functional programming). IMHO, this is actually a cleaner solutions than asserting into the Prolog database. The trick of changing the database and then performing a redo is confusing, as it's not the same program that is being redone. It's a "neat trick" to put into a textbook though.

Is there a consensus on state variables in Prolog?

Just hand them around as arguments. If need be, you can use 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)) as "argument bundle". But as usual, this has implications on efficiency.

Is there a way to restrict the scope of a state variable (or whatever the proxy would be) to a single rule?

Evidently, arguments are local, but there is, sadly, nothing beyond. I would like to have "local visibility scopes", especially for predicates so as to unequivocally associate "helper predicates" to their "parent predicate" but "modules" (implemented variously) is the best we have. (This is not made better by a tradition which finds module sizes of enormous size acceptable, something for which I would berate the intern in no uncertain terms, same as writing an object of several thousand lines, but I digress)

David Tonhofer
  • 14,559
  • 5
  • 55
  • 51
  • I am struggling to close the gap between backtracking which is the Prolog's way of "iterating" over sets and recursive calls in functional programming. The backtracking is bound to unwind whatever value I might assign in the depth of such quasi-loop. – vasily Jul 16 '21 at 11:14
  • 1
    @vasily That is right. If you want to loop while "collecting information" you will have to create a (tail-recursive) loop, exactly as in functional programming -- or else use one of the meta-predicates that _collect the bindings generated on each success of a subgoal_: [`bagof/3`](https://eu.swi-prolog.org/pldoc/doc_for?object=bagof/3), setof, findall. My [info on findall](https://github.com/dtonhofer/prolog_notes/tree/master/swipl_notes/about_findall). Without those, Prolog would be much less useful. – David Tonhofer Jul 18 '21 at 19:17
2

Your solution is not always using the proper Bound upon backtracking. The problem is that the variable gets bound too soon and then even if the fact gets updated with assertz/retract the variable will still be bound to the previous value. You can see the effects by letting the toplevel backtrack through all the solutions. There are some solutions intersped that have higher cost than a previous one.

Here goes an iterative solution customized to your problem, though you could probably make it more general by using call/N instead of the fixed calls to price/2 and 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], 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).

It will list all the best solutions, trimming the search space with the current Bound defined by the currently found best solution.

Sample run:

?- solution2(5000, Best).
Best = [best(1900, [a3, b1, c1]), best(1900, [a2, b1, c2])].
gusbro
  • 22,357
  • 35
  • 46