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地圖的大小。