rgzn-2圖搜索技術(shù)中的狀態(tài)空間法(編輯修改稿)
2025-08-31 09:58 本頁面
【文章內(nèi)容簡介】 rasp} 第三節(jié) 搜索過程要點用圖 來說明 狀態(tài)空間。求解一個能滿足目標(biāo)條件的問題可以表達(dá)為搜索一個圖以找到一個滿足目標(biāo)狀態(tài)描述的節(jié)點問題。討論的所有狀態(tài)空間搜索方法可以由下列圖論方法來模擬：: 對應(yīng)于初始狀態(tài)描述。（又稱子節(jié)點） 把適用于某個節(jié)點狀態(tài)描述的一些算符用來推算該節(jié)點而得到的新節(jié)點，稱為該節(jié)點的后繼節(jié)點。令Γ為推算所有后繼節(jié)點的特別算符。我們把應(yīng)用Γ于某節(jié)點的過程叫做 擴(kuò)展一個節(jié)點。: 從每個后繼節(jié)點返回指向其父輩節(jié)點。當(dāng)最終找到目標(biāo)節(jié)點時，這些指針能夠指出一條回到起始節(jié)點的路徑。: 檢查各后繼節(jié)點看其是否為目標(biāo)節(jié)點。如果還沒有找到目標(biāo)節(jié)點，則繼續(xù)進(jìn)行擴(kuò)展節(jié)點和設(shè)置指針的過程。當(dāng)找到一個目標(biāo)節(jié)點時，沿著有關(guān)各指針可以從目標(biāo)節(jié)點回溯到起始節(jié)點，產(chǎn)生一條解答路徑。于是，對應(yīng)于這條路徑上各連線的有關(guān)狀態(tài)描述算符，就構(gòu)成一個解答序列。 對一個搜索過程的完全說明必須敘述被擴(kuò)展節(jié)點的次序。寬（廣）度優(yōu)先搜索: 如果搜索是以接近起始節(jié)點的程度(由節(jié)點間連接弧線的數(shù)目來衡量)依次擴(kuò)展節(jié)點的，就叫做寬度優(yōu)先搜索，這種搜索是逐層進(jìn)行的。深度優(yōu)先搜索: 如果搜索時首先擴(kuò)展最新產(chǎn)生的節(jié)點, 則稱為深度優(yōu)先搜索。上述兩種搜索方法都屬于盲目( 或稱無信息)搜索過程, 其節(jié)點的擴(kuò)展次序不受目標(biāo)節(jié)點位置的影響。 ( 有時也稱為規(guī)則) , 以產(chǎn)生后繼節(jié)點。 或者是在選擇一個后繼節(jié)點之后, 再選擇一個合適的算符以產(chǎn)生一個新的后繼節(jié)點。其他控制任務(wù)包括檢驗算符的適用條件, 測試終止條件以及記住用過的算符等。因此, 我們可以把控制系統(tǒng)( 即選擇和確定控制策略的系統(tǒng)) 進(jìn)行算符( 規(guī)則) 選擇的過程看做一個搜索過程。 對于許多任務(wù)來說, 有可能指出經(jīng)驗法則或原則來簡化搜索。任何這種用來加速搜索的技術(shù)取決于由圖表示問題的特別信息。我們稱這種信息為啟發(fā)信息。利用這些信息, 我們往往能夠首先擴(kuò)展最有希望的節(jié)點, 從而把搜索較快地推向目標(biāo). 。 S if ┅ then ┅ if ┅ then ┅控制策略費用規(guī)則應(yīng)用費用.G 系 統(tǒng) 總 費 用 控制策略費用規(guī)則應(yīng)用費用計 算 費 用(為選優(yōu)而增加的費用)搜索空間大小費用00 啟發(fā)信息量傳統(tǒng)的計算費用分為兩類：規(guī)則應(yīng)用費用和控制費用。一個完全無信息的控制系統(tǒng)只需要很少的控制費用，因為只是任意選取規(guī)則而不需要花費多少控制計算費用。但是，這種策略的規(guī)則應(yīng)用費用卻很高，因為一般說來，要找到一個解需要應(yīng)用大量的規(guī)則。第四節(jié) 狀態(tài)空間搜索策略 圖搜索策略顯示圖: 各節(jié)點及其具有費用的弧線由一張表明確給出。表: 每一節(jié)點 后繼節(jié)點及連接弧線費用對 大型圖 不切實際 對無限節(jié)點圖不可能隱式圖: 起始節(jié)點已知,后繼節(jié)點算符Γ已知 擴(kuò)展節(jié)點 顯示圖可將使用隱式圖的狀態(tài)空間中的各節(jié)點劃分為以下三類: 未生成節(jié)點暫不放入計算機(jī)存儲 已生成但尚未擴(kuò)展節(jié)點實現(xiàn)時放入一個OPEN表中 已擴(kuò)展節(jié)點實現(xiàn)時放入一個CLOSED表中 OPEN表格式 CLOSED表格式狀態(tài)結(jié)構(gòu)返回指針狀態(tài)結(jié)構(gòu)編號返回指針 一般的圖搜索過程如下：GRAPHSEARCH過程 將始點S放到OPEN表中。 ① OPEN表為空 ? (Y) 失敗退出 (N) 將OPEN表中的第一個節(jié)點n 取出，放入CLOSED表 n為目標(biāo)點否 ? (Y) 輸出解并成功退出 (N) 擴(kuò)展節(jié)點n，即生成非n之祖先的后繼節(jié)點集合M [注1] 將M中那些既未在OPEN表,也沒在CLOSED表中出現(xiàn)過的節(jié)點加入OPEN表,并逐一設(shè)置指向n的指針 對M中每一個出現(xiàn)于OPEN中的節(jié)點K來說,則要確定一下它們是否應(yīng)該”投奔新父點”n (當(dāng)求最小費用路徑時,必須進(jìn)行這一判斷) [注2] 對M中每一個出現(xiàn)于CLOSED表中的節(jié)點K來說,則要:1．確定一下 K是否應(yīng)該”投奔新父點”n 2．由于K 已擴(kuò)展有子代,此時還需確認(rèn)K 的子孫后代節(jié)點的指針方向是否也要修改 [注3] 按某一方式或按某個試探組，重排OPEN表 ①說明如下: 啟發(fā)式搜索策略在狀態(tài)空間的盲目搜索中搜索到一個解，所需要擴(kuò)展的節(jié)點數(shù)目可能是很大的。因為這些節(jié)點的擴(kuò)展次序完全是隨意的，而且沒有應(yīng)用已解決問題的任何特性。因此，除了那些最簡單的問題之外，一般都要占用很多時間或空間（或者兩者均有）。這種結(jié)果是組合爆炸的一種表現(xiàn)形式。 有關(guān)具體問題領(lǐng)域的信息常常可以用來簡化搜索。我們假設(shè)，初始狀態(tài)、算符和目標(biāo)狀態(tài)的定義都是完全確定的，然后決定一個搜索空間，因此，問題就是如何有效地搜索這個給定空間。進(jìn)行這種搜索的技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息。我們已把此種信息叫做啟發(fā)信息，并把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。啟發(fā)信息: 具有某些有關(guān)具體問題領(lǐng)域的特性的知識 啟發(fā)信息分三種:用于決定下一個要擴(kuò)展的節(jié)點 擴(kuò)展節(jié)點時,用于決定要生成哪些后繼節(jié)點,而非全部 用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點 第七節(jié)中，我們將提出一個只利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪一個是下一步要擴(kuò)展的節(jié)點。一般，這種搜索總是選擇“最有希望”的節(jié)點作為下一個被擴(kuò)展的節(jié)點。執(zhí)行這種思想的搜索，叫做有序搜索或最佳優(yōu)先搜索?！白钣邢Ｍ敝?jié)點:標(biāo)準(zhǔn)1 以此節(jié)點距離目標(biāo)節(jié)點的估計距離進(jìn)行估算,近者為優(yōu) (注重 ”未來”)標(biāo)準(zhǔn)2 估算從起點S到此點,以及從此點到目標(biāo)節(jié)點的”綜合費用”,小者為優(yōu) (注重 ”歷史”+ ”未來”) 第五節(jié) 寬度優(yōu)先搜索 定義在圖搜索過程中，如果在有關(guān)問題的領(lǐng)域內(nèi)沒有任何啟發(fā)信息可以用于排列OPEN表上的節(jié)點，這樣得到的過程，叫做無信息搜索過程，又叫盲目搜索過程。在人工智能中，實際上我們對無信息搜索過程并不感興趣，但是為了便于進(jìn)行比較和加深對其他搜索過程或問題的理解，我們還是需要討論兩種類型的無信息搜索，即寬度優(yōu)先搜索和深度優(yōu)先搜索。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1