Tip:
Highlight text to annotate it
X
所以,我们已经看了2个搜索算法。
一,广度优先搜索,在其中我们总是最先展开
最浅的路径,最短的路径。
其次,成本最低优先搜索,我们总是首先展开
总成本最低的路径。
我要借此机会,介绍第三个算法,深度优先搜索,
这是一种与广度优先搜索截然相反的搜索。
在深度优先搜索中,我们总是首先扩展最长的路径,
即具有最大长度的路径。
现在,我想让你们做一件事,告诉我们在每个树的每个节点,
它们以怎样的顺序扩展,
第一,第二,第三,第四,第五,等等,在这些圆圈中填入相应的数字。
而如果有平等关系的,以从左至右的顺序关系区分,并填入相应数字。
然后,我想你问一个问题,或回答一个问题
问题是,这些搜索是最佳的吗?
也就是说,它们能保证找到最好的解决办法呢?
广度优先搜索,最佳就意味着找到最短路径。
如果你认为它可以保证找到最短路径,请在此处打钩。
对于成本最低优先,这将意味着发现具有最低总成本的路径。
如果你认为它保证做到这一点,请在这里打钩。
我们将允许所有费用均是正值的假设。
在深入优先中,成本最低或最佳的意思是,
如在广度优先中一样,找到具有最短长度的路径。
如果你认为深度优先总是会找到那,请在这里打钩。