|
Hello. I am reading Artificial Intelligence: The Modern Approach and can't understand one thing in the Recursive Best First Search (RBFS) algorithm. Here is a code of the algorithm from 3-d edition:
Two lines are confusing me:
Here for all successors for the current node we calculate their f-value, but why if parent's f value is greater than it's successor's f-value we assign parent's f-value? If new s.g + s.h is less then node.f this mean that heuristic estimation for a successor node is better than for a parent node, why should we ignore it and assign parent node's heuristic estimation to a successor's node? Thank you in advance. |
|
RBFS is a variation of A-star algorithm that using linear space. A-star algorithm, to be complete and optimal has several requirements for a heuristic function. Heuristic function should be:
This two requirements makes situation when f(parent_node) > f(successor_node) impossible. Heuristic function should be monotonic, to make possible to use GraphSearch in A* (GraphSearch is an implementation of a Dijkstra’s algorithm to find solution in state space where same states can appear several times). For more information you can read AIMA(Chpt 4 - Informed Search and Exploration) and Dijkstra’s algorithm |