Need some help with water jug problem ..
Posted: 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 ï¬lled, 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 deï¬ned as 1 unit for performing the action, an additional 1 unit for each gallon of water “moved†(ï¬lled,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 deï¬ned in Part b above. The “left to right†order of actions is ï¬ll-small, ï¬ll-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:
I'm not sure I fully understand the general-search function:
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..
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 ï¬lled, 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 deï¬ned as 1 unit for performing the action, an additional 1 unit for each gallon of water “moved†(ï¬lled,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 deï¬ned in Part b above. The “left to right†order of actions is ï¬ll-small, ï¬ll-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)