Lecture Notes: IDA*

1. Questions on A* or HW so far?

2. IDA* Intro

A. Complexity of A*: O(BD) time and space. Hopefully (B/K)D on average. But on large problems space requirements dominate. Review Depth First with Iterative Deepening (DFID).

B. Idea: Like DFID except:

i. Initial Cutoff = h(root)

ii. Cutoff based on f, not just g

iii. Can increase cutoff by > 1 per iteration

3. Examples

A. Example 1 (Same as A* example)

B. Example 2

4. IDA* Pseudo Code

DF-Aux(Node, Cutoff)
  if f(Node) > Cutoff then return f(Node)
  if  solution(Node) then return Node
  Min = 
  for each Child of Node do
    Temp = DF-Aux(Child, Cutoff)
    if solution(Temp) then return Temp
    if Temp < Min then Min = Temp
  return Min


IDA*(Root)
  Cutoff = h(Root)
  loop
    Temp = DF-Aux(Root, Cutoff)
    if solution(Temp) then return Temp
    if Temp =  then return failure
    Cutoff = Temp

5. Resultant Complexity if a tree

O(D) or O(BD) space

Problem: how to prevent repeats of previous nodes? (Check parent? Check all ancestors?) How to quantify the time penalty? [Open Question for non-ancestors] E.g.:

6. Backquote (Shorthand for list/quote/append. Often used with macros).

           'Foo º 'Foo
           '(A ,B C) º (list 'A B 'C)
           
           (setq A '(Foo Bar))
           '(A ,A ,@A) --> (A (Foo Bar) Foo Bar)
             º (append (list 'A) (list A) A)
           

A. Example: Suppose you were building a symbolic differentiation/simplification package. (One of the options for the final project). One of the simplifications you wanted to do was to convert a list of
(* X 2 X 3 X 4) to (* X X X 24). Assuming the variable is called Expression:

           '(,@(remove-if #'numberp Expression) 
         ,(apply (first Expression) (remove-if-not #'numberp Expression)))

Table of contents

1. - Questions on A* or HW so far?

2. - IDA* Intro

3. - Examples

4. - IDA* Pseudo Code

5. - Resultant Complexity if a tree

6. - Backquote (Shorthand for list/quote/append. Often used with macros).