diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /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.mail | 195 |
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. + |