summaryrefslogtreecommitdiff
path: root/web/spiderweb/src/turing+/example.mail
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /web/spiderweb/src/turing+/example.mail
Initial commit
Diffstat (limited to 'web/spiderweb/src/turing+/example.mail')
-rw-r--r--web/spiderweb/src/turing+/example.mail195
1 files changed, 195 insertions, 0 deletions
diff --git a/web/spiderweb/src/turing+/example.mail b/web/spiderweb/src/turing+/example.mail
new file mode 100644
index 0000000000..c1513a4b93
--- /dev/null
+++ b/web/spiderweb/src/turing+/example.mail
@@ -0,0 +1,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.
+