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

[Stefan F. (web.de) <ste...@we...>]

Hi Alex,
see answers below. 
>
> 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 :-)

Most likely the difference is from the two-phase approach.
Memory management should be irrelevant for the Java program, as all variables 
involved are fixed sized arrays, which are defined as final.
It will be more the speed of function calls and stack handling.

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

Evaluations count the call to the function that sums up the value of all 
trains after all trains are finished.
Predictions count the call to the function used after each station visit.

Actually the latest refactoring (I do not evaluate anymore until I reach the 
second station, previously I set that to zero) reduced the number of 
evaluations and predictions: 
The number of evaluations drops to 480k, the number of predictions to 
2,950k, the number of edges travelled does not change.
Speed improvement is minor (10-15%).

>
> 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)?

That seems identical, except that I do not mark the edges (as they are not 
train specific) as used, I only do that for the vertexes (train-specific). 

I have an outer loop that iterates over the base tokens: After I have 
considered all routes from the first token, I keep that vertex as visited to 
avoid evaluating the identical route again. (All routes with both first and 
another start token are already found from the first route, this will work as 
long as connectivity is symmetric).

>
> 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 :)

I am long lost with founding best routes for those scenarios, but I am not a 
good route finder.

>
> 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