Re: [Rails-devel] Route calculation validations

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

Hi Stefan,

Here are my numbers. It's pointless to compare edges, because I'm using  
2-phased approach, so I'm only giving number of revenue evaluations. I  
also assume that you're talking about 10+8 when you say "10+6" (that seems  
obvious from the attached stats). The good news is that the optimal  
revenue we're getting is identical in all cases. The bad news is that  
everything else is different. I have much higher number of revenue  
evaluation. I suspect that I evaluate something unnecessary (considering  
that I never find any better route :) ). That's not necessarily bad -  
perhaps if I get rid of it I can compute things faster. It's interesting  
that none of our methods is good for diesel plus other train. What's  
worse, I think that this time can deteriorate dramatically on the examples  
with more cities. The root of the problem is that there might be a lot of  
different diesel routes with very small value variation (like within  
10-30$) which would mean that in each case the remaining graph will have  
to be evaluated for the 8 train...

Btw, in what order do you iterate over trains? I go from longest to  
shortest. On some earlier tests I've decided that it worked better, but  
now I wonder if the diesel case might be an exception...

8 - 5601, 0.003s
D - 957676, 1.4s

10+8 - 3649238, 5.8s
D+8 - 16110745, 74.5s

Thanks,
Alex.



On Mon, 19 Apr 2010 14:01:14 -0600, Stefan Frey <ste...@we...> wrote:

> Hi Alex,
> I have attached a document that contains the detailed numbers for several
> train combinations without and with the revenue prediction active.
>
> The following figures are defined:
> revenue evaluation: how often the revenue of all trains is evaluated
> edges travelled: how many edges were followed during the search
> predictions: how often the potential maximum revenue was predicted.
>
> My desktop is even slower as my laptop, as it is slightly older and has  
> an AMD
> processor.
>
> It clearly shows that revenue predictions is strongest for train  
> combinations
> and non-diesel trains. Running a diesel alone is not any faster, unless  
> an
> optimal solution is found (early).
>
> Stefan
>
> I sent that to the develop list, as others might also be interested in  
> those
> numbers. I extract the main figures below,
> all runs on the test scenario A.
>
> 8 train alone:
> without prediction: 3.8k evaluations, 16.4k edges, time: < 1 sec
> with prediction: 62 evaluations, 858 predictions, 2.3k edges, < 1 sec
>
> 8 and 10 trains:
> without prediction: 1.9M evaluations, 11.0M edges, time: 90 sec
> with prediction: 25k evaluations, 143k predictions, 387k edges, time: 4  
> sec
>
> This clearly shows the strong increase of possible solutions, if more  
> than one
> train is involved. It is around 1:500!
>
> Diesel train:
> without prediction: 424k evaluations, 3.3M edges, time: 25 sec
> with prediction: 335k evaluations, 753k predictions, 2.6M edges, time:  
> 23 sec
> (In this example an optimal solution is found, but late).
>
> A diesel is less complicated than the combination of an 8 and 10, but the
> revenue prediction does no help.
>
> Diesel and a 6 train:
> without prediction: 7.3M evaluations, 52.5M edges, time: 480 sec
> with prediction: 231k evaluations, 2.8M predictions, 6.2M edges, time:  
> 56 sec
>
> Adding a 6 train, increases the running time by 20 without prediction,  
> but
> only a little more than doubles with prediction.
>
>
>
> On Sunday 18 April 2010 17:44:04 you wrote:
>> Hi Stefan,
>>
>> I would agree about the name of the first number.
>>
>> (1) should be ok, I do the same, and there is no good reason for the
>> algorithm to try evaluating route that just extend already evaluated  
>> route
>> by some stations the train can't reach anyway. Or we could run the test  
>> on
>> "express" train that can skip anything. Express trains (or any train
>> capable of skipping cities) actually make me wonder what are possible
>> rules about visiting the same hex. In some games train is not allowed to
>> visit the same hex twice (when there are 2 separate cities on the tile).
>> If there is any game with this rule and with express trains, then  
>> there's
>> a question - if the train skips one city in the hex and counts another -
>> is it valid route?
>>
>> (2) I apply the same method to the routes, but I didn't evaluate "half"
>> routes - I only evaluate complete route (consisting of those 2 parts).  
>> How
>> can you do differently? - There might be bonus for visiting 2 cities in
>> different halves, or something like east-west run.
>>
>> If it's difficult to extract this number from your code now, we could  
>> set
>> up example with the station in the dead-end, so there's only one way to
>> leave it.
>>
>> Number of segments is relevant to the two-phased approach only. It is
>> number of edges in the "coarse" graph (which is the same as number of
>> distinct ways to travel between any pair of cities). You were asking  
>> about
>> this number earlier to evaluate amount of memory that would need to be
>> stored.
>>
>> I've also done profiling and it appears that storing segment exclusions  
>> as
>> a vector of segments excluded by each segment is fine - this is not a
>> bottleneck. So I haven't tried 2D array of booleans approach. But maybe  
>> I
>> should try some different cases (for example set of 4 trains (2,2,3 and  
>> 3)
>> - that may have a bottleneck in different places comparing to the case  
>> of
>> few long trains).
>>
>> Thanks,
>> Alex.
>>
>> On Sun, 18 Apr 2010 13:28:24 -0600, Stefan Frey <ste...@we...>  
>> wrote:
>> > Hi Alex,
>> > I would call the first statistic "number of  route evaluations" and it
>> > counts
>> > every call to the evaluation function. This figure is also available  
>> for
>> > multiple-train runs. If we have the same number, it is almost sure  
>> that
>> > the
>> > two algorithms work identical. If not, it proves nothing, see below.
>> >
>> > Potential problems:
>> > 1) I terminate trains as soon as possible, thus numbers depend on the
>> > sequence
>> > of vertexes visited.
>> >
>> > 2) I have train runs divided in two half trains: First the head train
>> > starts
>> > and each station the train can return to its start token and then the
>> > bottom
>> > train runs. To avoid duplication of routes (due to symmetry) the  
>> bottom
>> > train
>> > can only start to the side with increased orientation. If I remember
>> > that is
>> > a different approach to yours.
>> >
>> > So if we want to compare figures we have to run a train with infinite
>> > length
>> > (to avoid termination) and is not allowed to run twice from the start
>> > vertex.
>> >
>> > I will have to adjust my codes to accommodate for such a test.
>> >
>> > The other statistic I am not fully clear about: Wat is exactly the
>> > number of
>> > segments? If this is related to the two-phase approach I assume this  
>> is
>> > the
>> > maximum number of connections between two stations on the map?
>> > And I guess, that this might be the answer to the unrelated question I
>> > raised
>> > before. This strengthens the case of your approach. I will implement  
>> it
>> > as
>> > soon as I have some time left, which will be most likely after the  
>> next
>> > release.
>> >
>> > Stefan
>> >
>> > On Sunday 18 April 2010 06:34:51 you wrote:
>> >> Hi Stefan,
>> >>
>> >> I thought it might be useful to compare how many routes we try during
>> >> the
>> >> complete route search. We should be getting the same number. If we  
>> are
>> >> not
>> >> it will indicate that one of us (or both) have a bug. I suppose to  
>> test
>> >> it
>> >> we would need to run a single sufficiently long train (or maybe try  
>> for
>> >> various train lengths) on the same track.
>> >>
>> >> I've also checked on number of segments in two-phased approach. In  
>> the
>> >> scenario B there are just 153 segments.
>> >>
>> >> Thanks,
>> >> Alex.
>