Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [best-first-search]

For questions related to the family of algorithms often denoted as best-first search algorithms. A* is an example of a best-first search algorithm.

9 questions
5
votes
1 answer

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

What are the differences between the uniform-cost search (UCS) and greedy best-first search (GBFS) algorithms? How would you convert a UCS into a GBFS?
Abbas Ali
  • 566
  • 3
  • 10
  • 17
4
votes
1 answer

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

I am reading the book "Artificial Intelligence: A Modern Approach" by Stuart and Norvig. I'm having trouble understanding a step of the recursive best-first search (RBFS) algorithm. Here's the pseudocode. What does the line s.f <- max(s.g + s.h,…
Just_Alex
  • 151
  • 4
3
votes
1 answer

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

How does best-first search differ from hill-climbing?
Ayesha Sajjad
  • 31
  • 1
  • 3
3
votes
2 answers

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

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found GBFS similar to DFS. It expands the whole branches…
iRestMyCaseYourHonor
  • 141
  • 1
  • 6
2
votes
1 answer

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

While watching MIT's lectures about search, 4. Search: Depth-First, Hill Climbing, Beam, the professor explains the hill-climbing search in a way that is similar to the best-first search. At around the 35 mins mark, the professor enqueues the paths…
calveeen
  • 1,251
  • 7
  • 17
1
vote
0 answers

What would happen if we set the evaluation function in the best-first search algorithm as the cost of paths taken to new nodes?

I am reading Artificial Intelligence: A Modern Approach. In Chapter 3, Section 3.3.1, The best-first search algorithm is introduced. We learn that in each iteration, this algorithm chooses which node to expand based on minimizing an evaluation…
Hamed
  • 21
  • 2
1
vote
0 answers

What is a example showing that the tree-based variant for the greedy best-first search is incomplete?

I understand that a tree-based variant will have nodes repeatedly added to the frontier. How do I craft an example where a particular goal node is never found. Is this example valid. On the other hand, how do I explain that the graph-based version…
goldilocks
  • 53
  • 1
  • 4
0
votes
1 answer

Which search algorithm expands nodes closest to the goal?

I want to know which search algorithm among A* and Best-First Search and Greedy First Search expands nodes closest to the goal. I have three opinions about A* and Best-First Search and Greedy First Search. As far as I know, Best-First Search is a…
ndycuong
  • 3
  • 1
0
votes
0 answers

How do I construct a state space that shows that Greedy Best First Search is not complete while A* is?

Construct a state space with appropriate heuristics and local costs. Show that Greedy Best First search is not complete for the state space. Also illustrate A* is complete and guarantees solution for the same state space. Here I can not come up…
npsulav
  • 1