1. Consider the following statements about solving dynamic programming problems.
ID: 3216163 • Letter: 1
Question
1. Consider the following statements about solving dynamic programming problems. Label each statement as true or false, and then justify your answer.a. After completing the solution procedure, if a nonoptimal decision is made by mistake at some stage, the solution procedure will need to be reapplied to determine the new optimal decisions at the subsequent stages.
b. Once an optimal solution has been found for the overall problem, the information needed to specify the optimal decision at a particular stage is the state at that stage and the decisions made at preceeding stages.
c. Dynamic programming will only provide one optimal solution to a problem.
Explanation / Answer
Statement a. After completing the solution procedure, if a nonoptimal decision is made by mistake at some stage, the solution procedure will need to be reapplied to determine the new optimal decisions at the subsequent stages.
Solution: This statement is False. According to Ballman principle of optimality, if any decision at any stage is going wrong, a corrective action is taken independently for the remaining stages. So if a solution is non optimal at some stages, solution procedure need not be reapplied, instead of that, corrective actions has to be taken at the subsequent stages.
Statement b. Once an optimal solution has been found for the overall problem, the information needed to specify the optimal decision at a particular stage is the state at that stage and the decisions made at preceeding stages.
Solution: This statement is true according to the Optimal policy of the Dynamic Programming problems. According to this policy, optimal decision is achieved by making most effective use of resources in the stages and decision made at preceeding stages,
Statement c. Dynamic programming will only provide one optimal solution to a problem.
Solution: True. Dynamic Programming goes through all possible solutions and finally picks up the best solution.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.