project problem description

I got some questions concerning the project. You might be interested.

1). yes. Nodes is a list of node struct values. goalp, children-fn, fvalue-fn are all functions. Actually, "funcall" means to call a function. You can check the syntax of funcall.

2). Here, sort means sort the list of nodes in accsending order based on the f-value. (actually, fvalue-fn should return a fvalue). One simple example of sorting is like this:
CL-USER> (defun fn (x)
(abs (- x 3)))
FN
CL-USER> (sort '( 2 3 5 4 1) #'< :key #'fn)
(3 2 4 5 1)

in which fn is a function return the value of |x-3|. Then, the list is sorted based on the value of |x-3|.

3). I think the instructor already explained the meaning of each entry. However, this defintion is very general. You might have to sepcify it based on your problem.

(defstruct node
STATE ;;the state of the problem corresponding to this node
PARENT ;;the node which is this nodes' parent
ACTION ;;the action which was taken at the nodes parent to get here
G-VAL ;;The g-value of the node
H-VAL ;;THe h-value of the node
F-VAL ;;THE f-value of the node
)


4). It's very difficult to generate some testing input for just part 1 as it is basically a framework to implement A* algorithm. You have to combine it with part 2.

-Lei

----------------------------------------------------
> I have a few questions about the function A*. I am not too good with lisp so bear with me. I think some examples will help me the most.
>
> 1) nodes is a list of node struct values. goalp, children-fn, and fvalue-fn are functions correct? 2) Can you explain to me how the sort function works here, with an example?
> 3) The struct node, can you explain what the values in the struct represent. A good way to do this would be to show me an example of a tree with these values.
> 4) What is a good input for testing this after completion?
>
> I've said a mouthful. I think most of my problems are just that. Understanding the problem (with a bit of lisp unfamiliarity). Any help will be great. I'll stop by your office tomorrow around 4pm if I can.
>
>
>
>
> (defun A* (nodes goalp children-fn fvalue-fn)
> (cond ((null nodes) nil)
> ;; Return the first node if it is a goal node.
> ((funcall goalp (first nodes)) (first nodes))
> ;; Append the children to the set of old nodes
> (t (A* (sort (append (funcall children-fn (first nodes))
> (rest nodes)) #'<
> :key fvalue-fn )
> goalp
> children-fn
> fvalue-fn))))
>
>
> (The sort function we are using is a built-in function for
> commonlisp. It takes three arguments: List to be sorted, the
> comparision predicate with which sorting is done (in our case <) , and
> an optional argument :key, which takes a function and applies it to
> the elements of the list, to get the field over which items of the
> list are compared (in our case, the f-value))
>
> To make our life simple, we shall assume that search nodes are defined
> as structures with at least the following slots:
>
> (defstruct node
> STATE ;;the state of the problem corresponding to this node
> PARENT ;;the node which is this nodes' parent
> ACTION ;;the action which was taken at the nodes parent to get here
> G-VAL ;;The g-value of the node
> H-VAL ;;THe h-value of the node
> F-VAL ;;THE f-value of the node
> )
>
>