搜索(bfs-和-dfs)(編輯修改稿)
2024-08-21 08:21 本頁面
【文章內(nèi)容簡介】 5 6 7 1 2 3 4 5 6 0 一個(gè)例題 TOJ 1132 knight moves 分析： 狀態(tài)變?yōu)轳R的坐標(biāo)； 起點(diǎn)和終點(diǎn)意義不變； 鄰接點(diǎn)從上 下 左 右變?yōu)椤叭兆中汀钡? 8 個(gè)方向； 課下練習(xí)？ 恩！ 其他內(nèi)容 難點(diǎn)：狀態(tài)的表示等 優(yōu)化：雙向 BFS（已知初末狀態(tài)） 其他用處：求樹的直徑等 又一個(gè)引例 不互相攻擊的皇后 一個(gè) 8*8 的國際象棋棋盤上，最多能擺放多少個(gè) 不 互相攻擊的皇后？ DFS – 深度優(yōu)先搜索 DFS 在訪問圖中某一起始頂點(diǎn) A 后 ,由A出發(fā) ,訪問它的任一鄰接頂點(diǎn) B。再從B出發(fā) ,訪問與 B鄰接但還沒有訪問過的頂點(diǎn) E。 然后再從 E 出發(fā) , 進(jìn)行類似的訪問 , … 如此進(jìn)行下去 ,直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) G為止。接著 , 退回一步 , 退到前一次剛訪問過的頂點(diǎn) , 看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有 ,則訪問此頂點(diǎn) , 之后再從此頂點(diǎn)出發(fā) ,進(jìn)行與前述類似的訪問 。 如果沒有 , 就再退回一步進(jìn)行搜索。重復(fù)上述過程 , 直到連通圖中所有頂點(diǎn)都被訪問過為止。 8 9 A C D E G B F I H 1 2 3 4 5 7 6 虛線是回溯過程 I 深度優(yōu)先搜索（ DFS） void DFS( Point P ){ for(所有 P的鄰接點(diǎn) K){ if(K未被訪問 ){ 標(biāo)記 K。 DFS(K)。 } } } 每次遞歸到一個(gè)點(diǎn)，則檢查是否存在與它相鄰，而且未被訪問的點(diǎn)，有則 遞歸 訪問這個(gè)點(diǎn)，無則返回上一層。 通過比較 BFS 和 DFS 加深一下理解 廣度優(yōu)先搜索是按層次來搜索的，根據(jù)第一層遍歷出第二層，當(dāng)?shù)诙尤勘辉L問完之后，再處理第二層，由第二層訪問到第三層，依次類推，直到處理完最后一層。 深度優(yōu)先搜索是運(yùn)用堆棧，從第一層的一個(gè)點(diǎn)， 遞歸 到第二層的一個(gè)點(diǎn)，再遞歸到第三層，到最后一層后，在回溯到上一層，然后從上一層遞歸到它的下一層的另一個(gè)點(diǎn)，直到它的所有點(diǎn)都被訪問完，再回溯到上一層，依此類推，直到回溯到起點(diǎn)，這時(shí)所有的點(diǎn)都被訪問完，最后形成一棵樹的形狀。 在一些情況下， DFS 和 BFS 與其說是對圖的搜索，不如說是 對狀態(tài)的搜索 ，比如兩個(gè)引例，都可以看做對狀態(tài)的搜索 遞歸 調(diào)用自身 例如一個(gè)求階乘的函數(shù) f(int n) int f(int n) { if (n == 0) return 1。 return n*f(n1)。 } 遞歸 1）調(diào)用自身的思想 2）設(shè)置一個(gè)遞歸出口
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1