【正文】 優(yōu)先法 (breadthfirst)，深度優(yōu)先法 (depthfirst)，有界深度優(yōu)先法，啟發(fā)式最優(yōu)圖搜索法 (A*，AO*)…….. ? 博弈搜索方法 極小極大法 (MiniMax)， AlphaBeta剪枝法 (pruning)……… ? 現(xiàn)代優(yōu)化搜索方法 爬山法 (hill climbing)，模擬退火法 (simulated annealing)，遺傳算法 (geic algorithms)……. 搜索策略的評價 ? 完備性 如果問題有解，能否保證找到？ ? 最優(yōu)性 (optimization) 如果問題存在不同的解，能否找到最優(yōu)解？ ? 時間復雜性 找到一個解需要花費多少時間 ? 空間復雜性 在搜索過程中需要占用多少內(nèi)存 時空復雜性的量度 ?狀態(tài)空間圖的大小 ?分支因子 b ?目標節(jié)點的深度 d ?路徑的最大長度 m ?搜索深度限制 l 問題及其搜索過程的表示 ? 狀態(tài)空間 表示法 通過“ 狀態(tài) ”表示問題，通過“ 操作符 ”求解問題 狀態(tài)的改變 表示了問題求解過程 狀態(tài)空間 ? 以“狀態(tài)”和“操作符”為基礎(chǔ) 狀態(tài) ： 問題求解過程中任意時刻的狀況 操作符 ： 使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作 ? 問題的全部狀態(tài) (包含初始狀態(tài)和目標狀態(tài) )及一切可用操作符所構(gòu)成的集合稱為問題的狀態(tài)空間。 ? 用 Sk=｛ Sk0， Sk1｝表示問題的 狀態(tài) ，其中，Sk0表示金片 A所在的鋼針號， Sk1表示金片 B所在的鋼針號。這種游戲求解的問題是：給定一種初始的將牌布局或結(jié)構(gòu)（稱初始狀態(tài)）和一個目標的布局（稱目標狀態(tài)），問如何移動將牌，實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)變?？梢允褂玫牟僮饔校? 空格左移，空格上移，空格右移，空格下移 尋找從初始狀態(tài)到目標狀態(tài)的解路徑。否則轉(zhuǎn) (2)繼續(xù)。其搜索過程是：從初始結(jié)點 S0開始，在其子結(jié)點中選擇一個最新生成的結(jié)點進行考察，如果該子結(jié)點不是目標結(jié)點且可以擴展，則擴展該子結(jié)點，依此向下搜索，直到某個子結(jié)點既不是目標結(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟結(jié)點進行考察。因此，深度優(yōu)先搜索是一種不完備策略，即使問題有解，它也不一定能夠找到解。 ?啟發(fā)式搜索方法所依據(jù)的是問題自身的 啟發(fā)性信息 ，而啟發(fā)性信息又是通過 估價函數(shù) 而作用于搜索過程的 。 一般形式 為 f(n)=g(n)＋ h(n) g(n)是從初始節(jié)點 S0到節(jié)點 n的實際代價。 估價函數(shù)例： f(n) = d(n) + W(n) 2 8 3 1 4 7 6 5 S0 節(jié)點 n在搜索樹中的深度 n中“不在位”的數(shù)碼個數(shù) f(S0) = ? = 0 + 3 = 3 1 2 3 8 4 7 6 5 Sg ? 根據(jù)搜索過程中選擇擴展節(jié)點的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)搜索。 開始 把 S放入 OPEN表，計算估價函數(shù) f (s) OPEN表為空表？ 把 OPEN表中的第一個節(jié)點 n放入 CLOSED表 n為目標節(jié)點嗎？ 擴展 n，計算所有子節(jié)點的估價函數(shù)值，并提供它們返回節(jié)點 n的指針。 1 2 3 8 4 5 6 7 ? 第 ② 步有三種情況 ,我們選擇其中f(n)最小的 : ? 其它依次類推 .最后用了 7步得出了結(jié)果 . 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (5) (5) ? ?最佳優(yōu)先算法有時無法得到最優(yōu)解，因為它的估價函數(shù) f的選取時，忽略了從初始節(jié)點到目前節(jié)點的代價值。 解 2： h(n) = P(n)， P(n)定義為每一個數(shù)碼與其目標位置之間距離（不考慮夾在其間的數(shù)碼）的總和，同樣可以斷定至少要移動 P(n)步才能到達目標，因此有 P(n)≤h*(n)，即滿足 A*算法的限制條件。 解 ：確定估價函數(shù)。 ? A*算法結(jié)合了啟發(fā)式方法（這種方法通過充分利用圖給出的信息來動態(tài)地作出決定而使搜索次數(shù)大大降低）和形式化方法（這種方法不利用圖給出的信息，而僅通過數(shù)學的形式分析，如 Dijkstra算法）。 ? 為了提高解答的正確性，我們可以適當?shù)亟档凸纼r函數(shù)的值，從而使之進行更多的搜索，但這是以降低它的速度為代價的，因而我們可以根據(jù)實際對解答的速度和正確性的要求而設計出不同的方案，使之更具彈性。需要指出的是，當結(jié)點數(shù) n大于 10， 000時，堆棧不再是正確的選擇，但這足已滿足我們一般的要求。從而如下代碼可實現(xiàn)之： ? double dx1 = currentX goalX。 ? cross = dx1*dy2 dx2*dy1。 在 A*算法中需要保留所有的結(jié)點，這將使得時間和空間的消耗都很大，而 Beam Search方法對結(jié)點數(shù)作出限期，當結(jié)點數(shù)過多時，它會將一些不 (大 )可能為最優(yōu)的點排除，從而降低時間和空間的要求，但需要說明的是，由于在排除結(jié)點后需對結(jié)點排序，當排序的工作量大于排除點后所節(jié)省的工作量，則該方法無意義。 ? c. Dynamic weighting。其缺點在于復雜度太大，一般僅用于復雜的圖形。 ? f. Dynamic A*(D*)。 靜夜四無鄰，荒居舊業(yè)貧。 00:48:4800:48:4800:48Wednesday, March 15, 2023 1乍見翻疑夢，相悲各問年。 2023年 3月 15日星期三 12時 48分 48秒 00:48:4815 March 2023 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。 :48:4800:48Mar2315Mar23 1世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 2023年 3月 上午 12時 48分 :48March 15, 2023 1少年十五二十時，步行奪得胡馬騎。 00:48:4800:48:4800:483/15/2023 12:48:48 AM 1越是沒有本領(lǐng)的就越加自命不凡。 :48:4800:48:48March 15, 2023 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 上午 12時 48分 48秒 上午 12時 48分 00:48: MOMODA POWERPOINT Lorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感謝您的下載觀看 專家告訴