07-搜索之bfs-展示頁
2025-08-02 02:45本頁面
【正文】 ： 按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。SEARCHING STRATEGIES ACM/ICPC 之 搜索篇 2022/8/21 2 搜索概論 ?搜索被稱為“通用解題法”，在算法和人工智能中占據(jù)重要地位。 ?但由于它巨大的局限性和自身靈活性，也被認(rèn)為是最難學(xué)難用的算法之一。 ?啟發(fā)式搜索 ： 在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向發(fā)展，加速問題的求解過程并找到最優(yōu)解。 ? 狀態(tài)轉(zhuǎn)移： 問題從一種狀態(tài)到另一種或幾種狀態(tài)的操作。 ? 搜索： 尋找一種可行的操作序列，從起始狀態(tài)經(jīng)過一系列狀態(tài)轉(zhuǎn)移，達(dá)到目標(biāo)狀態(tài)。問此人應(yīng)如何過河 ? 2022/8/21 7 過河問題（ con 1） ? 狀態(tài)：建立四元組（人，狗，雞，米）。 ? 起始狀態(tài) (0,0,0,0)，終止?fàn)顟B(tài) (1,1,1,1) ? 狀態(tài)轉(zhuǎn)移規(guī)則： (a,b,c,d) → (1a,1b,c,d)（當(dāng) a=b） → (1a,b,1c,d)（當(dāng) a=c） → (1a,b,c,1d)（當(dāng) a=d） → (1a,b,c,d) ? 約束： (a,b,c,d)中，當(dāng) a≠b時(shí) b≠c；當(dāng) a≠c時(shí) c≠d 2022/8/21 8 過河問題（ con 2） ?搜索： (0,0,0,0) →(1,1, 0,0) →(1,0,1,0) →(0,0,1,0) →(1,0,1,1) →(1, 0,0,1) →(1,1,1,0) →(1, 0,0,0) 2022/8/21 9 過河問題（ con 3） ? 搜索： → (1,0,1,1) →(0,0,0,1)→(1,1,0,1)→(0,1,0,1) →(1,1,1,1)ok →(0,0,1,0)→(1,0,1,1)→(0,0, 1,1) →(0,0, 1,1) →(1,1,1,0) →(0,0,1,0)→(1,0,1,1)→(0,0, 1,1) →(0,1,0,0)→(1,1,0,1)→(0,1,0,1) →(1,1,1,1)ok →(0, 1,1,0) 2022/8/21 10 過河問題（ con 4） ?搜索在“圖”中進(jìn)行，但圖不需要事先建立（“隱式圖”）。 ?搜索樹的結(jié)點(diǎn)個(gè)數(shù)、分枝數(shù)、深度，決定著搜索的效率。 ?用廣度優(yōu)先 (BFS, Breath First Search) 或 用深度優(yōu)先 (DFS, Depth First Search) 2022/8/21 13 BFS+DFS入門 ?顧名思義 ， 廣搜就是 “ 往廣了搜 ” ， 深搜就是 “ 往深了搜 ” 。 你總是先摸最接近你的地方 ， 如果沒有 ， 再摸遠(yuǎn)一點(diǎn)的地方 …… ?深搜例子：走迷宮 ， 你沒有辦法用分身術(shù)來站在每個(gè)走過的位置 。 2022/8/21 14 BFS思想 ? v0出發(fā)，在訪問了 v0之后，搜索 v0的 (所有未被訪問的 )鄰接頂點(diǎn) … ? ，廣搜圖中其它頂點(diǎn)，直至圖中所有已被訪問的頂點(diǎn)的鄰接頂點(diǎn)都被訪問到。直到圖中所有頂點(diǎn)均被訪問到。時(shí)間復(fù)雜度： O(V+E) 2022/8/21 15 BFS思想（ cont.） ? 樹 、 圖的 BFS演示 0 1 2 3 4 8 5 9 6 7 10 0 2 1 4 5 3 6 2022/8/21 16 BFS程序基本結(jié)構(gòu) 定義一個(gè)隊(duì)列 。 while(隊(duì)列不空 ) { 取出隊(duì)頭結(jié)點(diǎn) 。 否則，從它擴(kuò)展出子結(jié)點(diǎn) ,全都添到隊(duì)尾 。 否則輸出無解 。任何 非遞歸 的BFS程序都能套進(jìn)去 2022/8/21 17 BFS演示 ? 無向圖如下，邊權(quán)均為 1，求 V1到 V3的最短路徑 V3 V2 V4 V1 V6 V5 2022/8/21 18 定義一個(gè)隊(duì)列 。 while(隊(duì)列不空 ){ 取出隊(duì)頭結(jié)點(diǎn) 。 否則，從它擴(kuò)展出子結(jié)點(diǎn) ,全都添到隊(duì)尾 。 否則輸出無解 。 起始點(diǎn)加入隊(duì)列 。 若它是所求的目標(biāo)狀態(tài) ,跳出循環(huán) 。 } 若循環(huán)中找到目標(biāo) ,輸出結(jié)果 。 v1 0 V1 2022/8/21 20 定義一個(gè)隊(duì)列 。 while(隊(duì)列不空 ){ 取出隊(duì)頭結(jié)點(diǎn) 。 否則，從它擴(kuò)展出子結(jié)點(diǎn) ,全都添到隊(duì)尾 。 否則輸出無解 。 起始點(diǎn)加入隊(duì)列 。 若它是所求的目標(biāo)狀態(tài) ,跳出循環(huán) 。 } 若循環(huán)中找到目標(biāo) ,輸出結(jié)果 。 v1 0 V1 v1 0 V1不是終點(diǎn) 2022/8
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1