On Friday, March 6, 2020 at 9:47:39 AM UTC+1, Harry van der Wolf wrote: > > > > Op vr 6 mrt. 2020 om 01:41 schreef 'Arndt' via OsmAnd < > [email protected] <javascript:>>: >
> - the other aspect is the "averge cost factor", so the ratio of average >> versus minimal cost, which should be close to 1 and is e.g. about 1.05 for >> the "car eco" profile, 1.16 for "car fast". It's important to be close to 1 >> here to keep the search area small. >> > > I don't believe at all in "unconditional surrender" when going away from > 1.0. (And obviously neither do all those other navigation app builders.) > Hi Harry, 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. So yes, if you know you "x" and are pretty sure the your hc stays well below, fine. But why not lower the "x" itself? Same effect on computing times, but correct results. You can easily do that by lowering the "maxSpeed" in the routing.xml from 130kmh to 100kmh. regards, Arndt -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/osmand/a624e0fa-fa7f-4faa-a302-90653a33ae7a%40googlegroups.com.
