How to find out if an problem is amenable to the principle of optimality:
If we can find an algorithm to solve the problem, such that the optimal solution to the "sub-problem" can be found using the same algorithm, then we say that the the <Algorithm, Problem> tuple is amenable to the "principle of optimality".
for which principle of optimality applies, we can try to think through whether the problem necessarily needs a dynamic programming kind of a solution, or a greedy one will do.
Have a look at this as a template for proving that greedy algorithms are a good choice for a particular optimization problem, and this as an intro to the concept of knowing/finding out "when can greedy algorithms work i.e. for what structure of problems i.e. apparently (i will revisit this), "Most problems for which greedy approach works can be formulated in terms of Weighted Matriods"
If we can find an algorithm to solve the problem, such that the optimal solution to the "sub-problem" can be found using the same algorithm, then we say that the the <Algorithm, Problem> tuple is amenable to the "principle of optimality".
- e.g. lets say the Problem: Find the Shortest path for a graph with no negative edges (but with cycles) Let's choose Dijkstra's algorithm. We observe that if we run the same algorithm on any 2 points on this shortest path say path1, we will see that the newly found shortest path, say path2 is a subset of path1. Thus <Shortest path on a graph with no negative edges, Dijkstra> satisfies principle of optimality.
- <Longest path on a graph with no negative edges, Dijkstra> however is not amenable to the principle of optimality because e.g. imagine the longest path on a ring-like graph say made up of a-b-c-d-e-a . The longest path from a-d is a-b-c-d (and not a-e-d). And, the longest path from b-d is not b-c-d, but it is 'b-a-e-d'. This path cannot be found using Dijkstra. Therefore <Longest path on a graph with no negative edges, Dijkstra> does not satisfy principle of optimality. Of course <Longest path on a graph with no negative edges, some other algo A> may satisfy principle of optimality ! Is there any such algo? I do not know.
Have a look at this as a template for proving that greedy algorithms are a good choice for a particular optimization problem, and this as an intro to the concept of knowing/finding out "when can greedy algorithms work i.e. for what structure of problems i.e. apparently (i will revisit this), "Most problems for which greedy approach works can be formulated in terms of Weighted Matriods"
