532
京東網上商城
【算法小總結】廣度優先搜索剖析
廣度優先搜索
以前一直用搜索用的都是深搜，因為聽說有很多題能用廣搜就能用深搜什麼的。今天老老實實的去看廣搜了，結果發現我之前想的太天真的，DFS和BFS不僅在性質上不同，而且對於某些題和某些情況，用BFS比DFS要快（不是絕對）。
今天好好說道說道這個BFS（廣度優先搜索）
很多問題（如過迷宮問題），每走下一步，都要考慮很多種情況，這個時候，就要每一步每一步的去試探，去找到合適的方案，也是就是傳說中的“搜索”。
當然，想試探出結果，可以去將一種方案走到底，遇到不能走或者其他不符合要求的情況再退回來，選擇下一個方案繼續嚐試，這種可以稱作所謂的“深度優先搜索”（DFS）;還有一種方式，就是所有方案我先都嚐試第一步，檢測是否找到結果，如果沒有，繼續嚐試所有方案的第二步。。。。直到找到合適的結果或方案，這種搜索方式成為“寬度優先搜索”。
當然，上麵的話是我自己對DFS和BFS的理解和概括，下麵是官方的總結（摘自ppt）
優先搜索也稱為寬度優先搜索，它是一種先生成的節點先擴展的策略。
廣度優先搜索算法如下：（用QUEUE）
(1) 把初始節點S0放入Open表中；
(2) 如果Open表為空，則問題無解，失敗退出；
(3) 把Open表的第一個節點取出放入Closed表，並記該節點為n；
(4) 考察節點n是否為目標節點。若是，則得到問題的解，成功退出；
(5) 若節點n不可擴展，則轉第(2)步；
(6) 擴展節點n，將其不在Closed表中的子節點放入Open表的尾部，並為每一個子節點設置指向父節點的指針，然後轉第(2)步。
讓我們來看看廣度優先搜索和深度優先搜索的區別在哪
首先這是我們要搜索的圖（圖片摘自互聯網）：
用深搜：
搜索方式：
路徑1 ==> A --> B --> E --> H 路徑2 ==> i
路徑3 ==> C 路徑4 ==> D --> F --> K --> L 路徑5 ==> G
用廣搜：
搜索方式：
路徑1 ==> A 路徑2 ==> B --> C --> D 路徑3 ==> E --> F --> G
路徑4 ==> H --> i --> K 路徑5 ==> L
如果要搜的答案在H，那麼很顯然深搜先搜到
如果答案在D，那麼廣搜比深搜先搜到
DFS與BFS的效率還是分情況描述的，所以我就不做過多比較。。。
我來說說我總結的廣搜過程：
1.建立一個空隊列，將根節點Root(搜索的初始第一步)放在隊首。
2.Root出隊列，同時將Root的所有可能情況（假設s1,s2,s3）壓入隊列
3.然後判斷隊首元素(s1)，判斷s1是否是可行情況，如果可行，將s1的下一步可行情況壓入隊列。s1出隊列。
4.接下來一直執行2、3兩步，直到找到答案或者全部搜索完畢。
如（圖畫的不好見諒！）
假設需要從1開始，找到5，隊列的變換過程如下：
開始1（此時隊列中有 1 （下麵先後順序按隊首到隊尾））
1出隊列，將1的可能解2，3加入隊列 （此時隊列中有 2 ，3）
2出隊列，將2的可能解4，5加入隊列 （此時隊列中有 3，4，5）
3出隊列，將3的可能解6，7加入隊列 （此時隊列中有 4，5，6，7）
4出隊列，將4的可能解8，9加入隊列 （此時隊列中有 5，6，7，8，9）
5出隊列，找到答案，結束。
可以看看下麵的例題：https://blog.csdn.net/acmman/article/details/38345509
最後更新：2017-04-03 05:39:37