0

I failed to write a Prolog program using RBFS algorithm to solve a task - how to measure exactly 3 liters of water using 5-liter and 9-liter water jugs? I have a solution, but it does not use best-first search algorithm and works blindly (without heuristics). Can you please provide some pieces of code to apply RBFS algorithm to my task?

My code without RBFS:

volume(9,5).

program(A,B,W):-
    volume(VA,VB),
    A>=0,
    A=<VA,
    B>=0,
    B=<VB,
    change(A,B,[[A,B]],W),
    write1(W).
    
write1([]).
write1([X|L]):-
    writeln(X),
    write1(L).

element(A,B,W,W1):-
    not(member([A,B],W)),
    add1([A,B],W,W2),
    change(A,B,W2,W1).
              
change(3,_,W,W).
change(_,3,W,W).

change(A,B,W,W1):-
    volume(VA,_),
    B>0,
    C is VA-A,
    C>0,
    min(B,C,Min),
    A1 is A+Min,
    B1 is B-Min,
    element(A1,B1,W,W1).

change(A,B,W,W1):-
    volume(_,VB),
    A>0,
    C is VB-B,
    C>0,
    min(A,C,Min),
    B1 is B+Min,
    A1 is A-Min,
    element(A1,B1,W,W1).

change(A,B,W,W1):-
    volume(VA,_),
    A=VA,
    B>0,
    element(0,B,W,W1).

change(A,B,W,W1):-
    volume(_,VB),
    A>0,
    B=VB,
    element(A,0,W,W1).

change(A,B,W,W1):-
    volume(VA,_),
    A=0,
    element(VA,B,W,W1).

change(A,B,W,W1):-
    volume(_,VB),
    B=0,
    element(A,VB,W,W1).
    
min(A,B,A):- A=<B.
min(A,B,B):-A>B.

add(X,L,[X|L]). 

add1(X,[],[X]).
add1(X,[X1|L],[X1|L1]):-
    add1(X,L,L1).
Nick Reshetinsky
  • 447
  • 2
  • 13
  • Could you please add your code and ouput? – DuDa Feb 24 '21 at 09:25
  • I just added my code, but it has no RBFS logic – Nick Reshetinsky Feb 24 '21 at 15:06
  • What does this "RBFS" acronym stand for? Can you provide the material that explained it to you? What is it about it that you didn't understand? – TA_intern Feb 24 '21 at 16:43
  • RBFS - recursive best first search. It first builds a graph of nodes and assigns a heuristic value to a node, it works by traversing only those nodes that have a lower heuristic value – Nick Reshetinsky Feb 24 '21 at 17:31
  • OK, so you have a good handle on this. What exactly is the problem? – TA_intern Feb 24 '21 at 21:36
  • Does this answer your question? [Prolog - breadth first search for water jug](https://stackoverflow.com/questions/32529229/prolog-breadth-first-search-for-water-jug) –  Mar 20 '21 at 14:50

0 Answers0