UCS 是最佳的（但不一定是完整的）

让我们首先回顾一下，统一成本搜索 (UCS) 是最优的（即，如果它找到了一个解决方案，除非边上的成本足够大，否则不能保证该解决方案是最优的）并且它扩展了具有最小值的节点评价函数$f(n) = g(n)$， 在哪里$g(n)$是从目标/开始节点到的路径的长度/成本$n$.

使用 UCS 进行双向搜索是最优的吗？

使用 UCS 进行前向和后向搜索的双向搜索的问题是 UCS 不会像广度优先搜索那样逐层进行，这样可以确保当前向和后向搜索相遇时，已经找到了最优路径，假设它们在每次迭代时都扩展一个级别），因此前向搜索可能会探索搜索空间的一部分，而后向搜索可能会探索不同的部分，并且可能会发生（尽管我没有证据：我需要再想一想！），这些搜索不满足。所以，我会考虑这两种情况：

• 当前向和后向搜索不“相遇”时（最坏的情况，在时间和空间复杂度方面）

• 当他们相遇时（非退化案例）

退化案例

让我们考虑前向搜索不满足后向搜索的情况（最坏/退化的情况）。

如果我们假设边上的成本足够大并且起始节点$s$可以从$g$（反之亦然），然后双向搜索最终退化为两个独立的统一成本搜索，它们是最优的，这也使得 BS 也是最优的。

非生成案例

让我们考虑前向搜索遇到后向搜索的情况。

为了确保最优性，我们不能在两个边界相同时停止搜索$n$. 要了解原因，请考虑此示例。我们起飞第一个前沿节点$n_1$有成本$N$，那么我们取同一个边界节点$n_2$有成本$N+10$. 同时，我们起飞另一个前沿节点$n_2$有成本$K$和节点$n_1$有成本$K + 1$. 所以，我们有两条路径：一条带成本$N+(K + 1)$和一个有成本的$(N+10)+K$, 大于$N+(K + 1)$，但我们都离开了两个边界$n_2$第一的。

有关可能有助于了解 BS 的适当停止条件的更多详细信息和资源，请参阅其他答案。

这取决于停止条件。如果停止条件是“前向和后向扫描都遇到任何顶点就停止”，那么双向统一成本搜索不是正确的算法——它不能保证输出最优路径。但是可以调整停止条件，使双向均匀成本搜索保证输出最优解。

有关详细信息以及正确的停止条件，请参阅以下资源：

从外部存储器计算点对点最短路径。安德鲁·V·戈德堡、雷纳托·F·韦内克。亚历克斯/美国铝业公司 2005。

带预处理的点对点最短路径算法。安德鲁诉戈德堡。计算机科学理论与实践当前趋势国际会议，2007 年。

高效的点对点最短路径算法。Andrew V. Goldberg、Chris Harrelson、Haim Kaplan、Renato F. Wemeck。

我通过查看有关双向搜索的 Wikipedia 文章找到了这些资源；它提到终止条件已由 Andrew Goldberg 等人阐明，并引用了上面的第三个参考文献。然后在 Google Scholar 上快速搜索一下，其他论文也立即出现了。

未来的教训：花一点时间检查标准资源（例如 Wikipedia 和教科书）和检查文献（例如，使用 Google Scholar）会很有用。许多自然问题已经在文献中得到解答。