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

[brett l. <bre...@gm...>]

On Tue, Aug 9, 2011 at 10:10 PM, Stefan Frey <ste...@we...> wrote:
> 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.
>
>

Also, don't forget... the big difference between Comp Sci theory and
real world implementations, is that in the real world it's
occasionally possible (and completely acceptable) to cheat.

If we can find a "good enough" algorithm that at least gets us mostly
correct answers most of the time while still avoiding a brute force
method, I think that has a certain amount of value. This is especially
true if we continue to allow users to be the final arbitrator on what
their run values really are.

Even Simtex's 1830 game didn't have perfect route calculation
algorithms, and I've found a number of late game positions for which
it would suggest sub-optimal routes.

Personally, if y'all want to pitch in and use Rails to try out
different algorithms and see who can come up with the best one, I
think it would be fantastic. It may even be a good foundation for
supporting AI, which has also been a long-time dream. ;-)

---Brett.