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?).

Solution 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).

Solution 2

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.

Solution 3

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

Solution 4

The differences are given below:

• Uniform-cost search (UCS) expands the node with lowest path cost (i.e. with the lowest g(n)), whereas best-first search (BFS) expand the node with closest to the goal

• UCS cannot deal with a heuristic function, whereas BFS can deal with a heuristic function

• In UCS, f(n) = g(n), whereas, in BFS, f(n) = g(n) + h(n).

Solution 5

Uniform-cost search picks the unvisited node with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller.

Best-first search is an heuristic-based algorithm that attempts to predict how close the end of a path (i.e. the last node in the path) is to the goal node, so that paths which are judged to be closer to a solution are expanded first.

View more solutions