Re: [Rails-devel] Automatic route calculation

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

Hi Stefan,

You have made a lot of progress in implementing route calculation recently
:)

About the "greedy" edges: (I was calling this optimization "asterisk"
optimization in my previous post).

I avoid "switch" problem in a different way. My vertex definition is
geographical - vertex id is its coordinates. Because of that I can check
backtracking differently - my criterion is that two consecutive edges from
the same hex are only allowed if they are joined at the center. This can
not be derived from the graph definition formally. Essentially I have
additional information in the graph that is encoded in the vertex
identifiers.

When I look at the train routes in your example, the sequence [B11.1,
C10.NE, C10.W, C8.NE, D7.NE] doesn't look right to me - C10.W, C8.NE,
D7.NE looks like backtracking.

I've run the test with the setup similar identical to yours (same stations
and trains), it took ~7 seconds on my machine (which is probably somewhat
faster than yours, perhaps by factor of 2 or something like that - unless
your laptop was really high-end when new). 2.5 seconds to build a coarse
graph and 4.5 seconds to find the routes. My total was also 580 and I hope
it is valid. I'm actually finding it challenging to validate correctness.
Couple of times in my experiments I've seen this algorithm picking rather
strange looking routes (not what I would intuitively expected to be the
best), but no matter how I tried I couldn't beat them manually :)

I don't have any mechanism to output the routes in the text form, so I'm
attaching screenshot with those routes highlighted. On my screenshot the
picture is transposed, but it doesn't have any effect on the topology of
the problem. I do not have any timing indicating when these routes have
been found. In a way it doesn't matter right now, until we can somehow
tell that no better route is possible.

Concerning your algorithm, do you do transient vertex optimization? It is
probably the most important optimization on the original (primary as I
called it) graph. And it should be easy to implement (because of
asterisk/greedy edge approach you'd need to make it somewhat less
aggressive so that the resulting edge can preserve correct "greediness".

The other big optimization is two-phased approach - it's essentially
reduced dimensionality of a problem by a big factor. Another big
optimization for me was in efficient memory management, but that could be
hard to implement in Java. I'm also not certain if it's that important
anymore (since I've switched to the two-phased approach). It would be
interesting to see how much change in times you can achieve by removing
transient vertices. Another interesting experiment would be to time how
long it would take your algorithm to find all possible routes for every
city/town pair (that's what is necessary for building coarse graph). I am
not sure how easy it would to modify your code to do that.

I really appreciate your effort in adding this functionality to Rails. Not
being Java specialist I can only help on the algorithmic side. I want to
look into how the second phase works now and what can be improved there
(algorithmically) so I can share these results. I could also take a look
at how to [efficiently] combine transient vertex optimization with the
asterisk edge approach. If we decide to go with two-phased approach (and I
think we definitely should) and build the coarse graph incrementally,
asterisk edge optimization becomes less important. Of course, your
implementation needs asterisk edges to check backtracking which
complicates things a bit. Would it be easy to be use "geographical"
checking? Or is this part of code comes in some library you can't modify?

Please let me know what direction you think we should put our efforts.

Thanks,
Alex.

P.S. Sorry, I am unable to reduce the size of the screenshot much more  
without making it too hard to read.



On Mon, 12 Apr 2010 15:49:14 -0600, Stefan Frey (web.de)
<ste...@we...> wrote:

> Hi Alex,
>
> thanks for all the input below, it seems that there is really some more
> performance improvement possible. And without your proposals I would not  
> have
> started such an implementation at all.
>
> Unfortunately I do not have that much time now, but maybe some additions  
> here
> are helpful, as I had some troubles understanding your approach first.
>
> The major issue for me was how to get around the "switch" problem: A  
> train is
> not allowed to turn around at the end of the switch and you have to  
> leave the
> hex to the neighboring one. The major idea of my solution is the  
> definition
> of a "greedy" edge: The "virtual" edges connecting the sides of the
> neighboring hexes force the traveller on their path, if they came
> in "non-greedy"  (those are the tracks inside the hex).
>
> In the network graphs generated the non-greedy edges are those annotated  
> with
> asteriks. A nice property is that greedyness is dominating if one merges  
> two
> edges to eliminate a vertex with only two hexes. The new edge is greedy  
> if at
> least one of them was greedy. This implies after optimization most edges  
> are
> non-greedy, usually only the brown non-station tiles will be left. This  
> and
> the dead-end elimination creates the optimized graphs in Rails.
>
> I have attached the scenario (scenario A) that you talked below for  
> reference
> for all others, with the rails save file (does only work with the CVS  
> version
> due to the map corrections), a screenshot of the map and the optimized
> network graph.
>
> Stefan
>
> PS: I would like to compare the results and the performance of the two
> implementations (to know how much improvement is possible ...)
>
> I did not use the exact specification I suggested (due to technical  
> reasons):
> There is only one token in E12 and I run an 8 and 10 train.
>
> My solution run finished 12 minutes on my 4 year old laptop.  
> Interestingly it
> found already 560 after 1 second, 570 after 1 minute and then 580 after 8
> minutes.
>
> Revenue Value:580
> Revenue run:{8=[E12.1, C10.SE, C10.NW, B9.1, B11.1, C10.NE, C10.W, C8.NE,
> D7.NE, D7.W, D5.1, F5.1, E6.NW, F7.NW, F7.SW, G6.SW, J5.1, K4.1, J3.1],
> 10=[E12.1, H13.1, J11.W, J13.W, J13.SW, L11.1, M14.1, M10.1, M6.1, L5.SE,
> L5.NW, K4.1, L3.NE, L3.SW, M2.1, M4.NE, L3.SE, L3.NW, J3.1, J5.1]}
>
> On Monday 12 April 2010 06:31:19 Alex Tikhonov wrote:
>> Hi all,
>>
>> Sorry about my disappearance after raising this question couple of weeks
>> ago. Things weren't standing still; I was in contact with Stefan, but
>> unfortunately circumstances prevented quicker progress. Stefan has added
>> some new functionality to Rails to lay some background framework and to
>> simplify creation of "test problems". He has created few testing  
>> scenarios
>> too. My original algorithm has proved to be marginal - on a relatively
>> complex example the time was around 40 seconds. We've discussed various
>> optimizations and I believe we have found good approach. The basic idea  
>> is
>> to use two-phased process that runs on two different graphs. The first
>> graph (let's call it primary graph) is built from the tiles and
>> essentially follows one tile - 7 vertices principle (I've described this
>> approach before and after some discussion with Stefan we've concluded  
>> that
>> it's identical to the approach he had in mind). Essentially, one vertex  
>> is
>> in the center of the tile and there are 6 vertices, one per tile edge. I
>> was envisioning them inside of the tile, on the line connecting the  
>> center
>> of the tile edge to the center of the tile (in fact, that's how I was
>> visualizing them in my program) while Stefan was seeing the center of  
>> the
>> tile's edge as such vertex (so adjacent tiles would have their vertices  
>> on
>> the same spot and those vertices would be connected by [invisible]  
>> edge).
>> This obviously describes exactly the same graph and the difference is  
>> only
>> in how it can be thought of visually (or displayed).
>>
>> This primary graph is then used to generate secondary "coarse" graph.  
>> The
>> only vertices coarse graph has corresponds to the nodes with some value
>> (usually cities and towns). The edges of the coarse graph (I will call
>> also them segments) are defined by possible distinct routes between its
>> vertices. Thus there might be more than one edge connecting the same  
>> pair
>> of vertices. This edges are built by running my original algorithm on  
>> the
>> primary graph with the constraint requiring every route to contains
>> exactly two nodes (vertices with value) - one at the start and another  
>> at
>> the end. Essentially the list of these edges is the list of all possible
>> two city/town routes. Each segment of this graph has additional
>> characteristic - list of segments mutually exclusive with it. There are
>> two types of exclusions - one forbids use of the related segment by any
>> route and another forbids its use only by the same route. The first type
>> of exclusion happens when two segments share some edge of the primary
>> graph and the second type happens when only some vertex of the primary
>> graph is shared (here we only consider non-terminating vertices - ones
>> that are inside of the segment route, those vertices will have no  
>> value).
>> This information forms coarse graph. There are multiple advantages in
>> choosing this approach. The value of any route only depends on the nodes
>> (vertices with values) visited, not the intermediate vertices. This
>> considerably reduces number of possibilities to scan and it also allows  
>> to
>> optimize the process by using "pre-packed" segment routes between the
>> nodes. The coarse graph is company-independent - it has no token
>> information and can be used to do route computations for any company.  
>> The
>> coarse graph can be built incrementally. The most expensive part of
>> building this graph is the search for all possible routes between every
>> pair of nodes. This time can be saved if the coarse graph is updated
>> incrementally when new tiles are laid (or upgraded). We only need to  
>> track
>> the routes containing the newly added edges. All remaining routes are
>> unaffected. On the "realistic" 1870 scenario we've used for testing it  
>> is
>> taking 2-3 seconds to build coarse graph from scratch (on my rather
>> average computer). If it's built incrementally, this time will virtually
>> disappear. Of course, this leaves a question of game reloading (perhaps  
>> it
>> makes more sense to rebuild it non-incrementally when the game is
>> reloaded, or even save the coarse graph itself).
>>
>> The second phase of the process is to run optimal route search on the
>> coarse graph. I am just running my original algorithm on this graph.  
>> This
>> part takes care of source stations, hostile station blocking, visiting  
>> the
>> same city twice and similar rules (as well as various bonus  
>> application).
>> On the example described above this was taking 2-3 seconds. This phase  
>> has
>> to be re-run every time on "Run trains" step of the operating round, but
>> this response time seems acceptable. The run times I've mentioned are  
>> from
>> my quickly put together implementation of this new approach, so I would
>> imagine it's possible to do better just by refining the implementation  
>> and
>> we haven't looked closely at possible algorithmic optimizations of  
>> phase 2.
>>
>> There are few possibly optimizations that can be applied to the primary
>> graph too. Stefan has suggested "asterisk-edge" optimization. This is to
>> simplify verification preventing backtracking. Idea is to mark all edges
>> that are within the same tile with "asterisk" and then the rule  
>> preventing
>> backtracking becomes very simple: two "asterisk" edges can be traveled
>> consequently only if they're connected at the tile's center. This should
>> help in phase 1 generation. There's some difficulty now though, because
>> I'm using "transient vertex" optimization which can eliminate some edges
>> and thus change adjacency of "asterisk" and "non-asterisk" edges. The
>> transient vertex optimization works in the case when there's a vertex
>> (without value) connected to exactly two other vertices (for example
>> vertex B in A-B-C example). In this case vertex B can be removed and  
>> edges
>> (A,B) and (B,C) replaced with (A,C) edge. This provides big benefit,
>> because realistic track build normally has large amount of such  
>> vertices.
>> Another (obvious) optimization is dead-end elimination (if vertex has no
>> value and it is connected with one other vertex only it can be
>> eliminated). This optimization should not be used when tracking validity
>> of track lay (for obvious reasons).
>>
>> There were some other ideas, such as caching results of the optimal  
>> route
>> search and trying to eliminate some possibilities based on the values of
>> the cities/towns on the map, but we have no concrete approach to exploit
>> them.
>>
>> Hopefully, I haven't forgotten anything important. Stefan, please free  
>> to
>> add whatever I've missed.
>>
>> Thanks,
>> Alex.
>>
>> ---------------------------------------------------------------------------
>> --- Download Intel&#174; Parallel Studio Eval
>> Try the new software tools for yourself. Speed compiling, find bugs
>> proactively, and fine-tune applications for parallel performance.
>> See why Intel Parallel Studio got high marks during beta.
>> http://p.sf.net/sfu/intel-sw-dev
>> _______________________________________________
>> 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/