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

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

On 2011-08-09, at 15:41 , Stefan Frey wrote:
> John,
> thanks for your comments. 
> Good thing to know that first you were able to solve it (I hate working on 
> unsolvable problems in my free time) and second that it did not take anything 
> too extraordinary graph theory stuff to solve it. Third it shows the direction 
> to go to adjust the graph to incorporate the train constraints (I have some 
> ideas how to do that). An alternative might be to use a linear programming 
> algorithm to solve the flow problem which (potentially) makes adding other 
> constraints easier.
> 
> Can I ask you for reviewing my proposals, this might even help you retrieve 
> the ideas you had 24 years ago.
> Stefan

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.

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.

Bill Rosgen