[OT] Navigation systems

[Alex Tweedly]

On 17/10/2013 16:57, Peter Haworth wrote:
> Thanks for the pointers eveyone.  I have some reading to do!

I'll suggest some more reading :-)

I don't agree with some of the earlier posts. Navigation problems (i.e. 
'best' route from A to B) is not equivalent to the Travelling 
Salesperson Problem - it's considerably easier than that. It's a graph 
searching problem, and so there are solutions which run in polynomial 
time (whereas NP-complete problems like TSP don't).  Best known approach 
would be Djikstra's algorithm ( as used in in network routing, like OSPF 
and IS-IS)

You could start with http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 
though it's a pretty hard slog.

An easier intro is in http://en.wikipedia.org/wiki/Link_state_routing   
and go down to the section on "Calculating the shortest paths" (and 
don't get distracted by all the rest of the stuff link-state routing has 
to deal with;  in map/directions you don't need to dynamically detect 
link failures and you don't need to spread info about them over the 
network you are trying to use :-)

Or, jump to the answer  ...
http://stackoverflow.com/questions/430142/what-algorithms-compute-directions-from-point-a-to-point-b-on-a-map

-- Alex.
> Mike,  I never made the connection between aircraft boarding and navigation
> before but you opened my eyes!  Incidentally, Southwest now have a "clump"
> system layered on top of their no seat allocation rule. There are three
> boarding groups (A,B,C) and within those groups, numbers from 1-60 (or more
> for larger aircraft), with the group and number being assigned serially (I
> think) in order of time checked in. The numbers aren't seat numbers, just
> sequence numbers within the group. At boarding time, group A, numbers 1-30
> go first, followed by group A numbers 31-60, and so on.
>
> This all came about really because I'm using my Nexus 7 for navigation and
> it does not have the LTE option on it so I'm not on the internet when
> driving.  I found a few apps that will provide navigation when not
> connected to the internet, which they do by downloading maps from an open
> source mapping project.  Obvioulsy you have to get the necessary maps while
> you have an internet connection but after that, the apps use the gps in
> conjunction with the maps to figure out routes and navigate them.
>
> I guess Google maps allows you to save maps and work offline but I found
> that it has size restrictions that won't save maps that cover a large area.
>
> Pete
> lcSQL Software <http://www.lcsql.com>
>
>
> On Thu, Oct 17, 2013 at 7:57 AM, Richard Gaskin
> <ambassador at fourthworld.com>wrote:
>
>> A good overview:
>> http://en.wikipedia.org/wiki/**Travelling_salesman_problem<http://en.wikipedia.org/wiki/Travelling_salesman_problem>
>>
>> --
>>   Richard Gaskin
>>   Fourth World
>>   LiveCode training and consulting: http://www.fourthworld.com
>>   Webzine for LiveCode developers: http://www.LiveCodeJournal.com
>>   Follow me on Twitter:  http://twitter.com/**FourthWorldSys<http://twitter.com/FourthWorldSys>
>>
>>
>> ______________________________**_________________
>> use-livecode mailing list
>> use-livecode at lists.runrev.com
>> Please visit this url to subscribe, unsubscribe and manage your
>> subscription preferences:
>> http://lists.runrev.com/**mailman/listinfo/use-livecode<http://lists.runrev.com/mailman/listinfo/use-livecode>
>>
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode