On Wed, Dec 12, 2012 at 2:12 PM, Dennis Luxen <dennis.lu...@gmail.com> wrote:
> A* guarantees that the route is optimal for the given metric of >> cost. I assume that CH gives the same guarantee for the same metric >> and will therefore give exactly the same route. >> > > Not necessarily true. There may be distinct path with equivalent weight. > It will return a path of equal length but not necessarily the same one. > > It would be extremely rare for this to happen in OSM. Most shortest path calculations that I am aware of have a resolution of at least 10cm and the 'fastest route' calculations have a resolution of the order of 1ms. The top two choices on a 10km journey will typically differ by 40m or more. > Speaking of guarantees, I was thinking of search space sizes. A* is not > able to give any assertion that it is indeed faster than Dijkstras > seminal algorithm or uses less RAM. The correlation between the square of the direct distance (as the crow flies) and the memory consumed is pretty good. The exception is usually when there is some kind of data problem e.g. a gate tagged tagged as closed (although it's theoretically possible to solve some of these problems with preprocessing). > > But now you have many phones and tablets with 1GB RAM and a 1GHz >> processor, so A* can buffer all the static data in RAM and only takes >> a few seconds. >> > > If and only if the data fits into RAM. And thats going to deliver a > rather crappy user experience when a user has to quit other apps just to > have enough RAM. Mobile OS vendors do make an effort to accommodate resource intensive applications such as games. For example, properly written Android apps save their state when they are paused, so they can be killed at restarted. > > (B) Furthermore, most devices are now Internet enabled and long >> routes can be calculated in the cloud using A*. >> > > A place where you certainly don't want A*. > > Well I'm stuck with A* because I can't afford a server with 128GB RAM to do the preprocessing necessary for CH. > If a normal driver calculates all his routes with A*, the >> computational cost will be less than one hundredth of a cent per >> kilometre. >> > > That's some strange metric and awfully expensive for an online service > thats mildly popular. I merely gave an upper bound to illustrate a point. The figure for Yournavigation is so low it's difficult to quantify. Of the order of 0.00001 cent per kilometre at EC2 prices.
_______________________________________________ Routing mailing list Routing@openstreetmap.org http://lists.openstreetmap.org/listinfo/routing
