Home (Breadth-first search)

 Artificial Intelligence 

Home  
 
 
Home » Artificial Intelligence » Breadth-first search


 

Breadth-first search

Artificial Intelligence  Branch and bound  Brute-force search
04/24/2014

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


In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes.

Breadth-first search, uniform-cost search, and pure heuristic search are all special cases of a more general algorithm called best-first search.

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 ...

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.

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

Artificial Intelligence  Branch and bound  Brute-force search
04/24/2014

 
RSS Mobile