【文章內(nèi)容簡介】 S0 3 3 1 S8 1 3 1 S16 3 3 0 S24 1 3 0 S1 3 2 1 S9 1 2 1 S17 3 2 0 S25 1 2 0 S2 3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0 S3 3 0 1 S11 1 0 1 S19 3 0 0 S27 1 0 0 S4 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0 S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0 S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0 S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0 S0： (3， 3， 1)為初始狀態(tài) ， Sn： (0， 0， 0)為目標狀態(tài) 。 按照題目規(guī)定的條件，應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。例如，左岸邊野人數(shù)目超過修道士的情況， S S S S S2 S25， 6種； 右岸邊野人數(shù)目超過修道土的情況， S S S1 S2 S2 S27； S15和 S16不可能出現(xiàn)，因為船不可能?？吭跓o人的岸邊； S9不可能出現(xiàn)，因為修道士不可在數(shù)量優(yōu)勢的野人底下把船安全地劃回來； S28因為修道士也不可能在數(shù)量占優(yōu)勢的野人底下把船安全地劃向?qū)Π丁? 符合題目只有 16個合理狀態(tài)。 修道士和野人問題 4 21 (5) 當狀態(tài)數(shù)量不是很大時，按問題的有序元組畫出狀態(tài)空間圖 ； 依照狀態(tài)空間圖搜索求解；根據(jù)上述分析，共有 16個合法狀態(tài)和允許的操作， 可以劃出修道士帶野人問題的狀態(tài)空間圖，如圖所示。 331 310 220 320 321 300 311 110 221 020 031 010 021 111 011 000 S0 S18 S17 S21 S1 S19 S2 S26 S5 S29 S12 S30 S10 S13 S31 S14 02 01 01 11 10 02 01 20 11 20 01 02 01 10 11 01 02 P → Q→ P → Q→ 問題的狀態(tài)空間十分龐大而不能全部以顯式圖的方式表達時？？ 梵塔問題的狀態(tài)空間分析 2 22 直接求解的困難在于狀態(tài)太大，解 64階，要把全部的狀態(tài)空間圖都顯示出來不可能最優(yōu)解長度 264－ 1=18446744073709511615 每秒 2次 2900億年 (1) 此問題是否有解 ? (2)若問題有解，則解的形式如何 ?能否找到解的規(guī)律 ? 先從 n=2開始討論。設(shè)其中的小金片稱為 A，大金片叫 B，則問題的狀態(tài)可以用金片穿在寶石針的編號排列情況來表示， 例如用數(shù)組 (Pa， Pb)表示，這里 Pa， Pb∈ {1， 2， 3}，其中 Pa代表 A片處在 Pa號寶石針上， Pb代表 B片處在 Pb號寶石針上根據(jù) 9種可能狀態(tài)，可以構(gòu)成二階梵塔問題的狀態(tài)空間 11 21 31 23 33 13 32 12 22 12 21 (Pa， Pb) （小大 ) A B 高階梵塔隱式 23 代價樹的推進搜索（ CTSP問題） 24 城市數(shù) 路徑數(shù) 7 103 15 1011 20 1018 50 1064 100 5 10157 31 1032 (31－ 1)!/2 18902 17102 15404 KM 5個城市交通問題代價樹（ 廣度優(yōu)先） 例子 例 城市交通問題。設(shè)有 5個城市，它們之間的交通線路如圖所示，圖中的數(shù)字表示 兩個城市之間的交通費用（代價）。用代價樹的廣度優(yōu)先搜索，求從 A市出發(fā)到 E市 費用最小的交通路線。 解： A B E D C 3 4 5 3 2 4 C1 A D1 D2 E1 E2 B2 C2 E3 E4 B1 3 4 2 4 5 3 4 2 3 5 A→ C1→ D1→ E2 代價 =8 下標 l， 2， ． ．標出多次出現(xiàn) 啟發(fā)式搜索 26 問題求解信息環(huán)境 (1) 全信息環(huán)境 Ee 運用知識和經(jīng)驗，設(shè)法采用最優(yōu)算法，找到最佳路徑，以便取得理想效果。 象棋博弈。 (2) 部分已知信息環(huán)境 Ep 充分利用已知的部分信息環(huán)境， 制定策略，設(shè)法按照最佳搜索路徑取得最優(yōu)解?；蛘咴O(shè)法把部分已知信息環(huán)境變?yōu)? 清晰明了的全信息環(huán)境的智能搜索問題來求解。 軍棋 (3) 未知信息環(huán)境 En 首先要設(shè)法變環(huán)境。為部分已知信息環(huán)境來解決 。 偵察衛(wèi)星、實地探險 啟發(fā)式搜索原理 27 .1 啟發(fā)式策略 .2 基本搜索特點及其局限性 (稱為 弱方法 ) ① 是 依據(jù)某種固定規(guī)則運行的搜索 ， 屬于非啟發(fā)的強力搜索 , 沒有表現(xiàn)出智能搜索的活躍性與靈活性 。 ② 基本搜索策略普遍適用于樹狀問題求解 ， 控制性知識簡單 ， 編程容易在計算機上實現(xiàn) 。 ③ 實際搜索效率很低 ， 故又被稱為盲目搜索 。 一般必須知道問題的全部 狀態(tài)空間 ， 搜索效果差 ， 求解能力弱 . 啟發(fā)性信息 。 啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的 ， 并可指導(dǎo)搜索過程朝著最有希望方向前進的控制信息 。 啟發(fā)性信息一般有以下三種： ① 有效地幫助確定擴展節(jié)點的信息； ② 有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息： ③ 能決定在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息 。 啟發(fā)信息及其作用 28 (1) 兩種極端效率的搜索 ① 當 P=L／ T≈0， 沒有任何控制性知識作依據(jù) ， 搜索中的每一步都是 完全隨意而進行的 ， 稱為隨機搜索； ② P=L／ T＝ 1， 搜索以充分的控制性知識為依據(jù) ， 每一步搜索都十分嚴 密而正確 ， 即在其搜索路徑上 ， 所擴展的每一個節(jié)點都落在最佳路 徑上 ， 稱為最佳搜索 。 (2) 啟發(fā)信息 要求解的問題所聚集的有關(guān)資料 、 分析結(jié)果及與閑題求解相關(guān)等特性 信息 ， 啟發(fā)信息是控制性知識中活躍的 、 有利于提高求效率的特異性內(nèi)容； 啟發(fā)信息的作用在于綜合了人的經(jīng)驗及推理性常識等智能 ， 得出了有利 于找到問題解的較為完善的控制性信息與知識 。 把搜索中出現(xiàn)的諸如問 題的狀態(tài)條件 、 性質(zhì) 、 發(fā)展動態(tài) 、 解的過程特性 、 結(jié)構(gòu)特性等規(guī)律 ， 問 題求解的技巧性規(guī)則等 ， 統(tǒng)稱為搜索的啟發(fā)信息 。 盲人爬山法（局部擇優(yōu)搜索） 29 搜索每到達一個節(jié)點后 ， 其后繼節(jié)點不是預(yù)定的或盲目的 ， 而是在它的所有節(jié)點中 ， 按估計函數(shù) f(x)選擇最優(yōu)者 。 （ 目標函數(shù) ， 適合函數(shù) ， 梯度 ） 優(yōu)點是方法簡單 ， 要處理的資料量減少了 ， 所以占用內(nèi)存空間少 、 速度快 。 主要只在單因素 、 單極值的情況下使用 . 而在多極值情況下會遇到許多因難 ， 導(dǎo)致找不到最佳解 。 例如在二維或三維的情況下 ， 就會遇到 “ 多峰 ” 問題 、 “ 盆地 ” 或