Re: [Rails-devel] Automatic route calculation

[alexti <al...@sh...>]

Hi Stefan,

Don't worry about embarrassing errors! I have one somewhere and I don't  
even know where :) - I don't know why my algorithm doesn't find the  
optimal solution you've mentioned - it's supposed to, it's completely  
brute force and it should check every combination, but apparently it  
doesn't. I suspect I have a bug in my new 2-phased code where I determine  
which segments connecting cities are mutually exclusive.

I wonder, how do you plan to do the "best route estimates" in general.  
When the various train and bonus rules are added ("free" towns, express  
trains, doubling trains, East-West runs, bonuses for connecting pairs of  
cities etc...) evaluating what should be in the optimal route is going to  
be rather complex. It's also important to figure out how to quickly find  
pretty good set of routes, thus cutting off a lot of the search tree.

The times start to look promising, even the complete run finishing in 1-2  
minutes is pretty good. With one-phased algorithm it was taking ~40  
seconds on my machine to do complete search.

Thanks,
Alex.


On Tue, 13 Apr 2010 17:01:37 -0600, Stefan Frey (web.de)  
<ste...@we...> wrote:

> Hi Alex and all others...
> ... discussing revenue calculation. It seems to spur a lot of interest.
>
> Sorry for the long post (if one includes the text document), but I try to
> answer most of the asked and some of the not-yet asked questions.
> And it seems that the algorithms already improve from the fruitful  
> discussion.
>
> Some talk about the concepts are in the attached text document, that was
> easier to edit.
>
> This is the good thing of commit early and often. One of its  
> disadvantages are
> the embarrassing errors in the early releases. I list those at the end  
> of the
> attachment and hopefully it will clarify some of the problems you ran  
> into.
>
> Good news first:
>
> * Running Times
> After hunting them down and adding a new concept (the revenue prediction  
> - see
> attachment) evaluation time is now down to 1-2 seconds for a 8 and 10  
> train
> on the A scenario on my laptop. Without revenue prediction it runs for  
> 1-2
> minutes. Both runs have identical results.
>
> * Optimal Solution (?)
> The other thing is that my implementation suggests a (slightly)  
> different path
> than Alex' which results in an increase of revenue.
> The change is that the 8 train does not have the 10 - 30 - 30 (
> that is Alexandria and Baton Rouge in 1870, the right bottom in Alex  
> graph -
> it is rotated) in the end, but the 10 - 30 - 50 (that is Austin and  
> SouthWest
> on the map, the right top in Alex graph). Thus it runs for 20 more.
>
> It now pays off that we have independent algorithms running, that can  
> find
> flaws in each others (like you did for mine).
>
> Stefan


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/