chiark / gitweb /
Document all of the upheaval.
authormdw <mdw>
Fri, 7 Mar 2003 00:47:13 +0000 (00:47 +0000)
committermdw <mdw>
Fri, 7 Mar 2003 00:47:13 +0000 (00:47 +0000)
README

diff --git a/README b/README
index 102cdd7..62aba1d 100644 (file)
--- a/README
+++ b/README
@@ -32,9 +32,10 @@ RIGHT ON COMMAND-LINE
 
          * If you can't build `pkgIndex.tcl', run `tclsh' and say
 
-             % pkg_mkIndex -verbose -direct . elite.so elite.tcl
+             % pkg_mkIndex -verbose -direct -load Vec . \
+               elite.so vec.so graph.so elite.tcl
 
-           to it.  (Use `elite.dll' if you're on Windows.)  Say
+           to it.  (Use `elite.dll' etc. if you're on Windows.)  Say
 
              % set tcl_pkgPath
 
@@ -80,8 +81,9 @@ RIGHT ON COMMAND-LINE
 
          * a glob pattern (a string containing `*' and `?' wildcards,
            matching any substring or any single character,
-           respectively), for the first planet whose name matches the
-           pattern; or
+           respectively), optionally followed by `/N' for some positive
+           integer N, for the Nth (default first) planet whose name
+           matches the pattern; or
 
          * a string `GAL:P', where GAL is a galaxy-spec and P is a
            planet-spec, for the planet P in galaxy GAL.
@@ -145,14 +147,15 @@ RIGHT ON COMMAND-LINE
 
 
 
-  elite-path [-g GALAXY] [-w WEIGHT] [-a ACC] PLANET PLANET ...
+  elite-path [-g GALAXY] [-d DIST] [-w WEIGHT] [-a ACC] PLANET PLANET ...
 
        Computes a route through a GALAXY (default is standard galaxy
        1), starting at the first PLANET listed, via the second, via the
        third, etc., and ending at the last.  For each planet you're
        meant to stop at on the way, a summary line is printed giving
        the planet's name, position, government type, economy type and
-       tech level.
+       tech level.  The `-d' option gives the ship's hyperspace range
+       in lightyears.
 
        You can affect how elite-path selects its routes using the `-w'
        option.  The default is to minimize the number of hops.  Other
@@ -383,6 +386,82 @@ RIGHT ON COMMAND-LINE
        by minimum, maximum or average profit (highest at the top).
 
 
+  elite-salesman [-OPTIONS] GALAXY [START]
+
+       Solver for the Travelling Salesman Problem.  Plots a route
+       around (a connected subgraph of) GALAXY.  The START planet has
+       two related purposes:
+
+         * It identifies which subgraph to tour.  If the galaxy is split
+           into mutually unreachable subsets, it's obviously impossible
+           to visit the whole lot.
+
+         * If you specify the `-nocycle' option (see below), then START
+           is the starting place for the tour.
+
+       The following options affect the problem to be solved:
+
+       -w WEIGHT       Choose how to weight journeys.  This has the
+                       same meaning as in `elite-path'.  The default is
+                       to minimize the number of hops.
+
+       -d DIST         Distance we can travel in one hop, in
+                       lightyears.
+
+       -cycle          Find a cyclic route through the galaxy (i.e., so
+                       that when you finish, you come back to where you
+                       started).  You can use a cyclic solution to tour
+                       a galaxy from any starting point.  This is the
+                       default.
+
+       -nocycle        Find a route which begins at START, covers
+                       all the planets, and then stops.  Presumably you
+                       use a galactic hyperdrive to get to the next
+                       galaxy, or something.
+
+       The solution is displayed as a list of planet summaries.  An
+       indented line indicates a world you have to visit just to get
+       somewhere else.
+
+       The program doesn't compute an optimal solution -- doing so
+       would be very slow indeed, since the Travelling Salesman Problem
+       is NP complete.  Instead, it uses a technique called `simulated
+       annealing' to try to home in on a good solution.  There are a
+       number of options you can use to tweak this process.  The
+       default settings produce relatively good answers, but take about
+       five minutes to run.  Try playing with them, and see what sorts
+       of results you get.
+
+       -temp           The initial temperature of the system.  The
+                       temperature controls how willing the process is
+                       to accept a move which increases the journey
+                       cost -- a high temperature means that `bad'
+                       moves are more likely to be accepted.  The
+                       temperature should initially be greater than the
+                       maximum possible cost of exchanging two hops on
+                       the route.  The default is 1024, for no
+                       particularly good reason.
+
+       -cool           Cooling factor.  Each cooling cycle, the
+                       temperature is reduced by this factor.  It
+                       should be a little greater than 1.  The default
+                       is 1.001.  Smaller values (nearer 1) take longer
+                       but tend to produce better results.
+
+       -inner          Number of swapping iterations to do each cooling
+                       cycle.  The default is 10000.
+
+       -dead           The number of `dead' cycles (ones in which we
+                       never make an improving move) before we give up
+                       and accept the solution.  The default is 200,
+                       which seems to work OK.
+
+       Simulated annealing is an interesting technique which is
+       applicable to a wide variety of optimization problems.  There
+       are some decent descriptions on the 'net -- try asking Google
+       about it.
+                       
+
 3. The graphical editor
 
   elite-editor [GALAXY | FILE | -jameson]
@@ -476,7 +555,7 @@ RIGHT ON COMMAND-LINE
        unrewarding) or pirates (risky and tedious), and start trading
        food and other cheap items.
 
-$Id: README,v 1.6 2003/03/04 10:25:43 mdw Exp $
+$Id: README,v 1.7 2003/03/07 00:47:13 mdw Exp $
 \f
 Local variables:
 mode: text