An attempt to obtain a unified algorithm for dynamic programming
Jsun Yui Wong
The followimg example is the stagecoach problem (the shortest route problem ) from Jensen [4, pp. 102-103]. It is essential that one appreciates the network (picture) on p. 102 [4]. This illustration is similar to Wagner’s stagecoach problem (a prototype example for dynamic programming except that stages are not used in the present paper [3, Hillier and Lieberman, pp. 425-430]. Anderson et al. [1, pp. 820-829], Ecker and Kupferschmid [2 , pp. 347-352], Hillier and Lieberman [3, pp. 424-433], Wagner [5, pp. 262-270], and Wikipedia [6] are also very informative.
{6}
{3} {8}
{1} {5} {9}
{2} {7}
{4}
Figure 5.1 Road Network Example for Dynamic Programming, from [4, p. 102], (simplified for illustration only)
Some small changes shown below have been added to the original Figure 5.1 [4, p. 102], P01, P02, P03, …, P09, which are described in line 351 through line 397. P05, for example, stands for the shortest distance from P05 to the destination point, P01.
P04
{6}
P07 P02
{3} {8}
P09 P05 P01
{1} {5} {9}
P08 P03
{2} {7}
P06
{4}
P01 to P09 are described in line 351 to line 397.
To solve the problem above, the following computer program uses the Principle of Optimality of Dynamic Programming, which is “If a particular node is on the optimal route, then the shortest path from that node to the end is also on the optimal route, “ Anderson, Sweeney, and Williams [1, p. 821].
0 REM DEFDBL A-Z
1 REM DEFINT I, J, K
2 DIM B(99), N(99), A(2002), G(128), J44(222), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J(99), AA(99), HR(32), HHR(32), LHS(44), PLHS(44), LB(22), UB(22), PX(44), PN(22), NN(22)
85 FOR JJJJ = -32000 TO 32000
88 RANDOMIZE JJJJ
351 P01 = 0
355 P02 = 9 + 0
358 P03 = 6 + 0
362 P04 = 2 + 9
369 P05 = 5 + 6
373 P06 = 9 + 6
378 P07 = 3 + 11
389 P08 = 7 + 11
397 P09 = 8 + 14
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with qbv1000-win [6], and the complete output through JJJJ=-31998 is as follows:
0 9 6 11 11
15 14 18 22 -32000
0 9 6 11 11
15 14 18 22 -31999
0 9 6 11 11
15 14 18 22 -31998
So path {1}-{3}, {3}-{5}, {5}-{7}, {7}-{9} is an optimal path of length 22.
The wall-clock time (NOT cpu time) for producing the output above was 2 seconds when one counts from “Starting program…”. The computer system used here is the same as that used by the preceding paper.
References
[1] D.R. Anderson, D. J. Sweeney, I. A. Williams, An introduction to management science: quantitative approaches to decision science, ninth edition, South-Western College Publishing, 2000.
[2] J. G. Ecker, M. Kupferschmid, Introduction to operations research, John Wiley and Sons, Inc., 1988.
[3] F. S. Hillier, G. J. Lieberman, Introduction to operations research, sixth edition, McGraw Hill, Inc.
[4] Paul A. Jensen, Microsolve/Operations Research, Holden-Day, Oakland, California.
[5] Harvey Wagner, Principles of operations research, second edition, Prentice –Hall, Inc., 1975.
[6] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.
Comments