Skip to main content
Share Your Experience: Take the 2024 Developer Survey
4 votes

What are the differences between uniform-cost search and greedy best-first search?

In the case of UCS, the evaluation function (that is, the function that is used to select the next node to expand) is $f(n) = g(n)$, where $g(n)$ is the cost of the path from the initial node to $n$, ...
3 votes

What is the difference between hill-climbing and greedy best-first search algorithms?

Let's see their definition first: Best First Search (BFS): ‌ Best-first search is a search algorithm that explores a graph by expanding the most promising node chosen according to a specified ...
OmG's user avatar
  • 1,816
2 votes

How does best-first search differ from hill-climbing?

Best-first search BFS is a search approach and not just a single algorithm, so there are many best-first (BFS) algorithms, such as greedy BFS, A* and B*. BFS algorithms are informed search algorithms, ...
nbro's user avatar
  • 40.8k
1 vote

What does the statement with the max do in the recursive best-first search algorithm?

This is probably more easily understood as the collapse/restore macro. The idea is that the previously explored state was collapsed and only the minimum f-cost from the sub-tree was stored. This ...
Nathan S.'s user avatar
  • 371
1 vote

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

I was struggling with the same question. This is what I came up with after thinking it through. With depth-first-search, you backtrack to a node that is a non-expanded child of your parent (or the ...
Thomas's user avatar
  • 11
1 vote

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

After spending some time on the problem, I concluded that it is due to the fact that we need to store the heuristic function evaluations for all nodes during the traversal. So, one might claim that it ...
iRestMyCaseYourHonor's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible