雪之精灵

从吐丝结茧到破茧而出

DFS,BFS,DFS+ID

In a Nutshell Search Time Space When to use
    DFS O(c k) O(k) Must search tree anyway, know the level the answers are on, or you aren't looking for the shallowest number.
    BFS O(c d ) O(c d ) Know answers are very near top of tree, or want shallowest answer.
    DFS+ID O(c d) O(d) Want to do BFS, don't have enough space, and can spare the time.
d is the depth of the answer k is the depth searched d <= k Remember the ordering properties of each search. If the program needs to produce a list sorted shortest solution first (in terms of distance from the root node), use breadth first search or iterative deepening. For other orders, depth first search is the right strategy. If there isn't enough time to search the entire tree, use the algorithm that is more likely to find the answer. If the answer is expected to be in one of the rows of nodes closest to the root, use breadth first search or iterative deepening. Conversely, if the answer is expected to be in the leaves, use the simpler depth first search. Be sure to keep space constraints in mind. If memory is insufficient to maintain the queue for breadth first search but time is available, use iterative deepening.
    quote from http://ace.delos.com/usacotext2?a=y9SZdbB6WeB&S=rec

posted on 2008-10-22 19:02 雪之精灵 阅读(521) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理