Hi Arndt,
I've been following this thread for a while now. I also did some reading
up on the A* algorithm. But my non-academic brain cells got short
circuit pretty quick. But your explanation is hugely helpful and is
super easy to follow. So thanks for that! I makes much more sense now.
Still, if I could bribe you with a beer (or two) maybe then you would be
able to provide some additional easy to follow links? Even easier to
follow then Wikipedia? Even better, post something of this quality (but
a bit more elaborate) on your personal web space? That would make you
king of the hill of A* !!! :-D
Thanks a million!
Ceaus.
Op 09-03-2020 om 19:02 schreef 'Arndt' via OsmAnd:
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]
<mailto:[email protected]>.
To view this discussion on the web visit
https://groups.google.com/d/msgid/osmand/a624e0fa-fa7f-4faa-a302-90653a33ae7a%40googlegroups.com
<https://groups.google.com/d/msgid/osmand/a624e0fa-fa7f-4faa-a302-90653a33ae7a%40googlegroups.com?utm_medium=email&utm_source=footer>.
--
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/3be182d1-aa08-f073-7402-03cd1cc97f9d%40gmail.com.
