Re: [Rails-devel] Automatic route calculation

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

On Sun, 21 Mar 2010 13:41:30 -0600, John A. Tamplin <ja...@ja...> wrote:

> On Sun, Mar 21, 2010 at 2:30 PM, alexti <al...@sh...> wrote:
>
> Yes, I use brute-force approach of going through all possible routes that
>> include a token. Why interaction with another train will be more
>> complicated in this case? It still can't re-use the same track. Or are
>> there games where it can?
>
>
> Yes, but that actually makes it easier -- you just calculate the routes  
> of
> the trains that can reuse track independently of the others (such as TGV  
> in
> 1826, 4D in 18Neb, etc).
Ok, that's a good news.

> The problem is when they can't reuse track, you have to choose the  
> optimal
> run for all trains together, not independently.  It is often the case  
> that
> the optimal run for running multiple trains is not an optimal run for any
> one of the trains by itself.  Therefore, you must evaluate all the  
> trains at
> the same time, which in a brute force algorithm gets you back to n!^m.
I agree, but I am not sure that in practice it's that bad. Asymptotic  
behaviour may look scary, but we're dealing with a bound case. I'm  
assuming that m is relatively small (m<=4 ?). One of the factors that  
severely limits graph growth is a train length (because there's no point  
to include any edges that can not be reached from any station by a train  
of given length). I think that "unlimited" diesel or express trains would  
have to be part of the worst case scenario.

>> Perhaps it can be tested? There is no need to have complete support of
>> such games in Rails to make experiment. We could create a graph
>> representing "difficult case" and run algorithm on it.
>>
>
> Yes, though it could take time to manually build the graph the way your
> algorithm wants it.

>> > Some I would look at would be 18US, 18C2C (for sheer size and the  
>> ability
>> > for a company to run lots of large trains), 1844 (which adds tunnels  
>> and
>> > mountains that affect the route score), and 1860.
>> Unfortunately, I don't own any of them :(
>>
>
> The complete rules are available for at least 18US and 1844, and ps18xx
> includes the map/tiles for all of them.

Are there some cases you would consider examples of "difficult" ones that  
are available in some kind of format? From some PBEM games perhaps? It  
might be relatively easy to convert them into the graph I need. And it's  
difficult to get an impression of what realistic end game layout would be  
without playing the game.

Alex.