[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

On the homework extra credit problem on IDDFs/DFS node expansions ratio



There was apparently a question in yesterday's recitation session as to whether the
ratio of nodes expanded by IDDFS to DFS should  really be (b+1)/(b-1)

the (b+1)/(b-1) expression is the ratio of the _average_ number of nodes expanded by
IDDFS vs DFS 

The ratio of worst case number of nodes expanded will turn out to be slightly different.

(Getting the ratio for average is slightly more involved compared to getting the ratio for
the worst case).

FYI
Rao


--
Subbarao Kambhampati
http://rakaposhi.eas.asu.edu