Re: [Rails-devel] Route calculation for huge runs

[Stefan F. <ste...@we...>]

see below

On Wednesday, August 10, 2011 06:54:58 am John A. Tamplin wrote:
> On Wed, Aug 10, 2011 at 12:04 AM, Bill Rosgen <ro...@gm...> wrote:
> > Is the problem really solvable?  The planar cubic hamiltonian path
> > problem is NP-complete (see Garey, Johnson, and Tarjan 1976, which seems
> > to be available at
> > http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20p
> > lanar%20hamiltonian.pdf).  The title of the paper involves cycles, but
> > the text on page 713 claims it holds also for paths.  I have not
> > verified the results of the paper, but it appears in a very good journal
> > and so is likely to be correct.
> > 
> > I think the problem is equivalent to optimizing the run of only one
> > diesel on such a graph.  Given any planar graph with degree 3, it can be
> > implemented as an 18xx map with cities as vertices and track as edges,
> > though the map may get pretty large (though still polynomial in the
> > number of cities).  Imagine such a map with only one company (with a
> > token somewhere) that owns one diesel.  That train can hit every city if
> > and only if there is a Hamiltonian path in the original graph.
> 
> I don't think it is equivalent to Hamiltonian path on an arbitrary graph,
> and there are polynomial solutions for Hamiltonian path on many types of
> restricted graphs.  Also, you aren't actually asking is there a path that
> visits all cities but instead what is the best path that can be obtained.
> 
> > Practically this doesn't say that much, as we don't have arbitrarily
> > large graphs, and many of the trains in 18xx games run for some constant
> > length, but it might imply that a general purpose poly-time algorithm is
> > going to be difficult to find.
> 
> I agree, in particular I think being able to skip stops and double an
> arbitrary stop are things that would make anything short of brute
> force intractable.


This reminds me of getting involved into discussions of asymptotic behaviors 
by the econometrics theory people if I ask a question how to solve an 
econometric problem in an empirical applied context: I feel intimidated and 
stupid ;-)

And usually the number of answers exceeds the number of questions by a large 
multiple...

However what I take from this is that most likely that a polynomial solution 
exists (as John was able to find one 24 years ago) to the diesel/12 train 
scenario and that the existing algorithm covers the exotic train cases.