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
Accepted

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 ...
  • 1,683
1 vote

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, ...
  • 35k
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 ...
  • 361
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 ...
  • 11
1 vote
Accepted

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

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