Here it is:


Recall State Space Problem-solving formulations and the Depth-bounded 
Depth-first Search, A* and Iterative Deepening Depth-first Search 
problem-solving  algorithms.

Here you are asked to specify concisely in LISP the Iterative Deepening
A* Search algorithm, IDA*.

IDA* seeks to limit memory requirements of A* search (in the same
fashion as IDDFS does for DFS) by iteratively searching using A*.
But rather than using a depth bound limit as in IDDFS, IDA* uses an f-hat 
limit to prune the search.

Here you may assume you have available a function called DFS* that
conducts an A* search to a cost limit supplied as an argument. You
would call this function using the expression 

        (DFS* node goal-test successor-function f-limit),

where node is a "problem-solving node",and
      goal-test is a function that tests for goal nodes, and
      successor-fuction expands nodes into successor nodes, and
      f-limit is the current f-hat limit. (No nodes will be 
                       expanded whose f-hat value is greater than this limit.)

The DFS* function returns a list of two values:

The first value is a solution sequence if one has been found, otherwise nil. 
The second value is the cost of the found solution sequence (which 
would obviously be less than or equal to f-limit). 
If no solution sequence was found, then the second returned value is the 
next value of the f-hat limit.

You are asked to code ONLY THE MAIN IDA* function using DFS*. Its inputs 
are a state space problem and an initial f-hat cost limit, f-limit.


==========================================================================

Solution (Ok...ok...I fixed the obvious bug in the prior version):

(defun IDA* (initial-state goal-test successor-function f-limit)

  (let
   ( (root  (list initial-state nil 0 0 nil))
     (result (DFS* root goal-test successor-function f-limit)))

   (loop
   (if (first result)  (return result))
   (setf result
            (DFS* root goal-test successor-function (second result))))))






;BTW: what is the initialization of "f-limit"
:Answer:  (setf f-limit (f-hat S0))