[Thinking Cap]: Optimal Sub-structure;

To: "Rao Kambhampati" <rao@asu.edu>

Subject: [Thinking Cap]: Optimal Sub-structure;

From: "Subbarao Kambhampati" <rao@asu.edu>

Date: Mon, 10 Sep 2007 19:06:19 -0700

Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:references:x-google-sender-auth; bh=qL9ypF4VsaQETUKKkVigMcojlUc2SCXbsHNLcfismVE=; b=QR70HktXGhlDNaqZQgpMqzkgZ5mO6og1arZ8y9HzEfCVjS7/qbh1OID1M18P/1xH/IZN2MY1BsmMg1HivWawKkVAXkXyWV6twjNLJzeMp0J/5BknNy+eZJOkY6OBgvwb6pxxUy2IvsLjJakzGBNwQPpsmuSLgi3COD3vBB6IAZA=

Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:references:x-google-sender-auth; b=UuH7YVpX/LadSrD7WVHg+0AYIg/9HNUdK6aQHXrhl8eFDd9nV5OPmBMrYi7cb1oBzPTPAVTTjqPa1r1uEg1xYzf9hb3ulSbJJgdBjdT4Mz/yMQzkuADHV8l19h6c1vgLaOFyIclN1p091Wu+OVb2ZKE1IMjqqd0/TzQGqieJ+/A=

In-reply-to: <8d80847a0709101905md7fb37bh1a86a990bbe4a8c8@mail.gmail.com>

References: <8d80847a0709101905md7fb37bh1a86a990bbe4a8c8@mail.gmail.com>

Sender: subbarao2z2@gmail.com

1. We talked about the fact that all our search algorithms use "optimal-substructure" property. Because of this we never have to maintain more than the "current best path" to a node. Give an example of a scenario where optimal substructure doesn't hold--and argue that in that case, (1) the markov property also doesn't hold ( i.e., where you can go from a state depends not just on the state, but how you got there) and (2) argue that you will need to maintain more than the best path to the intermediate nodes so as to be able to find the optimal path to the goal node.

1.1. In your example above, see if you can change the definition of "State" so that the optimal sub-structure property holds again (and so does markov property).

Rao