Re: [Rails-devel] Automatic route calculation

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

On Sun, Mar 21, 2010 at 11:12 AM, alexti <al...@sh...> wrote:
> On Sun, 21 Mar 2010 11:59:01 -0600, brett lentz <bre...@gm...>
> wrote:
>
>> On Sun, Mar 21, 2010 at 10:54 AM, alexti <al...@sh...> wrote:
>>> On Sun, 21 Mar 2010 11:44:48 -0600, brett lentz <bre...@gm...>
>>> wrote:
>>>
>>>> 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, O(n!) only describes asymptotic behaviour, it doesn't mean that
>>> if
>>> you go from 1000 to 2000 than your time will increase by 2000!/1000!
>>> factor. In 18xx games there is also an interesting property of adding an
>>> edge unconnected to the station does not increase time at all and this
>>> is
>>> not uncommon in many games (at first because the track is not connected
>>> and later because it is blocked).
>>>
>>> Alex.
>>
>> You're right. Our problem isn't strictly the traveling salesman (which
>> is usually where O(n!) is seen).  I don't expect your algorithm to be
>> O(n!), but maybe closer to O(n^2) or O(2n).
>>
>> ---Brett.
>
> Unfortunately, I haven't done any formal analysis of my algorithm and I
> didn't know what is its asymptotic behaviour and how it behaves on a more
> typical range of n. Besides, on the modern hardware there are some
> interesting dependencies related to the memory speed vs CPU speed. There's
> a dramatic performance drop when the working data set stops fitting into
> the cache.
>
> Talking about software design, should the route calculation be run in a
> separate thread, so that the user doesn't experience "screen freeze" if
> for some reason it's taking too long? Also, as John has suggested, we
> could time-out or let the user cancel the calculations in those cases.
>
> Alex.

Yes, running the calculation in a separate thread is a good idea. This
would also allow use to begin calculations for the next OR during the
Stock Round.

I agree, there should be a tunable timeout value just so we don't take
more than 30 seconds or so to return any value.

Also, one thing that might be neat to have after the initial
implementation is a way to suggest routing "hints". For example, in
1830, allow the use to select that they want their route to hit New
York, Boston, and Philadelphia.  That gives us some concrete
information that would speed up the calculations quite a bit, I'd
expect.

---Brett.