Talk:Best-first search
From Wikipedia, the free encyclopedia
[edit] Suggested merge
See also Talk:Greedy best-first search
I have added a sentence here that notes the use of the name "greedy best-first search". I think Greedy best-first search can now just redirect to here. JonH 15:39, 24 August 2006 (UTC)
Greedy Best First Search is a Best First Search where the node evaluation function f(n) is defined as f(n) = h(n). It is also known as "Pure Heuristic Search", since the evaluation function disregards how hard is to get to the node (I need to look for a proper reference, but I think it is Richard Korf the one that introduced the term. 193.145.45.227 (talk) 15:31, 29 February 2008 (UTC)Miguel_Ramirez
[edit] Optimization of breadth-first or depth-first search
On 2002-11-17 the article said best-first search was an improved version of depth-first search, but this was quickly changed to "breadth-first". On 2004-12-01 it became "depth-first" and stayed that way until 2006-10-17 when it was changed back to "breadth-first". On 2007-11-28 it became "depth-first" again, but that was reverted again today.
Since editors cannot agree about this, does it actually help readers to say one thing or the other. As far as I can see, best-first search is neither breadth-first nor depth-first but is something different. I suggest changing the first sentence to say: "Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to some rule." JonH (talk) 19:23, 6 December 2007 (UTC)
- It's a combination of both breadth first AND depth first, but it's faster than both. I'd like to see a pseudo-code algorithm for these searches though... something like
-
- 1. Queue <- StartNode
- 2. While (GoalNotFound & QueueNotEmpty)
- ...etc.
- --90.210.122.240 (talk) 00:23, 31 January 2008 (UTC)
User:Abhijeetat has added a step-by-step version of the algorithm. I have tidied it up a bit, but I think it still needs work.
- I do not understand why there are two nested loops that both find the best node.
- It assumes that the problem requires finding a path, so it records the parent of each node. But best-first search can be used when the goal is just to find a state that satisfies some condition, and recording the parent is then unnecessary.
- It detects if a state has already been generated, and it updates the parent of the node if necessary, but it does not consider the possibility that the successors of the state are now more promising and the priority queue should be resorted. It may be necessary to add the node to OPEN again.
