The difference between Best-First Search and A* Search lies primarily in their evaluation functions and the way they handle past knowledge and optimality. Here is a detailed comparison:
Evaluation Function
Best-First Search: The evaluation function for Best-First Search is $$ f(n) = h(n) $$, where $$ h(n) $$ is the heuristic function that estimates the cost from the current node $$ n $$ to the goal node. This means it only considers the estimated cost to reach the goal from the current node, without taking into account the cost already incurred to reach the current node[1][2][7].
A Search*: The evaluation function for A* Search is $$ f(n) = g(n) + h(n) $$, where $$ g(n) $$ is the cost from the start node to the current node $$ n $$, and $$ h(n) $$ is the heuristic function. This means A* Search considers both the cost incurred to reach the current node and the estimated cost to reach the goal from the current node[1][2][3].
Past Knowledge
Best-First Search: This algorithm does not involve past knowledge. It only uses the heuristic function to guide the search[1][2].
A Search*: This algorithm involves past knowledge by incorporating the cost $$ g(n) $$ from the start node to the current node in its evaluation function. This helps in ensuring that the path found is optimal[1][2][3].
Completeness
Best-First Search: Best-First Search is not complete, meaning it does not guarantee finding a solution if one exists[1][2][7].
A Search*: A* Search is complete, meaning it will find a solution if one exists, provided the heuristic function $$ h(n) $$ is admissible (i.e., it never overestimates the cost to reach the goal)[1][2][3].
Optimality
Best-First Search: Best-First Search is not optimal. The path found may not be the shortest or least costly path[1][2][7].
A Search*: A* Search is optimal, meaning it guarantees finding the shortest or least costly path, provided the heuristic function $$ h(n) $$ is admi...
