07-搜索之bfs-全文預(yù)覽
【正文】 8 在 2 3的矩形里： 2022/8/21 37 ?例如：從 a1到 e4 當目標出現(xiàn)在所擴展出的結(jié)點里，結(jié)果就找到了。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 否則輸出無解 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 } 若循環(huán)中找到目標 ,輸出結(jié)果 。 起始點加入隊列 。 否則， 從它擴展出子結(jié)點 ,全都添到隊尾 。 v1 0 V2 V4 V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v4 1 2022/8/21 31 定義一個隊列 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 否則輸出無解 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 } 若循環(huán)中找到目標 ,輸出結(jié)果 。 起始點加入隊列 。 否則，從它擴展出子結(jié)點 ,全都添到隊尾 。 v1 0 V2 V4 V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 v2 1 2022/8/21 27 定義一個隊列 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 否則輸出無解 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 } 若循環(huán)中找到目標 ,輸出結(jié)果 。 起始點加入隊列 。 否則，從它擴展出子結(jié)點 ,全都添到隊尾 。 v1 0 V2 V4 V1 V6 V5 v2 1 v4 1 v5 1 v6 1 v1 0 2022/8/21 23 定義一個隊列 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 否則輸出無解 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 } 若循環(huán)中找到目標 ,輸出結(jié)果 。 起始點加入隊列 。 否則，從它擴展出子結(jié)點 ,全都添到隊尾 。 v1 0 V1 隊列結(jié)點記錄兩個信息 1：頂點編號 2：步數(shù) 2022/8/21 19 定義一個隊列 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 這個結(jié)構(gòu)是普遍適用的。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 //搜索過程沒有回溯，是一種犧牲空間換取時間的方法。 不撞南山不回頭 。 2022/8/21 11 過河問題（ con 5） 2022/8/21 12 過河問題（ con 6） ?普通狀態(tài) 可以用 4個整數(shù)表示 ?壓縮狀態(tài) 用 4個 bit表示 (char型有 8個 bit，足夠用 )。用 0表示在左岸，1表示在右岸。 ? 狀態(tài)空間： 一個“圖”，圖結(jié)點對應(yīng)于狀態(tài)，點之間的邊對應(yīng)于狀態(tài)轉(zhuǎn)移。 ?本節(jié)目標：希望同學們對于任意一個問題， 2022/8/21 3 搜索分類 ?盲目搜索 ： 按預(yù)定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。 ?但由于它巨大的局限性和自身靈活性，也被認為是最難學難用的算法之一。 ? 狀態(tài)轉(zhuǎn)移： 問題從一種狀態(tài)到另一種或幾種狀態(tài)的操作。問此人應(yīng)如何過河 ? 2022/8/21 7 過河問題（ con 1） ? 狀態(tài)：建立四元組（人，狗，雞，米）。 ?搜索樹的結(jié)點個數(shù)、分枝數(shù)、深度，決定著搜索的效率。 你總是先摸最接近你的地方 ， 如果沒有 ， 再摸遠一點的地方 …… ?深搜例子：走迷宮 ， 你沒有辦法用分身術(shù)來站在每個走過的位置 。直到圖中所有頂點均被訪問到。 while(隊列不空 ) { 取出隊頭結(jié)點 。 否則輸出無解 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 否則輸出無解 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 v1 0 V1 2022/8/21 20 定義一個隊列 。 否則，從它擴展出子結(jié)點 ,全都添到隊尾 。 起始點加入隊列 。 } 若循環(huán)中找到目標 ,輸出結(jié)果 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 否則輸出無解 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 v1 0 V2 V4 V1 V6 V5 v2 1 v4 1 v5 1 v6 1 2022/8/21 24 定義一個隊列 。 否則，從它擴展出子結(jié)點 ,全都添到隊尾 。 起始點加入隊列 。 } 若循環(huán)中找到目標 ,輸出結(jié)果 。 while(隊列不空 ){ 取出隊頭結(jié)點 。 否則輸出無解 。 若它是所求的目標狀態(tài) ,跳出循環(huán) 。 v1 0 V2 V4 V1 V6 V5 v2 1 v4 1 v5 1 v6 1 V3 v3 2 2022/
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1