1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
From att!surya.ho.att.com!ko Fri Mar 22 10:31:23 1991
Received: from Princeton.EDU (Princeton.EDU.) by fs.Princeton.EDU (4.0/1.105)
id AA21961; Fri, 22 Mar 91 10:31:21 EST
Received: from att.UUCP by Princeton.EDU (5.61++/2.69/princeton)
id AA18354; Fri, 22 Mar 91 10:31:17 -0500
Received: from spark.ho.att.com by surya.ho.att.com (4.1/SMI-4.1)
id AA09832; Thu, 21 Mar 91 17:27:35 EST
Date: Thu, 21 Mar 91 17:27:35 EST
From: surya.ho.att.com!ko
Message-Id: <9103212227.AA09832@surya.ho.att.com>
Received: by spark.ho.att.com (4.1/SMI-4.1)
id AA06596; Thu, 21 Mar 91 17:35:07 EST
To: att!att.uucp, nr@Princeton.EDU
Subject: Example file
Status: RO
Here is an example Turing Web file. Note: I have made a small
modification to "webkernel.tex" by adding \date and \author macros.
These are used in the file that follows. I include the modification
below:
\def\rhead{\.{WEB} OUTPUT} % this running head is reset by starred sections
\def\title{} % an optional title can be set by the user
% The following two are optional, and can be set by the user.
% (Kostas Oikonomou, Nov. 1990.)
\def\author{}
\def\date{}
\def\topofcontents{\centerline{\titlefont\title}\vskip1cm\centerline{\author}
\vskip0.4cm\centerline{\date}\vfill} % this material will start the table of contents page
\def\botofcontents{\vfill} % this material will end the table of contents page
----------------------------- paths.web ----------------------------------------
\def \title {General Least-Cost Paths in Graphs}
\def \author {Kostas N. Oikonomou}
\def \date {August 1990}
% See the TeXbook, p.154 for this!
\font \bbb = msbm10
\newfam\msbmfam
\textfont\msbmfam=\bbb
\def \Nat {{\fam\msbmfam N}}
\def \Real {{\fam\msbfam R}}
\def \c#1{\vert#1\vert}
@* The {\it paths\/} module.
Let $G$ be a complete directed graph on $V=\{0,1,\ldots,n\}$. The edges
are $E=\{(i,j)\mid i<j\}$. Let each edge have a cost (length) $\ell(i,j)$.
The cost of a {\it path\/} from $i$ to $j$ may be defined in various ways,
as a function of the costs (lengths) of the edges that make it up. For
example, it could be the sum of the lengths of the edges, it could be the
length of the longest edge, the length of the shortest edge, etc. We are
interested in finding best (least-cost) paths in $G$ from $i$ to $n$, with
a specified number $m$ of edges.
We will be able to do this efficiently if the function $C$ defining the
cost of a path $i,i_1,\ldots,i_{m-1},j$ from $i$ to $j$ is s.t. it satisfies
the optimality principle of dynamic programming. That is $C$ must be s.t.
$$
\min_{(i_1,\ldots,i_{m-1})} C(i,i_1,\ldots,i_{m-1},j) = \min_{i_1}
f \bigl( C(i,i_1), \min_{(i_2,\ldots,i_{m-1})} C(i_1,\ldots,i_{m-1},j) \bigr), \eqno (1)
$$
where $f(\cdot,\cdot)$ is some function, e.g. ``$+$'', and where the
``min'' could be replaced by ``max''. (An interesting recent reference on
generalizations of the optimality principle and related subjects is {\sl
Generalized Dynamic Programming for Stochastic Combinatorial
Optimization\/}, Carraway et al., Op. Res., Vol. 37, No. 5, 1989.)
Although our $G$ is directed, so that the minima in (1) are to be taken
over sequences such as $i<i_1<\cdots<i_{m-1}<j$, it should be clear that
(1) also applies to a complete undirected $G$, if the minima are taken over
unconstrained paths.
Module |paths| contains a procedure |least_cost| which, given the function
$f$ appearing in (1), returns in $c^*(1..m)$ the cost of the best 0-to-$n$
paths in $G$ with $1,2,\dots,m$ edges. The function |relation| expresses a
relation between $c^*(k)$ and $c^*(k-1)$, for checking purposes; if no such
relation is known, define the function to be identically true. The module
also contains a procedure |least_cost_path|, which returns in $I(0 .. k)$ the
vertices on the best $k$-edge path from 0 to $n$, for any $k\le m$.
@(paths.ch@> =
@t\% The ``include'' allows {\tt paths.ch} to be used unchanged by different parent modules:@>
include "paths.parent"
stub module paths
import (n, m)
export (least_cost, least_cost_path)
procedure least_cost (var c_star : array 1 .. * of real, function l(i,j : nat) : real, @| function f(c1,c2 : real) : real, function relation (c1,c2 : real) : boolean)
procedure least_cost_path (k : nat, var I : array 0 .. * of nat)
end paths
@ To find the paths and their costs, define
$$
c_k(i) = \min_{j:i<j<n} (\hbox{\rm cost of the best $i$-to-$n$ path with
$k\ge 1$ edges}).
$$
It follows from (1) that $c_k(i)$ satisfies the recurrence
$$
c_k(i) = \min_{j:i<j<n} f\bigl(\ell(i,j), c_{k-1}(j)\bigr), \qquad k\ge 2.
\eqno (2)
$$
This recurrence can be solved by noting that
$$
\forall i,\quad c_1(i) = \ell(i,n).
$$
Using this in (2) allows us to compute $c_2(i)$ for all $i$, and so on. To
conserve memory space, note that we don't really need to have a matrix
$c(k,i)$, but just two arrays |c_k| and |c_k_1| to hold $c_k(\cdot)$
and $c_{k-1}(\cdot)$.
Besides computing the cost of the best 0-to-$n$ paths, we also want to know
what these paths are. To do this, it suffices to remember for each $i$ and
$k$ the $j=J(k,i)$ that minimizes the r.h.s. of (2).
@
@<Compute $c_k(i)$ and $J(k,i)$ for all $i$@> =
for i : 0 .. n-2
c_k(i) := infinity
for j : i+1 .. n-1
const c := f(l(i,j), c_k_1(j))
if c < c_k(i) then
c_k(i) := c
J(k,i) := j
end if
end for
end for
@
@<Solve recurrence (2)@> =
const infinity := 10.0 ** 200
for k : 2 .. m
@<Compute $c_k(i)$...@>
@<Remember $c_k(0)$ and check its relationship with $c_{k-1}(0)$@>
@<Set $c_{k-1}(\cdot)$ to $c_k(\cdot)$@>
end for
@
@<Procedure |least_cost|@> =
body procedure least_cost
c_star(1) := l(0,n)
@<The arrays |c_k| and |c_k_1|@>
@<Solve recurrence (2)@>
end least_cost
@ Procedure |least_cost_path| calculates in $I_0,\dots,I_k$ the
vertices on the least-cost path from 0 to $n$ in $G$ with $k$ edges. It
uses the function $J(k,i)$ computed by procedure |least_cost|.
@<Procedure |least_cost_path|@> =
body procedure least_cost_path
I(0) := 0
I(k) := n
for i : 1 .. k-1
I(i) := J(k-(i-1), I(i-1))
assert I(i) > I(i-1)
end for
assert I(k-1) < n
end least_cost_path
@
@(paths.ch@> +=
body module paths
var J : array 2 .. m, 0 .. n-2 of nat
@<Procedure |least_cost|@>
@<Procedure |least_cost_path|@>
end paths
@ We store $c_k(0)$, the cost of the best 0-to-$n$ $k$-edge path, in
$c^*(k)$. If we know a relationship between the cost of the best path with
$k$ edges and that of the one with $k-1$ edges, e.g. $c^*(k)>c^*(k-1)$, the
function |relation| allows us to check that it holds.
@<Remember...@> =
c_star(k) := c_k(0)
assert relation (c_star(k), c_star(k-1))
@
@<The arrays |c_k| and |c_k_1|@> =
var c_k, c_k_1 : array 0 .. n-1 of real
for i : 0 .. n-1 % Here k = 2.
c_k_1(i) := l(i,n)
end for
c_k(n-1) := l(n-1,n) % Here k = 1 and this never changes.
@
@<Set $c_{k-1}(\cdot)$...@> =
for i : 0 .. n-2
c_k_1(i) := c_k(i)
end for
@* Index.
|
