In the A* algorithm, at each step, the node to be expanded is chosen based on the function $f(n)$, which is the sum of the current cost $g(n)$ and the heuristic $h(n)$. This allows the algorithm to choose the most promising path, considering both the current cost and an estimate of the remaining cost to the goal.
$$f(n) = g(n) + h(n)$$
-
$f(n)$ is the total cost function.
-
$g(n)$ is the cost of the path from the start node to the current node $n$.
-
$h(n)$ is the heuristic, in this case, the Manhattan distance.
The formula for the Manhattan distance heuristic, represented by
$$\lvert x_{goal} - x_{n} \rvert + \lvert y_{goal} - y_{n} \rvert$$
Where $(x_{goal}, y_{goal})$ are the coordinates of the goal node and $(x_{n}, y_{n})$ are the coordinates of the current node $n$.
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze1.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze1_solution.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze1_explored.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze2.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze2_solution.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze2_explored.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze3.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze3_solution.png)
![img](/wesleey/python-artificial-intelligence/raw/main/search/informed/a-star/images/maze3_explored.png)