0
设想一条线，有两个节点，A为-10，B为10，使用单向搜索，我们从（-30,10）搜索并使用双向搜索从（-20,0）和0,10）和（10,20）。无论哪种方式，我们正在寻找40个步骤。现在，如果我们用多邻居来扩展这一点，不难看出双向并非与单向搜索不同。我在这里弄错了什么。为什么在BFS中bidrectional搜索更高效？
A
回答
4
如果状态图是一条线，那么没有增益。如果在距离内节点的数量增长超过线性，则获得增益。比较半径为r（约A）的圆的面积与半径为r/2的两个圆的面积（以A和B为中心）。
的（绿色）后者越小。它在更多方面更具戏剧性。在很多图中，节点的数量随着半径呈指数增长，然后改善更大。
0
一般来说，它对某些类型的稀疏图而言可能会更快。然而，由于它与单向搜索一样好（即它永远不会变慢），并且不会更复杂，所以通常是优选的。
可以说最短路径有6个节点。在单向上，你需要找到全部6个，假设每个节点都连接到2个其他节点。您平均需要搜索大约64个（2^6个节点才能找到最短路径，对吗？相比之下，在双向算法中，每个搜索只需要找到3个（或4个，取决于实施）节点，这会只需要访问每个节点8（2^3）或16（2^4）个节点，总共需要16或32个，具体取决于您是否可以在邻居（更快）时结束搜索，或者每次搜索发现相同的节点（不那么快）
这种差异在我们的小图中可能看起来并不多，但是图越大越密集，差异越明显对于具有分支因子6的图，每个节点是连接到6个其他节点，距离为20（仍然不是特别大的图），数字将是3.6 * 10^15和1.2 * 10^8，这个差值快7个数量级。这种差异放大到一个图表Google地图的大小。