Talk:Best-first search

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)

• Agree. Zargulon 13:38, 12 September 2006 (UTC)
• Done. JonH 13:55, 12 September 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

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.

JonH (talk) 16:58, 28 March 2008 (UTC)

Is Dijkstra's algorithm really a best-first search?

I don't think so, it doesn't really `expanding the most promising node chosen according to a specified rule' and doesn't uses any heuristic function. I think A* search is a specialization of Dijkstra's algorithm and not converse. —Preceding unsigned comment added by 62.47.223.189 (talk) 10:06, 19 April 2009 (UTC)

It isn't. Removed statement. —Preceding unsigned comment added by 76.178.169.77 (talk) 08:36, 30 July 2009 (UTC)

Actually it is my understanding that most experts would consider Dijkstra's single-source shortest-path algorithm an example of best-first search. As explained in the article, best-first search expands nodes based on an evaluation function, denoted f(n). (For the algorithm, see BF* in Dechter & Pearl, "Generalized Best-First Search Strategies and the Optimality of A*," JACM 32(3) 1985.) Different best-first search algorithms can be constructed with different evaluation functions. Assuming additive costs, the following evaluation functions result in well-known algorithms. Note: g(n) = the sum of the edge costs on the path from the start to n, h(n) = a lower bound on the cost of any path from n to the nearest goal, depth(n) = the number of edges on path from start to n.

• f(n) = depth(n), breadth-first search
• f(n) = g(n), uniform-cost search, i.e., Dijkstra's algorithm
• f(n) = h(n), pure heuristic search
• f(n) = g(n) + h(n), A*

I think the entire introduction of this article should be rewritten to explain this. Any objections? Anyone agree? Alexdow (talk) —Preceding undated comment added 01:52, 7 August 2009 (UTC).

I agree with the explanation of Alexdow, and would add two points. By setting f(n) = -depth(n) you get depth-first search. Although breadth-first and depth-first search can be implemented as special cases of best-first search, there are more efficient implementations that do not require a priority queue.

But I am not so sure that the entire introduction (the lead) needs to be rewritten. I think it is the best part of the article because it precisely explains what the words mean. (Perhaps I am just defensive because the introduction is largely the result of my previous rewriting.) I think a better idea is to create a new section such as "Relationship to other algorithms" and to move everything about greedy best-first search (a.k.a. pure heuristic search) into that section. JonH (talk) 12:19, 10 August 2009 (UTC)

Algorithm Unclear

I think the following line is unclear:

  " b. Otherwise: change the parent if this new path is better than previous one."

I don't get this line: Has the parent node to be modified, or will the parenthood of the node be changed?!

Broken Link

http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html —Preceding unsigned comment added by 216.188.225.216 (talk) 11:53, 14 March 2011 (UTC)

Priority-first Search

Make PFS and Priority-first Search a redirect here and note it in bold. 100.8.208.187 (talk) 11:25, 4 July 2016 (UTC)