Tuesday, June 27, 2006

Problems for which "Principle of Optimality" does not hold??

For many optimization problems we take for granted that DP (Dynamic Programming works). But the first thing we need to check before we use the DP technique is the "Principle of Optimality".
o If the aim of a descision sequence(d1,d2,d3,d4........dn) is to minimize/maximize some objective function, then for any di , 1<=i<=n , the subsequence (di,di+1,....dn) should also minimize/maximize the objective function respectively.
o One problem for which the "Principle of Optimality" is when we have a KNAPSACK problem which both negative and postive profits, we might well ask ourself if a Item has negative profit then why we select that Item? well you might have forgotten the other factor which is the size of item...
I dont know of any other problems.

No comments: