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)`

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..