Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 3: Problem 11

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.

Short Answer

Expert verified
A chess game is an example where the Principle of Optimality doesn't apply. Here, every move is highly dependent not only on the current scenario but also on potential future scenarios. This dynamic nature of decision making in the game breaks the Principle of Optimality, making it not suitable for being solved by dynamic programming.

Step by step solution

01

Explanation of the Principle of Optimality

The Principle of Optimality applies when an optimal strategy can be pieced together from optimal solutions to subproblems. This effectively means: If an optimal solution contains within it optimal solutions to subproblems, then the Principle of Optimality applies. For example, the problem of finding the shortest path from A to B, assuming a path from A to B goes via C, the shortest path from A to B is the shortest path from A to C plus the shortest path from C to B.
02

Identify a problem where the Principle of Optimality does not apply

Contrarily, if an optimal solution contains within it subproblems for which there exist solutions that are not optimal, then the principle does not apply. A typical example of a situation where this principle is not working is a problem that involves a non-stationary decision, which means that the decision at a certain step depends not only on the state and control at that step, but also on the time or stage itself. Say, for example, in a chess game where the best move could worsens based on the subsequent decisions of the opponent.
03

Justification

In this example, the Principle of Optimality doesn't hold because making the best decision now doesn't necessarily contribute to an optimal solution overall. This is because the advantage of every possible move in chess isn’t just dependent on the current scenario, but also on every potential future scenario. Therefore, this breaks the Principle of Optimality and makes it incompatible with dynamic programming, as dynamic programming requires the Principle of Optimality to function.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that the number of binary search trees with \(n\) keys is given by the formula \(\frac{1}{(n+1)}\left(\begin{array}{l}2 n \\ n\end{array}\right)\)

Create the optimal binary search tree for the following items, where the probability occurrence of each word is given in parentheses: CASE (.05), ELSE (.15), END (.05), IF (.35), OF (.05), THEN (.35)

How many different binary search trees can be constructed using six distinct keys?

Find an efficient way to compute \(\sum_{m=i}^{j} p_{m},\) used in the Optimal Binary Search Tree algorithm (Algorithm 3.9).

Find the optimal order, and its cost, for evaluating the product \(A_{1} \times A_{2} \times A_{3} \times A_{4} \times A_{5}\) where $$\begin{aligned} &A_{1} \text { is }(10 \times 4)\\\ &A_{2} \text { is }(4 \times 5)\\\ &A_{3} \text { is }(5 \times 20)\\\ &A_{4} \text { is }(20 \times 2)\\\ &A_{5} \text { is }(2 \times 50) \end{aligned}$$
See all solutions

Recommended explanations on Computer Science Textbooks

Theory of Computation

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Systems

Read Explanation

Game Design in Computer Science

Read Explanation

Computer Programming

Read Explanation

Big Data

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free