I know that Breadth-first search & Depth-first search both of them are Uniformed Search, but what are the differences between them?

asked 11 Oct '11, 15:46

AUnshur's gravatar image

AUnshur
180118

retagged 13 Oct '11, 08:10

Merlin's gravatar image

Merlin
4.2k51429

Make sure you don't forget your second 'n'! UniNformed search...not to be confused with uniform cost search.
(17 Oct '11, 08:44) laconic laconic's gravatar image

In a Breadth-first search you explore each node at a given depth before moving on the the next level. So if you have a tree:

       A
  B         C
D   E     F   G

The search path would be A-B-C-D-E-F-G.

Depth first search explores all the way to the bottom of a path before moving backtracking up to another higher level child. so for the same tree the search path would be A-B-D-E-C-F-G.

link

answered 11 Oct '11, 16:15

EdK's gravatar image

EdK ♦
3.3k51134

This assumes that ties are broken by choosing the left most node. The search path would be different with alternate tie-breaking choices. The logic is right, though.
(17 Oct '11, 08:47) laconic laconic's gravatar image

Breath first is a careful search where you equally progress in all possible directions. If the goal is out there somewhere you will find it.

Depth first is a more aggressive and risk taking search where you choose one path and ignore all the other paths until you reach the end of your chosen path. If there is no end to that path you will continue forever which is why this approach is incomplete.

link

answered 11 Oct '11, 16:41

kindtb's gravatar image

kindtb
420313

take a look at videos 2.18-2.21. peter compares BFS and DFS (and UCS) with respect to optimality, completeness, and storage/memory costs; he also shows the traversal orders for each.

BFS is optimal and complete, but the frontier can get very large (O(2^n) nodes stored at level n in the search tree). DFS is neither optimal nor complete but you can store fewer nodes. Basically you end up storing your current path from the start state to the current node that you are expanding. So if you're at level n in the search tree, you're storing O(n) nodes.

Note that DFS could be complete if you store enough nodes in the explored list to avoid all repeated states, but that increases your storage costs.

link

answered 11 Oct '11, 16:18

nierman's gravatar image

nierman
34138

edited 11 Oct '11, 16:42

here is a nice animation in wikipedia explaining the idea of Breadth-first search: http://en.wikipedia.org/wiki/File:Animated_BFS.gif

link

answered 11 Oct '11, 17:28

hamda's gravatar image

hamda
11

Hello,

if we follow http://en.wikipedia.org/wiki/Depth-first_search then your A-B-C-D-E-F-G is correct. If we follow pages 86-86 from Artificial Intelligence - A modern approach - Russel-Norving 3rd edition, then it would be (from Left->Right) A-B-F-G-D-E, as the remove_choice is based on a FIFO queue.

link

answered 17 Oct '11, 08:43

aviguille's gravatar image

aviguille
1

Comment on the answer you are referring to. This is not a stand-alone answer.
(17 Oct '11, 08:58) laconic laconic's gravatar image

Although the implementation may be different (data structures, recursion vs. iteration, etc.) you can think of the way things working in this way. In BFS, children get added to a queue (FIFO) to be expanded. In DFS, children get added to a stack (LIFO). Notice how this causes deeper and deeper children to be explored first in DFS because those last nodes in are the ones you are going to expand first. Alternatively, BFS will expand children at the same depth-level first (they will be older in the queue than the next depth-level's children) before moving on to deeper children.

link

answered 17 Oct '11, 09:08

laconic's gravatar image

laconic
4929

Your answer
toggle preview

Follow this Question via Email

Once you sign in you will be able to subscribe for any updates here

Q&A Editor Basics

  • to upload an image into your question or answer hit
  • to create bulleted or numbered lists hit or
  • to add a title or header hit
  • to section your text hit
  • to make a link clickable, surround it with <a> and </a> (for example, <a>www.google.com</a>)
  • basic HTML tags are also supported (for those who know a bit of HTML)
  • To insert an EQUATION you can use LaTeX. (backslash \ has to be escaped, so in your LaTeX code you have to replace \ with \\). You can see more examples and info here

powered by OSQA