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

user_6204637 0
Viewed 38078

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

uniform-cost-search best-first-search difference artificial-intelligence search
5 Answers

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.

user_79745110

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

user_37279140

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

user_67144300

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.

user_102694130
Related