"'Arndt' via OsmAnd" <osmand@googlegroups.com> writes: > I guess we are close to a consensus, but let me explain some more > background why hc>1 is not yet "unconditional surrender" but hc > x is, and > how you can find out what x is. > > The heuristic cost used in A* is the "minimum remaining cost" and is > calculated by assuming there's an "optimal" road along the bee-line. > "Optimal" in OsmAnds sense is a road where you can travel at 130kmh. > > The real-life remaining cost will be higher as this bee-line cost by a > factor "x" for two reasons: 1) roads are not bee-lines 2) some roads have > lower speeds due to classification or speed-limits. > > So if you increase the heuristic cost by a heuristic coefficient hc < x, it > is still a good estimate for the remaining cost. The elliptic A*-search > area is stil an elipitic area, it just narrows. Computing times still go > quadratic with distance. I would agree to call that "pragmatic tuning", not > "unconditional surrender" > > Things change if you are going for hc > x. There will be no elipitic > search-area, but the search quickly follows roads pointing in the right > direction. This is a linear search. Computing time goes linear with > distance, not quadratic. Very fast, but also very bad results. You cannot > find an optimal solution simply because you are not searching for it.
Thanks; that's a very useful explanation. > So yes, if you know you "x" and are pretty sure the your hc stays well > below, fine. We don't know x, it seems. I wonder if an algorithm that starts with hc sort of too high, but high enough to be known to be adequately fast, perhaps 1.5, and then if the computation finishes in a reasonable period of time, recompute with 1.4, and so on. Perhaps this could be done more aggressively when on external power, and less so on battery. (IMHO, navigating 500 km routes on the phone's internal battery makes little sense anyway.) For bonus points, there could be a page that explains the overall minimized metric and computing time for each hc, so you can understand where the breakpoint was. > But why not lower the "x" itself? Same effect on computing times, but > correct results. I don't see how you can change x. x is basically a property of the map graph, which is about the typical shortest actual path between places. > You can easily do that by lowering the "maxSpeed" in the routing.xml from > 130kmh to 100kmh. I don't follow how that's correct, if there really are roads you can drive 130 km/h on. (Around me, there are definitely roads with that as the normal speed, despite posted limits.) -- You received this message because you are subscribed to the Google Groups "OsmAnd" group. To unsubscribe from this group and stop receiving emails from it, send an email to osmand+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/osmand/rmizhcps6gy.fsf%40s1.lexort.com.
