Re: [Rails-devel] Improved revenue prediction / different scenario

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

Hi Stefan,

My speed advantage is likely due to two-phased approach and more efficient  
memory management. I still would like to get more intelligent prediction  
algorithm though :-)

What exactly 5,651k predictions in your case mean?

I've actually looked at my approach to the station handling (after  
checking all routes from the first station I simply mark all segments  
connected to this station as "used", so no other route would include this  
station). I can't actually come up with any better method.

When you're saying you "keep start vertices visited", do you mean  
"stations" or you iterate in some other manner (not from the stations)?

Meanwhile, I've spotted some epic stupidity in my code and after removing  
it my time on that example went down to 30s.

I've started to work on more sophisticated predictor; but now I don't  
exactly understand what it is doing and it doesn't always work correctly.  
Even when I get it right, I am not sure if it will be any better :(

I've also realized that on that 4 train case, our algorithms would easily  
beat human - when I look at the map it's not obvious to me at all what the  
best run would be :)

Alex.


On Tue, 11 May 2010 16:12:20 -0600, Stefan Frey (web.de)  
<ste...@we...> wrote:

> Hi Alex,
> but you are still faster and get more scenic routes, thus you should not  
> be
> too concerned :-)
>
> And I did 565k evaluations plus 5,651k predictions, compared to this  
> number it
> is only 10 times less. The only optimization (or better avoidance of
> unnecessary duplication) I have not talked about is that I keep the start
> vertices visited, when I move to the next start vertex. All possible  
> routes
> which include the previous start vertex are already run from that vertex.
>
> Otherwise we should go back to much simpler examples to compare, but I  
> do not
> have much hope to get similar numbers as long as I do not have  
> implemented
> the two-phase approach.
>
> Stefan
>
>
> On Tuesday 04 May 2010 07:37:39 alexti wrote:
>> Hi Stefan,
>>
>> Thanks for the explanation. I think I understand what you're doing; I
>> wasn't doing exactly the same and changing my algorithm brought some
>> improvement, but as usual it was not that big - I'm starting to feel you
>> have some kind of magic predictor ;-)
>>
>> I've run your scenario and my algorithm found the same set of routes,
>> however it was able to find more scenic route between M6 and L11 for 5+5
>> train :) It took 46s. Here are my stats.
>>
>> Routes found in 45.9643s
>> [4:340] {E12,C10.SE,C10.NW,B9,B11,A10.N,A8.S,A8.N,A4.S,A4.N,A2.S}
>> [8:290]
>> {N1.SW,M2,L3.NE,L3.SW,K4,J3,J5,G6.NE,G6.NW,F5,E6.NE,E6.NW,D5,B3.SE,B3.NW,A2
>> .SE} [10:230]
>> {E12,H13,I14.NE,J13.SW,J13.NE,L11,M8,M10,M6,L5.SE,L5.NW,K4,J5,H3}  
>> [6:240]
>> {N1.S,N3.N,N3.SW,M4.NE,M4.NW,L3.SE,L3.NW,J3,H3,F5,D5,D7.N,D7.NW,C6.SE,C6.SW
>> ,B7,B9,C8.SW,C8.S,C10.N,C10.SW,B11} 50,125,612 routes tried
>>
>> The frustrating (to me) part is that you've done only 564,805 while I  
>> did
>> over 50 millions (almost 100 times more). I am not sure how you manage  
>> to
>> eliminate so many possibilities. I know that my algorithm doesn't handle
>> multiple stations efficiently - essentially it scales linearly with  
>> number
>> of stations. I have not thought about it yet, but it still wouldn't
>> explain the difference.
>>
>> Maybe I'm overlooking something. Or maybe I have some bug in the
>> implementation that doesn't eliminate something I think it does :)
>>
>> Thanks,
>> Alex.
>>
>> On Sun, 02 May 2010 13:20:14 -0600, Stefan Frey <ste...@we...>  
>> wrote:
>> > Alex,
>> > sorry for not answering earlier to the question about the improved
>> > revenue
>> > prediction.
>> >
>> > The scheme is simple.  Assume that N is the number of trains in the
>> > trainset.
>> > First I replace the maximum revenue potential of each single train by  
>> the
>> > maximum results of running each train alone.
>> >
>> > If there are more than two trains to run:
>> > Start with J=N-1 and decrease J with each step until J=1.
>> > - Run the combined set of trains [J, ... N] and use the optimal  
>> result to
>> > predict the maximum future revenue potential of that train set.
>> >
>> > Then run the combined optimization of all trains, given the maximum
>> > revenue
>> > potential for each set [J, N], with J > 1.
>> >
>> > I would like to compare another scenario based on the track network A  
>> to
>> > check
>> > if we get the same results.
>> > The changes are:
>> > - SLSF has 4 tokens now (D5, J3, L11, E12)
>> > - Trains running are 6E, 8, 5+5, 4D
>> > (E: ignores towns, D: ignores towns and double city and offboard  
>> values)
>> > The best run I find is 1100. Total running time 78 sec.
>> > Network runs (6E cyan, 8 pink, 5+5 orange, 4D gray)  and log is  
>> attached.
>> >
>> > Stefan
>
>
>
> ------------------------------------------------------------------------------
>
> _______________________________________________
> Rails-devel mailing list
> Rai...@li...
> https://lists.sourceforge.net/lists/listinfo/rails-devel


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