Home (Breadth-first search)

 Artificial Intelligence 

What is what? Everything you always wanted to know.
  » »

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
It starts from the root node, explores the neighboring nodes first and moves towards the next level neighbors. It generates one tree at a time until the solution is found. It can be implemented using FIFO queue data structure.

Breadth-first search
In this strategy, the root node is expanded first, then all of the nodes generated by the root are expanded before any of their successors. Then these successors are all expanded before any of their successors.

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

~es 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 A Star Algorithm (A*) ...

In computer science, ~ (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. ...

~ which conservatively explores all alternatives at once, one node at a time (another informed search).
Uniform-cost search expands nodes which have the least cost-so-far first (uninformed).
Best-first search expands nodes which score best in some evaluation function.

gets round the exponential problem of ~ by expanding only the p most promising nodes at any level, and so at any level k there are only a total of pb nodes. However, this technique is not guaranteed to find a goal.
Method 5: Best-first search ...

Many algorithms textbooks describe graph searching algorithms that do not use heuristics (~, 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 ~
3.5.3 Lowest-Cost-First Search
3.6 Heuristic Search ...

Since most browsers encourage depth-first browsing, Letizia conducts a ~ 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 ~.

See also: See also: What is the meaning of Algorithm, Depth-first search, Search algorithm, Artificial intelligence, System?

◄ Branch and bound   Brute-force search ►
RSS Mobile