Consider the following network problem and the associated figure from the textbook, the objective is to find the longest distance from start to finish.
There are four stages that have been taken from the origin to the destination in the given problem. The first stage is the origin or the Start. The second stage is the next step from origin towards the destination. It can take any of the two states or.
Now at stage-2 contains states and.
At third stage are the next possible nodes in the route. So the stage-3 has three states and. As move further, the possible nodes in the route are and.
At states form the stage-4. The next stage will then have just one more step before the finish. This is stage-5 and it has states and. Thus finally reach the Finish of the network through these stages and states in the given dynamic programming formulation
In the dynamic programming problem, start from the destination node and compute the longest distance at each stage. Eliminate the shorter routes at each stage in the process. In the given figure, it is given that
To obtain compute the distance of path– Finish.
To obtain compute the distance of path– Finish.
To obtain compute the distance of path– Finish.
To obtain compute the distance of path– Finish.
Now at stage-3 computations,
To obtain compute the largest distance from paths– Finish and – Finish.
To obtain compute the largest distance from paths– Finish and – Finish.
To obtain compute the largest distance from paths– Finish and – Finish.
Now at stage-2, to obtain the value of
Similarly find,
Finally the stage-1 computations,
So the graphical solution of the dynamic programming problem is,
So the longest path from start to finish is or, both giving the longest time as 17.
The finish node can be reached through either state. Therefore at stage-5 the solution is,
n= 5 |
s |
f* 5 (s) |
x 5 * |
J |
5 |
J |
|
K |
4 |
K |
|
L |
7 |
L |
As we proceed to stage-4, we compute the table for. So,
n= 4 |
s |
f 4 (s) |
f* 4 (s) |
x 4 * |
||
J |
K |
L |
||||
F |
6 |
- |
- |
6 |
J |
|
G |
- |
8 |
- |
8 |
K |
|
H |
- |
10 |
- |
10 |
K |
|
I |
- |
- |
9 |
9 |
L |
Further for stage-3 we have table for as,
n= 3
s
f 3 (s)
f* 3 (s)
x 3 *
F
G
H
I
C
10
12
-
-
12
G
D
-
-
12
11
12
H
E
-
-
13
12
13
H
The next step is to compute the table for n = 2 at stage-2,
n= 2 |
s |
f 2 (s) |
f* 2 (s) |
x 2 * |
||
C |
D |
E |
||||
A |
17 |
17 |
- |
17 |
C or D |
|
B |
- |
- |
16 |
16 |
E |
To proceed further, node can go to states A and B so,
n= 1 |
s |
f 1 (s) |
f* 1 (s) |
x 1 * |
|
A |
B |
||||
Start |
17 |
16 |
17 |
A |
Thus the longest path is or with longest duration as.
Problem No. 10.2-3. Consider the following project network (as described in Sec. 9.8), where the number...
this is a dynamic programming problem Question 3 - Dynamic Programming 18 marks total a) Consider an acyclic network defined by a set of nodes N and a set of arcs A. We know the travel time for each arc and the value for visiting each node We wish to construct a maximum value path from a specified origin to a specified destination, subject to the constraint that the total travel time of the path is no more than a...