Tip:
Highlight text to annotate it
X
这里是答案。
广度优先搜索,顾名思义,以这种秩序扩展节点。
1,2,3,4,5,6,7。
因此,它一次横跨一条,广度优先。
它是最优的吗?
那么,它总是首先扩展最短的路径,
因此,无论目标藏在哪里,它终将通过检查最短的路径找到它,
所以实际上,它是最优的。
成本最低优先,首先扩展零长度的路径,
然后是长度为2的路径。
现在有一个长度为4的路径,和长度为5的路径,
路径长度为6,长度为7的路径,最后,长度为8的路径。
正如我们看到的,它保证找到所有成本最低的路径,
假设所有的各个步骤成本不是负值。
深度优先搜索,试图先走到尽可能远,
因此它这样走,1,2,3,然后回撤,4,
然后回撤,5,6,7。
你可以看到,它并不一定能找到所有的最短路径。
比方说,有目标在位置5和位置3。
它会发现在位置3的较长的路径,并找到目标
而不会找到位置5的目标。
因此,它不是最佳的。