S*******C
发帖数: 822 | 1 有人说 worst time cost. 如果树里有环，DFS会不会结束。
有人说 it does not decide “what to do next” by examining the content of an
intermediate problem space, which means that it cannot take advantage of
noticing that the current state of the problem is near a solution.
还有人说
The disadvantage of Depth-First Search is that there is a possibility
that it may go down the left-most path forever. Even a finite graph can
generate an infinite tree. One solution to this problem is to impose a
cutoff depth on the search. Although the ideal cutoff is the solution depth
d and this value is rarely known in advance of actually solving the problem.
If the chosen cutoff depth is less than d, the algorithm will fail to find
a solution, whereas if the cutoff depth is greater than d, a large price is
paid in execution time, and the first solution found may not be an optimal
one.
Depth-First Search is not guaranteed to find the solution.
And there is no guarantee to find a minimal solution, if more than one
solution exists.
到底应该是什么缺点？ |
b********0
发帖数: 62 | |
S*******C
发帖数: 822 | 3 这是Amazon的面试题，就是问DFS通常有什么缺点？
【在 b********0 的大作中提到】
: 脱离具体问题谈 是不是有点没意义
|
n******n
发帖数: 12088 | 4 栈溢出，找最优解慢。
【在 S*******C 的大作中提到】
: 这是Amazon的面试题，就是问DFS通常有什么缺点？
|
n******n
发帖数: 12088 | 5 人工智能：现代方法，状态空间搜索那章，有BFS和DFS的详细对比
【在 n******n 的大作中提到】
: 栈溢出，找最优解慢。
|
S*******C
发帖数: 822 | 6 CC150上有这么一段话应该可以算DFS缺点
However, if we have a very large tree and want to be prepared to quit when
we get too far from the original node, DFS can be problematic; we might
search thousands of ancestors of the node, but never even search all of the
node's children. In these cases, BFS is typically preferred.
【在 n******n 的大作中提到】
: 人工智能：现代方法，状态空间搜索那章，有BFS和DFS的详细对比
|
n******n
发帖数: 12088 | 7 说的太细。
the
【在 S*******C 的大作中提到】
: CC150上有这么一段话应该可以算DFS缺点
: However, if we have a very large tree and want to be prepared to quit when
: we get too far from the original node, DFS can be problematic; we might
: search thousands of ancestors of the node, but never even search all of the
: node's children. In these cases, BFS is typically preferred.
|
c****8
发帖数: 76 | 8 如果跟Disk相关的话，那么DFS经常需要移动disk head去找下一个需要的读的数据，而
BFS可能可以整块读出来。 |
l*****n
发帖数: 199 | 9 我记得以前面dropbox的时候有问过我如何选择DFS或者BFS去找一个dir下的文件，好像
面试官想要的答案是如果dir很深就用BFS,如果很广就用DFS |
