Home (Breadth-first search)

 Artificial Intelligence 

  » »
 
   

Breadth-first search

Artificial Intelligence  Branch and bound  Brute-force search

In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
Contents ...


Breadth-first search, uniform-cost search, and pure heuristic search are all special cases of a more general algorithm called best-first search. In each cycle of a best-first search, the node that is best according to some cost function is chosen for expansion.

Breadth-First Search:
- Remove a node from the queue. This becomes the current node.
- Place all child nodes of the current node onto the queue.
Newton's Method ...

Breadth-first searches are expanded across before moving down (Matthews, 2000a). Figure 2, adapted from Matthews (2000a), illustrates the order that the nodes are explored.
Figure 2 - Breadth-First Algorithm Node Expansion
2.2.1.1 A Star Algorithm (A*) ...

In computer science, breadth-first search (BFS) is a tree search algorithm used for traversing or searching a tree, graph. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...

Many algorithms textbooks describe graph searching algorithms that do not use heuristics (breadth-first search, depth-first search, Dijkstra's). Reading about them may help in understanding A*, which is a variant of Dijkstra's.

3.5.1 Depth-First Search
3.5.2 Breadth-First Search
3.5.3 Lowest-Cost-First Search
3.6 Heuristic Search ...

Since most browsers encourage depth-first browsing, Letizia conducts a breadth-first search concurrently for other useful locations that the user may be interested in. It does this by ëguessingí the userís intention and proceeding to search using the search engine.

beam search a search method that maintains a predetermined number of the best search paths found thus far at any given point. Thus, it considers more possibilities than depth-first search, but avoids the exponential number of possibilities of breadth-first search.

See also: See also: Algorithm, Depth-first search, Programming, Search algorithm, System

◄ Branch and bound   Brute-force search ►
 
RSS Mobile