Geek asks and answers

What is the A * algorithm if the heuristic function H is not monotonic?

I tried to understand what would be the A * algorithm if the heuristic function does not satisfy the monotonicity condition, where in

h (u) <= e (u, v) + h (v), for any u, v such that there is an edge between u and v

is the monotonicity condition, where h is the heuristic function, u and v are the vertices in the search graph, and the function e sets the cost of edges between u and v (the search graph is not oriented). However, wikipedia (here) does not provide an algorithm for this and other sources, such as Norwig's book on artificial intelligence.

Is there a good source to study this. The pseudo code will be great!

In addition, I do not want to solve this by converting a nonmonotonic heuristic function into a heuristic.

+3
source share
2 answers

Assuming the heuristic function function is still admissible - the A * algorithm will work fine.

However, for non-monotonous heuristic functions, you may need to update an already "closed" node, and you must enable this behavior.

+2
source

In the case of a tree search, it is not necessary to be optimal. Instead, if the graph A * search is optimal only if the heuristic is valid and consistent.

In this figure, you can see an example of consistent heuristics: A * algorithm does not find the correct path.

example

, A *, @amit, , . , , , .

0

More articles:


All Articles