首页 文章

如何理解分支和边界中广度优先搜索的内存问题

提问于
浏览 次
1

我最近对分支定界方法感到困惑 . 分支定界方法有三种搜索策略：深度优先搜索，广度优先搜索和最佳优先搜索 . 所有的书籍和文献都指出，广度优先和最优先的将更多地记忆所使用的计算机 . 怎么理解这个？以二叉树为例，当从实时节点列表中取节点（父节点）进行处理时，生成两个子节点（或子节点）并插入到实时节点列表中，但应删除父节点因此，只有一个节点的内存增加 . 从这个角度来看，所有三种搜索策略都采用了与计算机相同的记忆 . 我对吗？它让我困惑了很久 . 有人能给我一些建议吗？

breadth-first-search branch-and-bound

1 回答

  • 0

    好，

    您可以考虑数据结构：

    Breadth-first-search: 它是作为队列实现的 . 展开节点（父节点）时，在队列中包含子节点 . 父节点已删除 . 我们举一个例子：

    enter image description here

    • 展开 45 ：我们在队列中包含20和70并删除45所以：

    20 | 70

    • 展开 20 ：我们从队列中扩展第一个节点并包括他的儿子：

    70 | 10 | 28

    • 展开 70 ：我们从队列中扩展第一个节点并包括他的儿子：

    10 | 28 | 60 | 85

    等等...

    如您所见，空间复杂度是指数的：O（
    enter image description here
    ）（b =分支因子; d =深度，最初为0）

    Deepth-first-search: 它是作为堆栈实现的：

    enter image description here

    • 展开 45 ：我们在堆栈中包含20和70并删除45所以：

    20 | 70

    • 展开 20 ：我们从堆栈顶部扩展第一个节点并包括他的儿子：

    10 | 28 | 70

    • 展开 10 ：我们从堆栈顶部扩展第一个节点并包括他的儿子：

    1 | 18 | 28 | 70

    等等...

    现在空间复杂度是线性的：O（d） . 两种算法的时间复杂度均为O（
    enter image description here
    ） .

    Best-first-search: 根据启发式评估函数f（n）对队列进行排序，并使用最佳f（n）扩展成功者 . 空间复杂度是线性的：O（d） .

    希望这可以帮助 .

    回复于

相关问题