What is the difference between uniform-cost search and best-first search methods?
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).
There is a little misunderstanding in here. Uniform cost search, best first search and A* search algorithms are all different algorithms. Uniform cost is an uninformed search algorithm when Best First and A* search algorithms are informed search algorithms. Informed means that it uses a heuristic function for deciding the expanding node. Difference between best first search and A* is that best first uses f(n) = h(n) for expanding and A* uses f(n) = g(n)+h(n) for choosing the expanding node. h(n) is the heuristic function. g(n) is the actual cost from starting node to node n.
https://www.cs.utexas.edu/~mooney/cs343/slide-handouts/heuristic-search.4.pdf It can be seen here with more details.
Slight correction to the accepted answer
Best-first search does not estimate how close to goal the current state is, it estimates how close to goal each of the next states will be (from the current state) to influence the path selected.
Uniform-cost search expands the least cost node (regardless of heuristic), and best-first search expands the least (cost + heuristic) node.
- f(n) is the cost function used to evaluate the potential nodes to expand
- g(n) is the cost of moving to a node n
- h(n) is the estimated cost that it will take to get to the final goal state from if we were to go to n
The f(n) used in uniform-cost search
f(n) = g(n)
The f(n) used in best-first search (A* is an example of best-first search)
f(n) = g(n) + h(n)
Each of these functions is evaluating the potential expansion nodes, not the current node when traversing the tree looking for an n that is a goal state