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

[Bill R. <ro...@gm...>]

On 2011-08-10, at 12:54 , John A. Tamplin wrote:

> On Wed, Aug 10, 2011 at 12:04 AM, Bill Rosgen <ro...@gm...> wrote:
>> 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.

But on a cubic planar graph the Hamiltonian path problem remains NP-complete (as shown in the paper of Garey, Johnson, and Tarjan).  Cubic planar graphs can be represented as 18xx maps.  The best path on such a map, if one exists, is the one that visits all cities.  This implies that if there is a general algorithm for 18xx maps that works in the case of one company with one token and one diesel, it also can be used to decide whether or not a cubic planar graph has a Hamiltonian path.

Bill