Q6Design and Analysis of Algorithms
Question
2 marks
What is Optimal Substructure?
Answer
Optimal Substructure means the optimal solution to a problem contains optimal solutions to its subproblems.
A problem exhibits Optimal Substructure if an optimal solution to the problem can be constructed efficiently from optimal solutions to its subproblems. This property is a necessary condition for both Dynamic Programming and Greedy algorithms to work correctly.
Examples: Shortest path exhibits optimal substructure — if the shortest path from u to v goes through w, then the subpath from u to w and from w to v must also be shortest paths. 0/1 Knapsack and LCS also have optimal substructure. Note: Longest simple path does NOT have optimal substructure.