Stack Overflow
Stack Overflow

Questions tagged [best-first-search]

11 questions
25
votes
4 answers

Is the greedy best-first search algorithm different from the best-first search algorithm?

Is the greedy best-first search algorithm different from the best-first search algorithm? The wiki page has a separate paragraph about Greedy BFS but it's a little unclear. My understanding is that Greedy BFS is just BFS where the "best node from…
Alex
  • 7,728
  • 3
  • 35
  • 62
18
votes
5 answers

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

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…
T.Poe
  • 1,949
  • 6
  • 28
  • 59
6
votes
2 answers

Is best first search optimal and complete?

I have some doubts regarding best first search algorithm. The pseudocode that I have is the following: best first search pseudocode First doubt: is it complete? I have read that it is not because it can enter in a dead end, but I don't know when can…
Ivan Sanchez
  • 79
  • 1
  • 1
  • 6
4
votes
0 answers

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

Best-first search - a search that has an evaluation function f(n) that determines the cost of expanding node n and chooses the lowest cost available node Uninformed search - has no knowledge of h(n) Informed search - has knowledge of h(n) Greedy…
user10939349
  • 41
  • 1
  • 3
3
votes
1 answer

If the A* search with the Euclidean Distance heuristic allowed diagonal moves, would it still be optimal?

So if I've got the A* search on a 10x10 maze with 10 obstacles and I allowed diagonal moves within this, would it still be optimal? My answer is that it would still be optimal, and this is because the Euclidean Distance calculates the straight line…
Kappa123
  • 361
  • 1
  • 3
  • 11
2
votes
1 answer

Constructing a graph path using a best first strategy

I want my program to construct a path using a best first(greedy) strategy (i.e the next point picked to be in the path will be the one closest to the current point), from a given list of lists of distances, where distances[i][j] is the distance…
RishtarCode47
  • 365
  • 1
  • 4
  • 18
1
vote
1 answer

Best-First-Search: Why are nodes with higher path costs explored again?

I am reading the book of Russell & Norvig: AIMA and wonder, why A* (Best-First-Search with f=g+h) does explore a node, even if it has already been explored with a lower PATH-COST. Following the example from John Levin, Best-First-Search expands the…
Manuel Schmidt
  • 2,429
  • 1
  • 19
  • 32
0
votes
0 answers

Python: Why are my children not creating children?

Here is the code: (from MAIN file) def BestFirstSearch(startingBoard): Q = [startingBoard] Visited = [] while (len(Q) != 0): Q.sort() currentQ = Q.pop(0) Visited.append(currentQ) # print(currentQ) …
Nikola Szymanska
  • 1
0
votes
0 answers

best success point

I have two classes of points "success" (1) and "failure" (0) in 2-dim XY-space, I am trying to find the best possible point (or region) of space where the success is highly likely. Meaning that if I take a new point that lands around that point (or…
Artashes
  • 102
  • 1
  • 9
0
votes
1 answer

Find local shortest path with greedy best first search algorithm

Recently I took a test in the theory of algorithms. I had a normal best first search algorithm (code below). from queue import PriorityQueue # Filling adjacency matrix with empty arrays vertices = 14 graph = [[] for i in range(vertices)] #…
Joachim Gotzz
  • 1
  • 1
  • 2
0
votes
1 answer

Lights Out Best-First Search/A* Algorithm

This is a homework assignment that I'm trying to develop more, but I'm having trouble figuring out how to go further. The assignment is basically about solving Lights Out of different sizes using different approaches. I have developed a brute-force…
sobosama
  • 150
  • 8