Question 1

There are six cities (City 1-City 6)serviced by a particular bus line.Limited routes are available,and the distance for each of these routes is presented in the table below. 
-If dynamic programming were used to solve for the minimum distance from City 1 to City 6 above,how many stages would there be?
A)6
B)5
C)4
D)3
E)2

Accepted Answer

D

Question 2

In dynamic programming,the decision rules defining an optimal policy give optimal decisions for any entering condition at any stage.

Accepted Answer

In dynamic programming, the decision rules defining an optimal policy give optimal decisions for any entering condition at any stage. This is because dynamic programming involves solving subproblems and storing their solutions, which can then be used to make optimal decisions regardless of the current state.

Question 3

The second step in solving a dynamic programming problem is to solve the last stage of the problem for all conditions or states.

Accepted Answer

In dynamic programming, we solve the problem backward starting from the last stage and move towards the initial stage. Therefore, the second step is to solve the last stage for all conditions or states.

Question 4

Dynamic programming can be applied to a professional tennis player's serving strategy.

Accepted Answer

Dynamic programming can be used to optimize the serving strategy of a professional tennis player by analyzing different possible shot combinations based on the opponent's weak points and previous return patterns. This allows the player to make more efficient use of their energy and increase their chances of winning the point.

Question 5

For the bus line problem above,what are the stages that provide the minimum distance?
A)1-2,2-4,4-6
B)1-2,2-5,5-6
C)1-3,3-4,4-6
D)1-3,3-5,5-6
E)None of the above

Accepted Answer

The answer of For the bus line problem above,what are...

Question 6

Your local paper carrier could make use of the shortest-route technique.

Accepted Answer

The answer of Your local paper carrier could make use...

Question 7

The following information describes a shortest-route problem with the distance in miles.How many stages will this dynamic problem have? 
A)8
B)4
C)3
D)2
E)1

Accepted Answer

A shortest-route problem typically involves finding the most efficient path between two points or multiple points. The problem described only involves distance in miles, indicating that it is a simple shortest-route problem. The number of stages is determined by the number of points between which the shortest route is being calculated. However, the problem does not provide information regarding the number of points, so we cannot determine the exact number of stages. We can, however, assume that the problem involves only two or three points, which would result in 2 or 3 stages. Therefore, the best choice is C, which indicates that the problem has 3 stages.

Question 8

In a shortest-route problem,the nodes represent the destinations.

Accepted Answer

In a shortest-route problem, the nodes represent the destinations that need to be connected through edges or links to find the shortest path between them.

Question 9

In dynamic programming,there is a state variable defined for every stage.

Accepted Answer

In dynamic programming, a state variable is defined for every stage.

Question 10

Both dynamic programming and linear programming take a multi-stage approach to solving problems.

Accepted Answer

Dynamic programming takes a multi-stage approach to solving problems by breaking them down into simpler subproblems and solving each subproblem just once, storing its solution. Linear programming, however, is a mathematical method for determining a way to achieve the best outcome in a given mathematical model and does not inherently involve a multi-stage approach to problem-solving.

Question 11

Table M2-1
The data below is a dynamic programming solution for a shortest route problem. 
-Using the data in Table M2-1,determine the minimum distance from point 1 to point 7.
A)21
B)22
C)23
D)24
E)75

Accepted Answer

To find the minimum distance from point 1 to point 7, we need to look at the value in the bottom-right cell of the table, which is 22. This represents the shortest distance from point 1 to point 7 using the given paths. Therefore, the answer is B, 22.

Question 12

Each item in a knapsack problem will be a stage of the dynamic programming problem.

Accepted Answer

In dynamic programming approach to solve the knapsack problem, each item is considered as a stage that contributes to the overall solution. Therefore, each item is a stage of the dynamic programming problem.

Question 13

Dynamic programming can only be used to solve network-based problems.

Accepted Answer

Dynamic programming can be used to solve a wide range of problems, not limited to network-based problems. It is a general technique for solving optimization problems by breaking them down into smaller subproblems and solving each subproblem only once.

Question 14

A transformation changes the identities of the state variables.

Accepted Answer

A transformation changes the values of the state variables, but not their identities. The identities of the state variables remain the same before and after the transformation.

Question 15

Linear programming is typically applied to problems wherein one must make a decision at a specified point (or points)in time.Dynamic programming is typically applied to problems wherein one must make a sequence of decisions.

Accepted Answer

Linear programming is used for making decisions at a specific point, while dynamic programming is used for sequential decision-making problems.

Question 16

Subproblems in a dynamic programming problem are called stages.

Accepted Answer

This is true. Subproblems in dynamic programming are often broken down into stages or phases in order to tackle them systematically.

Question 17

For the bus line problem above,what is the minimum possible distance to travel from City 1 to City 6?
A)26
B)20
C)18
D)22
E)None of the above

Accepted Answer

The minimum possible distance to travel from City 1 to City 6 is 18, assuming the problem involves finding the shortest path in a network or graph.

Question 18

For knapsack problems,s_n-1 = a_n × s_n + b_n × d_n + c_n is a typical transformation expression.

Accepted Answer

This expression represents the recursive formula for the knapsack problem, where a, b, and c are the values of the items, s and d are the binary variables indicating whether an item is selected or not, and n represents the item number. Therefore, this statement is true.

Question 19

In a shortest-route problem,the limit on the number of allowable decision variables from one node to another is the number of possible nodes to which one might yet travel.

Accepted Answer

In a shortest-route problem, the limit on the number of allowable decision variables from one node to another is the number of possible nodes to which one might yet travel. This is because the decision variables represent the choices of which node to move to next in order to reach the destination, and the number of possible nodes to travel to is the limit on those choices.

Question 20

The problem that NASA has in determining what types of cargo may be loaded on the space shuttle is an example of a knapsack problem.

Accepted Answer

The knapsack problem involves determining the best combination of items to fit a specific capacity, which is similar to the problem of determining what types of cargo can be loaded on the limited space shuttle.

Quiz 17: Dynamic Programming