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%)