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