【正文】 計(jì)算可能的得分?？尚械霓k法是只生成一定深度的博弈樹，然后進(jìn)行極小極大分析 ,找出當(dāng)前最好的行動方案。 ? (1) 若 P對任何一方來說都不是獲勝的位置，則 e(P)=e(那些仍為 MAX空著的完全的行、列或?qū)蔷€的總數(shù) )e(那些仍為 MIN空著的完全的行、列或?qū)蔷€的總數(shù) ) ? (2) 若 P是 MAX必勝的棋局，則 e(P)＝ +∞。當(dāng)這些估值被倒推回去時，可看到 MAX的最好的也是唯一能使他避免立即失敗的一個走步。 2022/8/21 95 ? 從算法中看到： (1) MAX節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 α值永不減少； (2) MIN節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 β值永不增加。 2022/8/21 98 ? 例： αβ剪枝技術(shù)的例子，圖 。 下面讓我們對 αβ剪枝技術(shù)的搜索效率再作一些分析。 2022/8/21 101 遺傳算法 ? 遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類搜索算法，從某種程度上說遺傳算法是對生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。 2022/8/21 103 遺傳算法的結(jié)構(gòu) ? 霍蘭德 (Holland)的遺傳算法通常被稱為 簡單遺傳算法 (簡稱 SGA)，我們以此作為討論主要對象，加上適應(yīng)的改進(jìn)，分析遺傳算法的結(jié)構(gòu)和機(jī)理。要注意 w1,w2 ,…… ， wn是互不相同的。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。 現(xiàn)在對 TSP的變異操作作簡單介紹，隨機(jī)產(chǎn)生一個 1至 n之間的數(shù) k，決定對回路中的第 k個城市的代碼 wk作變異操作，又產(chǎn)生一個 1至 n之間的數(shù) w，替代 wk，并將 wk加到尾部，得到： w1 w2 …… w k1 w wk+1 …… w n wk ? 這個串有 n+1個數(shù)碼，注意數(shù) w其實(shí)在此串中出現(xiàn)重復(fù)了，必須刪除與數(shù) w相重復(fù)的，得到合法的染色體 2022/8/21 112 ? 并不是所有被選擇了的染色體都要進(jìn)行交叉操作和變異操作，而是以一定的概率進(jìn)行，一般在程序設(shè)計(jì)中交叉發(fā)生的概率要比變異發(fā)生的概率選取得大若干個數(shù)量級， 交叉概率 取 ； 變異概率 取 至 。對這個新種群進(jìn)行下一輪進(jìn)化。 (7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。近似解與問題真正的最優(yōu)解的差是一個統(tǒng)計(jì)意義下的量，也就是說每次程序運(yùn)行得到的解的質(zhì)量可能是有較大的差別的。 對遺傳算法的性能影響最大的也許是交叉和變異操作，有很多文獻(xiàn)對此進(jìn)行了研究的改進(jìn)。對整個種群使用相同的變異概率，并不利于優(yōu)良個體的成長和劣個體的改良。遺傳算法的商業(yè)應(yīng)用五花八門 ,覆蓋面甚廣 ,比如通用電器公司的計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng) Engeneous,這是一個采用了遺傳算法以及其他傳統(tǒng)的優(yōu)化技術(shù)做為尋優(yōu)手段的混合系統(tǒng) (hybrid system)。退火過程由冷卻進(jìn)度表 (Cooling Schedule)控制，包括控制參數(shù)的初值 t及其衰減因子 Δt、每個 t值時的迭代次數(shù) L和停止條件 S。事實(shí)表明，對大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。 2022/8/21 134 ? 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀。 ? 第二步是計(jì)算與新解所對應(yīng)的目標(biāo)函數(shù)差。根據(jù) Metropolis準(zhǔn)則，粒子在溫度 T時趨于平衡的概率為 eΔE/(kT)，其中 E為溫度 T時的內(nèi)能， ΔE為其改變量， k為 Boltzmann常數(shù)。 如果一個應(yīng)用問題不能求得目標(biāo)函數(shù)的全局最優(yōu)值 ,而只能或只希望求一定意義下的“滿意解”，這時 ,可供選擇的方法之一自然是遺傳算法，因?yàn)檫z傳算法比其他算法有更多的優(yōu)勢。 交叉概率和變異概率選取也是遺傳算法的性能影響最大的因素之一，直接影響著收斂速度。如下有一個線性變換： 2022/8/21 120 ? C1和 C2的選取主要依具體問題的情況而定，并應(yīng)滿足一定的約束條件 (例如變換后的適應(yīng)度值不能是負(fù)值等 )。 2022/8/21 117 ? 當(dāng)遺傳算法收斂時，求到的解通常只是所要解決問題的最優(yōu)解的一個近似解，或者叫滿意解。 (5) 按概率 Pc進(jìn)行突變操作 。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進(jìn)行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會。其交換過程如下圖所示： 2022/8/21 110 ? 變異操作的簡單方式是改變數(shù)碼串的某個位置上的數(shù)碼。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。一般情況是從城市 w1開始，依次經(jīng)過城市 w2,…… ， wn，最后回到城市 w1，我們就有如下編碼表示： w1 w2 …… w n 由于是回路，記 wn+1= w1。 2022/8/21 102 ? 遺傳算法自從 1965年提出以來，在國際上已經(jīng)形成了一個比較活躍的研究領(lǐng)域，已召開了多次比較重要的國際會議和創(chuàng)辦了很多相關(guān)的國際刊物。當(dāng)前修剪枝數(shù)最大時，需要生成和估計(jì)的端節(jié)點(diǎn)數(shù)就最少。發(fā)生修剪的那些節(jié)點(diǎn)用“ ”表示。 畫出節(jié)點(diǎn) B及它的第一個兒子節(jié)點(diǎn) C，算出節(jié)點(diǎn) C的靜態(tài)值為 1，于是節(jié)點(diǎn) B的倒推值不會比 1大，又注意到節(jié)點(diǎn) B的最終倒推值不會小于起始節(jié)點(diǎn)的 α值，由此可肯定最終倒推值 β=1。 (2) 對于一個或節(jié)點(diǎn) MAX，若能估計(jì)出其倒推值的下確界 α，并且這個 α值不小于 MAX的父節(jié)點(diǎn) (一定是與節(jié)點(diǎn) )的估計(jì)倒推值的上確界 β，即 α≥β，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對 MAX父節(jié)點(diǎn)的倒推值已無任何影響 了 )。而 MIN為了避免立即敗北被迫走了另一步，從而產(chǎn)生如下棋局： MAX再次搜索，產(chǎn)生如圖 。 2022/8/21 84 ? 為了不致于生成太大的博弈樹，假設(shè)每次僅擴(kuò)展兩層。 2022/8/21 82 ? 在博弈問題中，每一個格局可供選擇的行動方案都有很多，因此會生成十分龐大的博弈樹。其基本思想或算法是： (1) 設(shè)博弈的雙方中一方為 MAX，另一方為 MIN。 (2) 在博弈樹中， 或 節(jié)點(diǎn)和 與 節(jié)點(diǎn)是逐層交替出現(xiàn)的。 (3) 任何一方在采取行動前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對自已為最有利而對對方最為不利的對策，不存在擲骰子之類的“碰運(yùn)氣”因素。修正費(fèi)用 q(n)是從 n到一組終節(jié)點(diǎn)的一個最佳解圖費(fèi)用的一個修正估計(jì)。 2022/8/21 73 ? (12) 如果 m已標(biāo)記為 SOLVED，或者 m的修正費(fèi)用不同于它的前一道費(fèi)用，則把 m的所有那樣的父輩節(jié)點(diǎn)都添加到S中去，這些父輩節(jié)點(diǎn)的通過某個有標(biāo)記連接符的后繼節(jié)點(diǎn)之一就是節(jié)點(diǎn) m。 (5) select G’ 的任意一個非終葉節(jié)點(diǎn) n(將在以后說明如何選擇 )。正如圖搜索一樣 ,如果 h滿足一定的限制，則搜索過程語句是可能得到簡化的。 在一個解圖費(fèi)用的定義中，我們可能要不止 — 次地計(jì)算解圖中某些連接符的值。 2022/8/21 68 ? 象在普通圖中采用的弧線費(fèi)用葉一樣，在與或圖中給連接符指定一定的費(fèi)用往往是很有用的 (這些費(fèi)用模擬規(guī)則應(yīng)用的代價。今后，我們就一直使用這種無環(huán)性假定。在隱含圖中，與滿足產(chǎn)生式系統(tǒng)終止條件的數(shù)據(jù)庫相對應(yīng)的是一個終節(jié)點(diǎn)集合。 ? 在與或樹中，每個節(jié)點(diǎn)最多只有一個父輩節(jié)點(diǎn)。這些超弧線又叫做連接符。一種情況是由總數(shù)據(jù)庫標(biāo)記的一個父輩節(jié)點(diǎn)擁有一組與后繼節(jié)點(diǎn)，每一個后繼節(jié)點(diǎn)都用一個分量數(shù)據(jù)庫來標(biāo)記。 (d) 比較新舊路徑代價。 ? (2) 重復(fù)下列過程，直至找到目標(biāo)節(jié)點(diǎn)止。 2022/8/21 55 ? A算法和 A*算法的定義 定義 1 在 GRAPHSEARCH過程中，如果第 8步的重排OPEN表是依據(jù) f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為 A算法。為此，引進(jìn)一個新函數(shù) g*，這將使我們的記號得到某些簡化。使用不能識別某些節(jié)點(diǎn)真實(shí)希望的估價函數(shù)會形成非最小代價路徑；而使用一個過多地估計(jì)了全部節(jié)點(diǎn)希望的估價函數(shù) (就像寬度優(yōu)先搜索方法得到的估價函數(shù)一樣 )又會擴(kuò)展過多的節(jié)點(diǎn)。 2022/8/21 46 有序搜索例子 ? 下面讓我們再次用八數(shù)碼難題的例子來說明過程GRAPHSEARCH是如何應(yīng)用估價函數(shù)排列節(jié)點(diǎn)的。具有最小估價函數(shù) f（ j）的節(jié)點(diǎn)被選作父輩節(jié)點(diǎn)。對于 i的每一個后繼節(jié)點(diǎn) j： ? (a) 計(jì)算 f(j)。被選為擴(kuò)展的節(jié)點(diǎn)，是估價函數(shù)最小的節(jié)點(diǎn)。根據(jù)習(xí)慣， OPEN表上的節(jié)點(diǎn)按照它們 f函數(shù)值的遞增順序排列。 ? 估價函數(shù)的任務(wù)就是估計(jì) OPEN表中各節(jié)點(diǎn)的重要程度。 把利用啟發(fā)信息的搜索方法叫做 啟發(fā)性搜索方法 。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第 (2)步。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解 。 2022/8/21 30 算法動態(tài)演示圖 2022/8/21 31 ? 例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，我們設(shè)置深度界限為 5。 2022/8/21 29 ? 含有深度界限的深度優(yōu)先搜索算法如下： (1) 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn) OPEN表中。 2022/8/21 27 ? 我們定義節(jié)點(diǎn)的深度如下： (1) 起始節(jié)點(diǎn) (即根節(jié)點(diǎn) )的深度為 0。 2022/8/21 19 2022/8/21 20 ? 寬度優(yōu)先搜索方法分析： ? 寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實(shí)際是將 OPEN表作為“ 先進(jìn)先出 ”的隊(duì)列進(jìn)行操作。 2022/8/21 16 ? 從圖可見，這種搜索是逐層進(jìn)行的；在對下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。這種排序可以是任意的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù) (屬于啟發(fā)式搜索 )。對已經(jīng)在 OPEN或 CLOSED表上的每一個 M成員，確定是否需要更改通到 n的指針方向。 ? (3) LOOP：若 OPEN表是空表，則失敗退出。 2022/8/21 7 ? 在介紹圖搜索策略之前，讓我們來看一個例子。 2022/8/21 3 ? 從問題表示到問題的解決，有一個求解的過程。本章先介紹搜索技術(shù)，將要討論問題求解的搜索原理，包括一些早期的搜索技術(shù)或用于解決比較簡單問題的搜索原理和一些比較新的能夠求解比較復(fù)雜問題的搜索原理，包括算法、遺傳算法和模擬退火算法等。 ? 圖中的節(jié)點(diǎn)對應(yīng)于狀態(tài)，而連線對應(yīng)于操作符。 ? (2) 建立一個叫做 CLOSED的已擴(kuò)展節(jié)點(diǎn)表（簡稱 CLOSED表），其初始為空表。把 M的這些成員加進(jìn) OPEN表。 2022/8/21 13 2022/8/21 14 ? 圖搜索方法的幾點(diǎn)分析： ? 圖搜索過程的第 8步對 OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個“最好”的節(jié)點(diǎn)作為第 4步擴(kuò)展用。 寬度優(yōu)先搜索 (breadthfirst search)的定義：如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索 (breadthfirst search)，如圖 。 (6) 如果 n的任一個后繼節(jié)點(diǎn)是個目標(biāo)節(jié)點(diǎn)，則找到一個解答，成功退出；否則轉(zhuǎn)向第 (2)步。深度相等的節(jié)點(diǎn)可以任意排列。值得說明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。 (6) 如果后繼節(jié)點(diǎn)中有任一個為目標(biāo)節(jié)點(diǎn)，則求得一個解，成功退出；否則，轉(zhuǎn)向 (2)。在搜索樹上，我們假設(shè) g(i)也是從起始節(jié)點(diǎn) S到節(jié)點(diǎn) i的最少代價路徑上的代價，因?yàn)樗俏ㄒ坏穆窂剑? 2022/8/21 35 等代價搜索算法 ? 等代價搜索方法以 g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)，其算法如下： (1) 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中。 (5) 擴(kuò)展節(jié)點(diǎn) i。 啟發(fā)信息 ：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的，與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息，把此種信息叫做 啟發(fā)信息 。 2022/8/21 39 估價函數(shù) ? 用來估算節(jié)點(diǎn)希望程度的量度，叫做 估價函數(shù) (evaluation function)。 2022/8/21 40 有序搜索 ? 我們用估價函數(shù) f來排列 GRAPHSEARCH第 8步中 OPEN表上的節(jié)點(diǎn)。估價函數(shù) f是這樣確定的：一個節(jié)點(diǎn)希望程度越大，其 f值就越小。 2022/8/21 42 ? (6) 擴(kuò)展節(jié)點(diǎn) i，生成其全部后繼節(jié)點(diǎn)。 2022/8/21 43 ? 注： ?步驟（ ）是一般搜索圖所需要的，該圖中可能有一個以上的父輩節(jié)點(diǎn)。如果沒有適用的準(zhǔn)確的希望量度，那么 f的選擇將涉及兩個方面的內(nèi)容：一方面是一個時間和空間之間的折衷方案