What is the difference between uniform-cost search and best-first search methods?

Question

Both methods have a data structure which holds the nodes (with their cost) to expand. Both methods first expand the node with the best cost. So, what is the difference between them?

I was told that uniform-cost search is a blind method and best-first search is not, which confused me even more (both have information about node costs or not?).

Answer 1

The difference is in the heuristic function.

Uniform-cost search is uninformed search: it doesn't use any domain knowledge. It expands the least cost node, and it does so in every direction because no information about the goal is provided. It can be viewed as a function f(n) = g(n) where g(n) is a path cost ("path cost" itself is a function that assigns a numeric cost to a path with respect to performance measure, e.g. distance in kilometers, or number of moves etc.). It simply is a cost to reach node n.

Best-first search is informed search: it uses a heuristic function to estimate how close the current state is to the goal (are we getting close to the goal?). Hence our cost function f(n) = g(n) is combined with the cost to get from n to the goal, the h(n) (heuristic function that estimates that cost) giving us f(n) = g(n) + h(n). An example of a best-first search algorithm is A* algorithm.

Yes, both methods have a list of expanded nodes, but best-first search will try to minimize that number of expanded nodes (path cost + heuristic function).