A heuristic function h(n) satisfies the monotone restriction if for all nodes ni and nj ,
h(ni) &le h(nj) + c(ni,nj)If h(n) satisfies this restriction (similar to the triangle inequality), then a node never has to be moved from closed back to open. In this case, closed could be eliminated, saving storage.
The effectiveness of a heuristic can be expressed as the effective branching factor, b*. b* is the inferred branching factor that would produce the actual number of nodes searched at the solution depth d.
Contents    Page-10    Prev    Next    Page+10    Index