Weighted A*

The Pull and the Push

Consider the function,

$f(n) = g(n) + w * h(n)$

where $w$ determines how much weight we give to the heuristic function.

$h(n)$ → manhattan distance

At one end of the spectrum is $w = 0$

with the pull of the source

and only the shortest path in mind

At the other end of the spectrum $w \rightarrow \infty$

with the push towards the goal

and only speedy termination in mind

Unlike Best First Search the Weighted A* algorithm does look back to consider the g-values and prefers this node to its child which is closer to the goal.
- It will in fact find a better path for its child than the one already found
The rapidly decreasing weighted heuristic pushes the search faster towards the goal, exploring less of the state space than the A* algorithm.

Weight	Algorithm
0	Branch and Bound
1	A*
2	Weighted A*
$\infty$ (the weight of g(n) is zero, that is, negligible)	Best First Search

The search spaces for A1 and A2 when h2(n) > h1(n).

Here h2 was more informed than h1

In weighted A* we can shrink this further but lose admissibility.

Untitled