Tip:
Highlight text to annotate it
X
鉴于非最优的深度优先搜索,
人们为什么还会选择使用它呢?
答案与存储空间需求有关。
在这里,我描述了一个由一个非常大的,
甚至无限的二叉树组成的状态空间。
随着我们从第1,2,3层,下降到n层,
树变得越来越大。
现在,让我们考虑这些搜索算法的边界。
广度优先搜索,我们知道边界看起来像这样,
所以在广度优先搜索中,当我们下到第n层时,
我们将需要2的n次方的存储空间来通过。
成本最低优先中,边界更加复杂。
我们需要理清这种成本的轮廓,才能知道,
但它也有类似的节点总数。
但深度优先搜索,当我们沿着树向下,我们开始走出这个分支,
然后我们回撤,但在任何时候,我们的边境只会有n个节点
而不是2的n次方个节点,这样的深度优先搜索会大幅节省空间。
现在,当然,如果我们也保持跟踪已探索的节点的集合,
我们就没有得到那么多的节省。
但是,如果没有已探索的节点的集合,在节约空间方面,
深度优先搜索就有着巨大的优势。
另一个我们需要考虑的算法的属性是完整性,
这意味着,如果某处有一个目标,
该算法会找到了吗?
所以,让我们从非常大的树转移到无限大的树,
比方说,有一些隐藏在该树的某深处的目标。
而问题是,这些算法中的每一个都是完整的吗?
也就是说,它们能保证找到可到达目标的路径吗?
您认为在这个意义上某个算法是完整的,就在其复选框上做标记。