第七講搜索-展示頁(yè)
2024-10-23 13:01本頁(yè)面
【正文】 是一個(gè)移動(dòng)序列，使得移動(dòng)后結(jié)果變成 //本程序在 ai上會(huì)超內(nèi)存，在 acm上能過(guò) include iostream using namespace std。 此方案比方案 1省空間； 此方案需要編寫(xiě)給定排列求序號(hào)和給定序號(hào)求排列的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的 9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。 此方案需要編寫(xiě)字符串形式的 9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。位序列最多需要 99位，因此存放位序列的數(shù)組需要 99/8 + 1個(gè)字節(jié) 48427562字節(jié)。 判重需要一個(gè)標(biāo)志位序列，每個(gè)狀態(tài)對(duì)應(yīng)于標(biāo)志位序列中的 1位，標(biāo)志位為 0表示該狀態(tài)尚未擴(kuò)展，為 1則說(shuō)明已經(jīng)擴(kuò)展過(guò)了 標(biāo)志位序列可以用字符數(shù)組存放。 void DFS(int depth){ for(node的每一個(gè)可行變化 ){ 改變 node DFS(depth + 1) 恢復(fù) node } } 此種做法需要一個(gè)全局?jǐn)?shù)組 array來(lái)存放每個(gè)走過(guò)的 node， array[depth]就是進(jìn)入 DFS函數(shù)時(shí)需要擴(kuò)展的節(jié)點(diǎn) 判重 ? 判重 ? 新擴(kuò)展出的結(jié)點(diǎn)如果和以前擴(kuò)展出的結(jié)點(diǎn)相同，則這個(gè)新節(jié)點(diǎn)就不必再考慮。第七講 搜 索 程序設(shè)計(jì)實(shí)習(xí) 內(nèi)容提要 ? 枚舉與搜索 ? 搜索 ? 廣度優(yōu)先搜索 ? 深度優(yōu)先搜索 ? 影響搜索效率的因素 ? POJ 1011 木棍問(wèn)題 枚舉 ?逐一判斷所有可能的方案是否是問(wèn)題的解 ? 例 1：求出 AI這九個(gè)字母對(duì)應(yīng)的數(shù)字 （ 19） ，使得下式成立 （ 一一對(duì)應(yīng) ） ABCD E FGHI 枚舉 ? 解法： ?枚舉 ABCDE的值 ， 計(jì)算乘積 ，判斷是否符合要求 。 ABCD E FGHI 搜索 ? 搜索：高級(jí)枚舉 ? 有順序有策略地 枚舉狀態(tài)空間中的結(jié)點(diǎn) ， 尋找問(wèn)題的解 …… 例題： POJ1077八數(shù)碼問(wèn)題 1 2 3 4 5 6 7 8 8 2 3 1 4 6 5 7 例題： POJ1077八數(shù)碼問(wèn)題 ? 狀態(tài)空間 8 2 3 4 1 6 5 7 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 8 2 4 1 3 5 7 6 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索 ? 優(yōu)先擴(kuò)展淺層結(jié)點(diǎn) ， 逐漸深入 第一層 第二層 第三層 8 2 3 4 1 6 5 7 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 8 2 4 1 3 5 7 6 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索 ? 用隊(duì)列保存待擴(kuò)展的結(jié)點(diǎn) ， 從隊(duì)首隊(duì)取出結(jié)點(diǎn) ， 擴(kuò)展出的新結(jié)點(diǎn)放入隊(duì)尾 ， 直到找到目標(biāo)結(jié)點(diǎn) （ 問(wèn)題的解 ） 8 2 3 4 1 6 5 7 8 2 3 4 1 5 7 6 8 2 4 1 3 5 7 6 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索的代碼框架 BFS(){ 初始化隊(duì)列； while( 隊(duì)列不為空 且 未找到目標(biāo)結(jié)點(diǎn) ){ 取隊(duì)首結(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的結(jié)點(diǎn)放入隊(duì)尾； 必要時(shí) 要記住每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)； } } 深度優(yōu)先搜索 ? 深度優(yōu)先搜索 ? 優(yōu)先 深入 遍歷靠前的結(jié)點(diǎn) 8 2 3 4 1 6 5 7 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 0 7 8 2 4 1 3 5 7 6 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 深度優(yōu)先搜索 ? 深度優(yōu)先搜索 ?可以用棧實(shí)現(xiàn) ， 在棧中保存從起始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)； 8 2 3 4 1 6 5 7 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 深度優(yōu)先搜索 ? 深度優(yōu)先搜索的棧實(shí)現(xiàn) （ 非遞歸 ） 框架 DFS(){ 初始化棧； while( 棧不為空 且 未找到目標(biāo)結(jié)點(diǎn) ){ 取棧頂結(jié)點(diǎn)擴(kuò)展，擴(kuò)展出的結(jié)點(diǎn)放回棧頂； } …… } 深度優(yōu)先搜索 ? 深度優(yōu)先搜索的 遞歸 框架 type node。 ? 如何判重？ 重復(fù) ? 8 2 3 4 1 6 5 7 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 0 7 8 2 4 1 3 5 7 6 8 2 3 4 1 5 7 6 8 2 3 4 1 6 5 7 判重 ? 需要考慮的問(wèn)題 ? 狀態(tài)數(shù)目巨大，如何存儲(chǔ)？ ? 怎樣才能較快的找到重復(fù)結(jié)點(diǎn)？ 時(shí)間 空間 判重 ? 合理編碼，減小存儲(chǔ)代價(jià) ? 不同的編碼方式所需要的存儲(chǔ)空間會(huì)有較大差別
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1