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

Poet

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

Edina

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. – Merrick

At the moment of evaluation, the heuristic function in best-first search is evaluating one of the next possible states, not the "current state". The following statement is untrue with regards to how a best-first search uses its heuristic function: "it uses a heuristic function to estimate how close the current state is to the goal". It would be true to say "it uses a heuristic function to estimate how close potential next states are to the goal." – Merrick

@Merrick 1. Check please some pseudocode to see that there is no problem with using the words "current state". 2. I never said it "evaluates the current state". I said it "estimates how close it is". There is nothing wrong with that statement. – Edina

When you are looking for the next node and starting from node A, and ultimately wanting to end up on node Z, the heuristic function in best-first search runs on node B,C,D,...,Y - it doesn't run on node A, ever. It doesn't even consider node A, and node A is the "current state". – Merrick

A more precise answer is achieved if you look also at this question What's the difference between best-first search and A* search? – Neisse

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

Anion

Answer 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) = h(n)

The f(n) used in A* search.

Note: The h(n) from best-first search above is expanded in A* so that it always includes g(n). It is still basically just a heuristic, but it is a heuristic that includes g(n).

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

Merrick

Nope f(n) = g(n) + h(n) is used by A* – Geldens

@Merrick you provided the link to wikipedia. Did you even yourself read it? Of course a star is a special case of best first search. But bfs and a* are different. Criteria for bfs is to use f(n) and expand the node with lowest f(n). In simple bfs it is simply f(n) = h(n). A* also uses f(n) thats why it is a specisl case of bfs. But its f(n) = g(n) + h(n) – Withstand

Thank you Francis it took me awhile to understand what you were saying. I've edited my answer. – Merrick

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

Stablish

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

Carlock

You say "with the lowest distance", what do you mean by "distance" here? Lowest distance to or from what? – Sassafras