Monday, September 10, 2007

[Thinking Cap]: Optimal Sub-structure;

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).


Tuan A. Nguyen said...

Hi everyone,

This is my example:

I want to go from location S_0 to S_g as quickly as possible, and assuming that there're some kinds of transportation I can choose during my journey, each of which only runs on specific routes and takes different periods of time from each other (e.g, taxi will move faster than bus, though its' more expensive). To find my path (together with suitable vehicles) from S_0 to S_g, I will run "Dijkstra" algorithm, in which for each location S_i, T(S_i) is the amount of time I need to spend to get S_i from S_0 (I choose time since it's my current concern). The edge from S_i to S_j indicates the shortest time of any kinds of transportation going from S_i to S_j. At each step of the algorithm, one "visited" location W with minimum T value will be chosen, and T's values of un-visited locations reachable from W will be updated if necessary.

Now I follow the result of Dijkstra to begin my journey. Suppose that at the current time, I am in S_4, and next I need to flight to come to the next location. However, because I haven't take care of my budget so far, I'm very disapointed that I don't have enough money for flight ticket. As a result, I must choose a bus instead, and finally I come to the destination much later than expected.

The problem here is that at location S4, I just keep track the min time used, but not how much money I spent from the beginning to S4. In other words, to continue to find the optimal path (in terms of time used) from S4 to S_g, I need to know not only the state S4 (time used) but also other information (money used) of locations between S_0 to S_4 in the optimal path.

We can change the state to solve this problem: state includes both the time and money used, i.e at each step, I will choose the next vehicle that I can afford and has the minimum running time. This representation also help me if I change my objective: journey with minimum total of time, and help me to save as much money as possible. Then, time and money will be my preferences (in that order of importance) in choosing the best location at each step of Dijkstra algorithm. We can easily extend the discussion to problem where there are many objectives need to be concerned during the search.


Subbarao Kambhampati said...


This is in the right direction but needs to be clarified on several points:

1. Why does it *not* have optimal substructure? (you didn't argue that the optimal path to S_G doesn't pass through optimal paths for S_4 etc)

2. Illustrate that you need to keep track of multiple paths to intermediate nodes to find the optimal path to the goal node.

What is right about what you wrote is the argument/insight that when you do lose optimal substructure, often it is possible to reinstate it by extending the "state" with additional information.


Ravi Gummadi said...

Consider an army positioned at the border of a city and asked to accomplish the following task.They have limited time and resources to achieve this.

G1 - Goal - [ This contains two goals a. Blowup Whole City and b. come out with least damage G1-a has higher precedence over G1-b..]

Each of the following nodes are associated with Factors such as

F1. Distance from Army Camp
F2. Importance to the city
F3. Reduction in the enemy power
F4. Alarm levels which can be raised

Intermediate Steps are

N1 - Diffuse nuclear Center

N2 - Blowup Army HQ

N3 - Blowup Airport

N4 - Blowup Police Station

N5 - Blowup Civilian Colonies

If you want to blowup the whole city the optimal path to do that is to follow the following sequence

1. N1 -> N2 -> N3 -> N4 -> N5

and consider some optimal paths to intermediate just blowup the civilian colony (N5) They need not go through N1 to N4. That doesn't make sense as well.

This clearly fails the optimal substructure property.


Markov property states that "knowledge of the previous states is irrelevant for predicting the probability of subsequent states"

Lets consider in the above case...If you blow up the Civilian Colony, the alarm levels raised are pretty high and army gets alerted and protects the Nuclear Center
and HQ. If this happens the present resources of the attacking army aren't enough and the probability that all of them are going to be killed is 1 and hence even the city is not demolished

So its very important to know abt the previous states to proceed to next step if you want to reach the Goal node


Apart from the best path to the node, you need to maintain the current situation in the city and predict if its possible to accomplish the task with the remaining force


I guess if in the present state if we include the [Alarm Level, Total strength of enemy force, Own army's strength, Time remaining] this would follow optimal substructure property.
I am not sure !

My function would be something like G(x) = (1/Alarm Level + 1/Total Enemy Force + Army Strength + Time Remaining )...

So when we travel from N1 -> N5 This holds true G(N1) >= G (N2) >= G(N3) >= on

Ravi Gummadi ! :-)

Anupam said...

Example: Assembly line

Let each action be of the form A(i) i.e. "mount component i", and let there be an ordering which components can be mounted. Each state represents the components that have been mounted.
If product X requires action A(2), A(3) (i.e. components 2 and 3), and product Y requires A(1), A(2) and A(3), then assembling procedure for Y includes actions needed for X. But since this set of actions is not a minimal set needed to assemble X, its not an optimal sub-structure for assembling X.
Also, since the components cannot be mounted in any order, components that can be added not only depend on the list of components added so far(the state), but also on order in which they were added.
I'm not sure how optimal sub-structure can be made valid in this case by changing state definition.

RANDY said...

1. A simple example would be crossing a bunch of planks that had pivots in the middle. The Markov property fails because each plank used will temporarily alter the difficulty of crossing it again by tipping it. If you only kept the local best path you would find that a zigzag across the whole structure looked best, while differing plank lengths might make a narrow or chaotic zigzag more favorable.

1.1. The state of the system is the current plank, plus the current tilt angles of all of the planks.

Tuan A. Nguyen said...

Thanks for your comment. I need to write it better:

1. What I mean here is that, in order to come to Sg as fast as possible, I will be ready to sacrifice the time from S0 to S4 (e.g 2 hours) for the money left at S4 so that I can fly a Dreamliner to Sg in 45 minutes. However, this does not mean that I can not go from S0 to S4 in no less than 2 hours. I also can fly if I don't have to save money. This is where "optimal substructure" is not true.

2. Now for instance, from S4 I can also fly A380 to S_g. Although this flight is slower than the previous one, but it's cheaper. Then, it's useful if I know some other way from S0 to S4, which is faster than 2 hours such that the total time (together with flying A380) is still less than 2 hours and 45 minutes, as long as I have enough money left for A380 ticket.

In other words, in this case I need to keep track many paths to immediate nodes so that I will have a best choice for future optimal searching.

3. Now if states include location, time, vehicle and cost, one former state (containing location, time with many paths starting from S0 being kept track) now may correspond to many other states (same location, different from time, vehicle and cost) with one path need to be stored for each. Using this way, "optimal substructure" is correct.

Best regards,

Yin said...

A simple example is a graph with two paths from A to D: A-–1—B—10—D, and A—2—C—1—D. Although the optimal path is A-C-D, its sub path A-C is not optimal compared with the path A-B. In this example, the optimal substructure property does not hold. However, we can still say the substructure of an optimal structure must also be optimal.

In this case, to search the optimal path, we must store the optimal sub path to all possible intermediates. Or, we can use the greedy algorithm to start the search from the goal node.

imina said...

The graph example by Yin draws incorrect conclusions as according to Principle of Optimality any sub-path within the optimal path is optimal, i.e. the path A-2-C-1-D has to have A-2-C as the most optimal path => if there was any other shorter path (cost 1) to reach C from A we would choose that instead of the present cost 2 path to get a more "optimal" A-1-C-1-D. We can't compare paths to nodes that are not included in the optimal path so it was not fair to compare A-B with A-C.

Subbarao Kambhampati said...

Dear all:
Interesting discussion and examples. Of the various examples, I think Randy's one is short and complete.

If you hate walking on unstable planks, consider the following example (that is a variation on Tuan's):

You are trying to go from phx to LA by road. Let us assume that going on I-10 is the shortest route.

Suppose you already know that over at Blythe, they put traffic barricades and are not allowing people to continue on I-10 unless they have a low-emissions certificate on your car.

The low-emissions certificate is available from Casa Grande, which is on the other side of I-10 from Phx.

If you can't pass through blythe, your alternative is to go via I-8 via san diego which is significantly longer.

Clearly the shortest path involves
going to Casa Grande, getting the emissions certificate and going via Blythe to LA.

This path is not the optimal one for going to Blythe (heck it is not even the optimal one to go to Phx--conisdering that you pass by phx twice).

The "cost" of the path from Blythe to LA depends on whether you already visited Casa Grander or not
(so you have "path-dependent" edge distances).

You can make the mess go away by
defining "State" as {city, certificate} Where city is the city name and certificate is a boolean saying whether you have the emissions certificate or not.

In this new space--which is essentially *twice* the size of the old space (since each city can occur with certificate yes and certificate no), you do have optimal sub-structure; markov states etc. etc.


Gavin Lewis said...


Basically we're looking for the property,

if minimum_path(A to C) includes B, then minimum_path(A to C) = minimum_path(A to B) + minimum_path(B to C)? (and adding the 'certificate' to the state brings the property back?)

E.g., in the road trip example, Blythe is on the minimum trip to LA, but (let -> indicate minimum cost between nodes) PHX -> Blythe + Blythe -> LA is lower than PHX -> LA, but when you add the certificate, you get {PHX, no} -> {Blythe, yes} + {Blythe, yes} -> {LA, *} = {PHX, no} -> {LA, *} (both cases).

Gavin Lewis said...

(note that {Blythe, yes} -> {LA, no} could be defined as infinite, but that's still fine, right?)