[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
On the homework extra credit problem on IDDFs/DFS node expansions ratio
- To: cse471-f06@parichaalak.eas.asu.edu
- Subject: On the homework extra credit problem on IDDFs/DFS node expansions ratio
- From: "Subbarao Kambhampati" <subbarao2z@gmail.com>
- Date: Fri, 8 Sep 2006 18:50:42 -0700
- Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=nQIHR7hWQUhX2/MDE1hwkK/uKKDOn2LhuAq/dOnTSA3PNZoGZN8QycJaJqRX7YHgGIfYMZLk57PkNbJmhTyo49tkvED2u4FMpntnYPvCo7BIOOytfDFxM42ZG9qUo8oxcwvI5NxkWJtu2DQtuQwNxYQValPXpzK1Ixj6y4eOhLE=
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