Re: [Rails-devel] Automatic route calculation

[brett l. <bre...@gm...>]

On Sun, Mar 21, 2010 at 10:35 AM, alexti <al...@sh...> wrote:
> On Sun, 21 Mar 2010 10:27:18 -0600, John A. Tamplin <ja...@ja...> wrote:
>
>> On Sun, Mar 21, 2010 at 1:43 AM, alexti <al...@sh...> wrote:
>>
>> A brute-force search of all possible routes is O(n!), and is really only
>> feasible (even on modern machines) for 1830-like games.  Games like 18US
>> that have simplified plain track tend to have a couple orders of
>> magnitude
>> more possible routes.
> I am not sure what is n in O(n!), but I don't think that asymptotic is
> particularly useful in the given context. On the actual maps number of
> vertices and edges is relatively small and because of 18xx track and route
> rules dependency is not proportional to n! for that range of n. I have not
> played 18US, but I have tried setting up artificial examples of rather
> convoluted track and for single route set evaluation it was fine (though
> for AI it was causing problems).
>


http://en.wikipedia.org/wiki/Big_O_notation

O(n!) means that for each vertex/edge that's added to the calculation,
the time it takes for the algorithm to reach a solution grows by a
factorial order of magnitude.

---Brett.