Geek Answers Handbook

Select an open list of algorithms *

I understand that in the A * algorithm, when performing the next step, the step with the next lowest predicted value should be selected from an open list or border, but when there are several smallest steps, all with the same predicted value, are there any preferences for which to choose?

I think the latter in the first step may work better, but I'm not sure if there is a better way to choose the next step when there are several comparable costs.

+4
source share
4 answers

According to A *, all stages with an equal appraised value (value from the beginning plus a heuristic) are equally worthy of attention.

, ; , , , .

f(x) = g(x) + h(x), , :

  • x, , ( ): , , ;
  • x h, ( , A *).

, , / (f, h), f. , :

 *
/ \
| |
\ /
 +

, , , ( , ).

, x h, , .

0

, (AKA A * -epsilon).

f(v) = g(v) + (1+eps)h(v). eps , "" "" .

, , , eps - - .

+1

, , , - , , , .

, , ith prime . .

0

node G, .

http://movingai.com/astar.html

, G .

, , " G" "last node". , - . , , ...

, , . http://movingai.com/benchmarks/

, A *, , ... /:)

In general, using the maps and scripts from the link above and my own implementation of A *, breaking ties by simply selecting the last node wins 90% of the time. On the other hand, there are several cards where breaking ties by choosing the highest G wins 90% of the time.

I would like to hear how this happens to you.

0
source

More articles:


All Articles