## Description

Dynamic Programming

Date:

Programme:

Group Member Name :

( Student ID )

( )

( )

( )

( )

( )

Arrangement:

Maximum 5 students in a group.

Introduction:

Dynamic programming (DP) is a general approach in making a sequence of interrelated

decisions to obtain an optimal solution. We can describe the general characteristics, but

the details depend on the application. Fundamentally, DP is recursive, like a computer

routine that calls itself, adding information to a stack each time, until certain stopping

conditions are met. Once stopped, the solution is unraveled by removing information

from the stack in the proper sequence.

Procedures of DP:

1. Define a small part of the whole problem and find an optimum solution to this

small part.

2. Enlarge this small part slightly and find the optimal solution to the new problem

based the previously found optimal solution.

3. Continue with Step 2 until you have enlarged sufficiently that the current problem

encompasses the original problem. When this problem is solved, the stopping

conditions will have been met.

4. Track back the solution to the whole problem from the optimal solutions to the

small problems solved along the way.

2

Scenario:

Assuming that PolyU ITS is going to decide how to maintain banks of disk drives at four

separate locations for security reasons, with probabilities of failure that depend on the

locations. For additional security, ITS can also provide backup disk drives in each

location. However, there are only FOUR backup disk drives available at all, and ITS

wants to determine where to put them to minimize the overall probability that all four

locations will fail simultaneously with the constraint that each location can assign not

more than THREE backup drives. The estimated probabilities of failure are summarized

in the following table.

Location

Backup

drives

assigned

A B C D

0 0.20 0.30 0.40 0.50

1 0.15 0.20 0.25 0.30

2 0.05 0.10 0.10 0.15

3 0.025 0.05 0.02 0.10

For example, if no backup drive is going to be assigned, then the overall probability of

simultaneous failure of all four locations is 0.20 x 0.30 x 0.40 x 0.50 = 0.012.

1. What is the recursive relationship between the optimal decision at a stage and a

previous optimum decision? (10%)

Hint: Define the recursive function and related variables such as:

Let i be the current stage,

di be the number of backup disk drives,

xi be the decision of backup disk drives to be assigned to this location.

Pi(xi) be the probability of failure at stage i given that xi backup disk drives

are being assigned,

….

The recursive function linking up two stages is:

fi(di)=min…..

2. Calculate the optimal solution that has a minimum probability of failure with

details procedures. (40%)

3. Unwind the recursion to find out the actual backup drives assignment. (10%)

4. Elaborate your observations regarding the favor of using of dynamic

programming with an example? (30%)

5. Format and presentation. (10%)

## Reviews

There are no reviews yet.