[8/29 Discussion/Thinking Cap topic for BLOG] Search algorithms...

["Subbarao Kambhampati" <rao@asu.edu>]

Here are a few things that you can think about and/or comment on.

[0] (optional ;-) Estmate how near-sighted an instructor needs to be to not 
notice that you are sleeping and/or doing something below the desk. The estimate can 
be analytical, and can depend on your height, distance from the podium, decibels of snoring etc.


[1] (Iterative deepening search)
 
The following are two of the characteristics of iterative deepening search: 

a. It uses depth-first search in each of its iterations
b. it increments the "depth cutoff" for the tree uniformly (i.e., there is one single depth limit
for all branches)

If I am considering the following changes to IDDFS 

a': Instead of use depth-first search, use breadth first in each iteration
b': instead of using a uniform depth cutoff, use non-uniform depth cutoffs (i.e, the "search fringe" will
go to varying depths in different branches). 

How do a' and b' affect

(i) completeness (ii) optimality (iii) time complexity (iv) space complexity properties?


[2](Effect of the goal distribution)
In the discussion we did in the class, I assumed that the goal node(s) can appear at any level of the 
search tree, and anywhere in that level. If I happen to know that all goal nodes will appear only at level (depth) "m" 
would it change the relative tradeoffs between breadth-first and depth-first? Can you think of some problems where 
this type of property holds? 

[3](search on finite graphs with cycles)
We noticed that even if the number of states is finite, it is possible for a search to "loop"--i.e., go back and forth between 
the same state multiple times. This is a problem for both breadth-first and depth-first, but is a bigger problem for depth-first
(since it may not even terminate). One way of stopping this problem is to maintain a  "CLOSED" list that contains all the nodes that have 
been already expanded. Before adding any new node to the queue (i.e., OPEN list), we check to make sure if the state for that
node already exists on the CLOSED list. If it does, we don't put it back on the OPEN. 

How does this simple idea affect the time and space complexity of depthfirst and breadth-first search?


Rao