Need some help with water jug problem ..

Discussion of Common Lisp
Post Reply
roccia
Posts: 1
Joined: Wed Sep 28, 2011 11:29 pm

Need some help with water jug problem ..

Post by roccia » Wed Sep 28, 2011 11:59 pm

It' my homework , I got some problems in programming ...

There are two jugs, one can hold 3 and the other 5 gallons of water. Actions that can be performed with the jugs are:they can be filled, emptied ,poured from one to the other until either the receiving jug is full or the pouring jug is empty. Goal is the larger one have 4 gallon water.
The cost of an action is defined as 1 unit for performing the action, an additional 1 unit for each gallon of water “moved” (filled,emptied, poured), and an additional 1 unit for each gallon wasted (when a jug is emptied ). The path cost (g) is the sum of the cost of all the actions. Use heuristic function h as you defined in Part b above. The “left to right” order of actions is fill-small, fill-large, empty-small, empty-large, pour-small-to-large, pour large-to-small.

The heurstic function I defined is |n-4|, n is the current volume of the larger jug.


here is the programming question:

Code: Select all

;prints the states while they are *visited* (not generated),
; total number of visited states, and cost of solution path
;returns the solution path (sequence of actions) in a list
(defun general-search (insert-fn initial-state goal-test-fn
successor-fn step-cost-fn heuristic-fn)
...
;returns t if the node is a goal state
(defun jug-goal-test (node) 
(eq (large-jug state) 4)
)
;returns a list of legal successor nodes (generated dynamically)
;heuristic-fn could be nil
;the "left to right" order of actions is: ...
(defun jug-successor (node step-cost-fn heuristic-fn) ...)
;returns the step cost of applying an action at a certain node
(defun jug-step-cost (node action) ...)
;returns the (admissible) heuristic value of node
(defun jug-heuristic (node) ...)
;returns the updated frontier with the successors inserted into
;the frontier according to the UCS algorithm
(defun ucs-insert (frontier successors) ...)
;returns the updated frontier with the successors inserted into
;the frontier according to the A* algorithm
(defun a*-insert (frontier successors) ...)

I'm not sure I fully understand the general-search function:

Code: Select all

 (defun general-search (insert-fn initial-state goal-test-fn successor-fn step-cost-fn heuristic-fn) 
insert-fn is a function that contains all kinds of algorithms, but how should I define it ? the same as initial-state and so on.... I know this general search funtion is used to slove all kinds of problmes,such as you can just add MC-function in it to solve Missonaries and Cannibals problem, without writing unnecessary code. but I still can't firgure out how it works . I need someone help me to understand the whole structure of these codes. I don't know whether I made myself clear... anyway , thanks for reading and helping..

wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Re: Need some help with water jug problem ..

Post by wvxvw » Wed Oct 05, 2011 3:42 am

Hi. http://en.wikipedia.org/wiki/Missionari ... ls_problem is a same kind of problem, so would help reading up on it.
In short, you define a state machine. Transitions between states you have already named: fill-small, fill-large etc. It would probably help to abstract them to numbers, so that you could see the progress more clearly. You would also need to "chop off the bad branches" by the rule that if the state has been reached in the past, going into that state again is an error. There is finite number of unique states, given finite number of transitions. If I'm not mistaking, this is the shortest way to do it, but there might be more, and maybe more of another length, so you will need to choose the shortest. Sorry I was "lazy" to actually write the code :)

Code: Select all

------ Action -------|--------- State ---------|
---------------------|- 5 gallons | 3 gallons -|
Fill 5 gallons jug   |      5     |     0      |
Pour to 3 gallons jug|      2     |     3      |
Empty 3 gallons jug  |      2     |     0      |
Pour to 3 gallons jug|      0     |     2      |
Fill 5 gallons jug   |      5     |     2      |
Pour to 3 gallons jug|      4     |     3      |

Post Reply