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

[John A. T. <ja...@ja...>]

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%20planar%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.

-- 
John A. Tamplin