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