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

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

On Sat, Mar 12, 2011 at 4:02 PM, Aliza Panitz <ali...@gm...>wrote:

> Rails 1.4.1, 1856, CGR running 3 Diesels. (This is not completely
> absurd -- my plausible choices for the CGR in this game are 5,6; D,5;
> and D,D,D.  The money doesn't work out right for D,D.  This is a very
> odd game where the CGR formed with 4,5,6, and ten excellent tokens)
>
> At first, run calculations were taking 15-20 minutes on a T60 laptop
> running Windows XP.  Now, though, I've got a calculation that's been
> running for well over an hour, taking 45-55% of my CPU the whole time.
> The map isn't that much more developed! [added - it finally completed.
>  $1440 per 10% share.]
>
> Earlier, I was all ready to file a Rails bug because I could clearly
> see a better route than what was displayed, but I stepped away from my
> computer and when I came back, a better run was shown instead.  So,
> one simple request:  when Rails is still calculating a run, there
> should be a note on the screen saying something like "route
> calculation in progress."  (Screen shot attached.  Even I can quickly
> see that the light blue train should run towards the WGB tokens for an
> extra $60 on the run, and in fact Rails eventually did $10 or $20
> better than that.)
>
> The next thing is that I'd like to know what was autocalculated versus
> hand-entered.  A note in the logfile saying what the calculated run
> was would be very useful. (Yes, I could go back in the history and
> look for myself, but that's not always feasible.)
>
> Finally, any interrupt between calculating a run and entering it
> restarts the calculation -- even things like saving the file or
> entering the destination of another company.  Highly annoying, though
> not quite a bug.
>

This is a known issue with the current brute-force algorithm -- it was
brought up when it was being implemented.  Basically, when the number of
trains and stops goes up, the number of possible routes goes up
exponentially.

A long, long time ago, I implemented route calculation by transforming the
problem to a flow graph and running the max-flow/min-cut algorithm on it
(sorry, I no longer have this code), which avoids exponential time.
 However, I don't know how to adapt this to all the exotic rules that have
been added since then -- there may not be any better approach than brute
force to make sure no solutions are missed.

Perhaps the best approach is to take advantage of multiple cores by sharding
testing alternate routes into threads and count on hardware getting faster
:).

-- 
John A. Tamplin