Op ma 9 mrt. 2020 om 19:02 schreef 'Arndt' via OsmAnd < [email protected]>:
> 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]>: >> > > >> - 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 > > > Thanks for educating me. I must admit that your explanation of x was unknown to me. And indeed: Simply copying the default profile and lowering the max speed to 100 (what it will be in the Netherlands anyway after 16.03), does indeed result in shorter computation times. Question: Is there some mathemitcal approach to calculate or estimate the x for a certain route? Harry -- 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/CAGARPpvLWsF%2Bcw8Q5hsB_P6HbBYsK3ssgGg8NXMRTL2vJ99KGg%40mail.gmail.com.
