I'm just a beginner here trying to follow this discussion. I also did a (pretty naive) implementation of CH.<br><br>I guess even when A* would be ok 'in the could' or on a mobile device isn't it always better to use a more efficient algorithm considering battery life, the environment and the hosting costs of any routing solution? Computational power isn't free, even if users would be willing to pay for a solution like this someone else implements it smarter and better and you would have to keep up.<br>
<br>I use CH's for logistical optimization, it's very fast on many-to-many calculations, another use case where dykstra or it's variant A* is way too slow for any practical usage except maybe small areas with only a few customers.<br>
<br>Regards,<br><br>Ben<br><br><div class="gmail_quote">On Wed, Dec 12, 2012 at 1:12 PM, Dennis Luxen <span dir="ltr"><<a href="mailto:dennis.luxen@gmail.com" target="_blank">dennis.luxen@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
A* guarantees that the route is optimal for the given metric of<br>
cost. I assume that CH gives the same guarantee for the same metric<br>
and will therefore give exactly the same route.<br>
</blockquote>
<br></div>
Not necessarily true. There may be distinct path with equivalent weight.<br>
It will return a path of equal length but not necessarily the same one.<br>
<br>
Speaking of guarantees, I was thinking of search space sizes. A* is not<br>
able to give any assertion that it is indeed faster than Dijkstras<br>
seminal algorithm or uses less RAM.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I'm talking about real life routing: (A) In 2007 a mobile device<br>
typically had only 64MB RAM and a 300MHz processor. So, if you<br>
didn't have a routing hierarchy, it would take a minute or two to<br>
compute the average route a commuter would take.<br>
</blockquote>
<br></div>
We are mixing up terms here. Hierarchy can mean a number of distinct<br>
things. Most people speak of hierarchy when they simple prune the<br>
search, i.e. take only motorways at a certain point in the search.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
But now you have many phones and tablets with 1GB RAM and a 1GHz<br>
processor, so A* can buffer all the static data in RAM and only takes<br>
a few seconds.<br>
</blockquote>
<br></div>
If and only if the data fits into RAM. And thats going to deliver a<br>
rather crappy user experience when a user has to quit other apps just to<br>
have enough RAM.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
(B) Furthermore, most devices are now Internet enabled and long<br>
routes can be calculated in the cloud using A*.<br>
</blockquote>
<br></div>
A place where you certainly don't want A*.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I have demonstrated on many occasions that the longest routes in<br>
OpenStreetMap can be calculated fairly quickly on reasonable hardware<br>
e.g. only 30 seconds on a Xeon processor with 16 GB RAM.<br>
</blockquote>
<br></div>
'Fairly quickly' is a debatable term, here. Even for naive routing algorithms, this is a lot of computation.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If a normal driver calculates all his routes with A*, the<br>
computational cost will be less than one hundredth of a cent per<br>
kilometre.<br>
</blockquote>
<br></div>
That's some strange metric and awfully expensive for an online service thats mildly popular.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Insignificant compared to the cost of fuel, man hours,<br>
mobile bandwidth etc.<br>
</blockquote>
<br></div>
Well, 30 seconds is certainly significant when compared to a latency of hundred milliseconds or so on the cell network.<div class="HOEnZb"><div class="h5"><br>
<br>
______________________________<u></u>_________________<br>
Routing mailing list<br>
<a href="mailto:Routing@openstreetmap.org" target="_blank">Routing@openstreetmap.org</a><br>
<a href="http://lists.openstreetmap.org/listinfo/routing" target="_blank">http://lists.openstreetmap.<u></u>org/listinfo/routing</a><br>
</div></div></blockquote></div><br>