Question

1. Find an optimization problem in which the principle of optimality does not apply and therefore that the optimal solution cannot be obtained using dynamic programming. Justify your answer.

Answer 1

A problem where the optimal solution cannot be determined using dynamic programming is the longest path problem i.e. the longest simple path without cycles between two nodes of a graph. This is because there is no optimal substructure property of it or the principle of optimality does not hold here because in an optimal solution of the problem the subproblems may or may not be optimal.

For example, consider the graph below:-

Here say from node q to node t there are two longest paths i.e q->r->t and q->s->t but say in the solution q->r->t, the subproblems i.e longest path between r to t and longest path between q to r is not optimal as the longest path between r to t is not r->t but r->q->s->t and longest path between q to r is q->s->t->r.