【文章內(nèi)容簡介】 N可擴(kuò)展？ 失敗 是 否 成功 是 擴(kuò)展 N并用 f(x)估計(jì)每個(gè)子結(jié)點(diǎn) Ni 及配上指向 N的返回指針，將 {Ni} 并入 OPEN表，利用 f(x)對(duì) OPEN表 重新排序（小的在前） 是 否 否 啟發(fā)式函數(shù)的實(shí)現(xiàn) ? 前面我們介紹過啟發(fā)式優(yōu)先搜索的關(guān)鍵是啟發(fā)式函數(shù)的制定上，不同的問題有不同的啟發(fā)式函數(shù)。下面介紹的是處理重排九宮問題時(shí)制定啟發(fā)式函數(shù)的原則。 ? 2 8 3 ? 1 6 4 5 6 0 ? 7 5 ? 2 8 3 1 2 3 ? 1 4 3 4 0 8 4 ? 7 6 5 7 6 5 ? 2 8 3 ? 1 6 4 5 6 0 ? 7 5 2 位置不符將牌 距離總和 二倍將牌逆轉(zhuǎn)數(shù) 目標(biāo) 啟發(fā)式函數(shù)的實(shí)現(xiàn) ? 2 1 3 1 2 3 ? 8 4 8 4 ? 7 5 6 7 6 5 目標(biāo) 九宮問題的目標(biāo)狀態(tài)及有兩個(gè)逆轉(zhuǎn)位置的狀態(tài) 1和 2， 5和 6 下面給出重排九宮問題的兩個(gè)啟發(fā)式函數(shù)： f1(x)= p(x)+w(x) 其中 p(x)是 x結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)相比將牌不相符的數(shù)目， w(x)是結(jié)點(diǎn) x和目標(biāo)結(jié)點(diǎn)相比每個(gè)將牌的距離之和。 啟發(fā)式函數(shù)的實(shí)現(xiàn) f2(x)= p(x)+3s(x) 其中 p(x)是 x結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)相比每個(gè)將牌“離家”的最短距離之和； s(x)是這樣計(jì)算的：每個(gè)將牌和目標(biāo)相比，若該將牌的后繼和目標(biāo)中該將牌的后繼不同，則該將牌得 2分，相同則該將牌得 0分，中間位置有將牌得 1分，沒將牌得 0分。顯然 f2(x)的啟發(fā)強(qiáng)度要比 f1(x)大。對(duì)于給定的格局和目標(biāo)請(qǐng)大家按兩種啟發(fā)式函數(shù)給出搜索的狀態(tài)空間圖。 2 8 3 1 2 3 ? 1 6 4 8 4 ? 7 5 7 6 5 初始狀態(tài) 目標(biāo)狀態(tài) 博弈樹的啟發(fā)式搜索策略 ? 下棋、打牌、戰(zhàn)爭等競爭性智能活動(dòng)稱為博弈。其中最簡單的一種稱為二人零和非偶然性全信息博弈。 ? 所謂二人零和、全信息非偶然性搏弈是指： ? （ 1）對(duì)壘的雙方 A、 B輪流采取行動(dòng)，博弈的結(jié)果只有三種情況： A勝， B??； B勝 A敗；和局。 ? （ 2）對(duì)壘的雙方都了解當(dāng)前的格局和過去的歷史。 ? （ 3）任何一方在采取行動(dòng)之前，都要根據(jù)當(dāng)前的實(shí)際情況進(jìn)行得失分析，選取對(duì)自己最為有利而對(duì)對(duì)方最不利的對(duì)策，不存在碰運(yùn)氣的偶然因素。 博弈樹的啟發(fā)式搜索策略 ? 在博弈過程中，任何一方都希望自己獲得勝利。因此，在 A方有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是選對(duì)自己有利而對(duì) B方不利的方案，站在 A方的立場看問題，供A方選擇的方案之間是一種或的關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在 A方的手里，他或者選擇這個(gè)方案或這者選擇另一個(gè)方案。 ? 但是，若 B方也有可供選擇的若干方案，則對(duì) A方來說這些方案之間是與的關(guān)系，因?yàn)檫@時(shí)主動(dòng)權(quán)操在 B手里，這些可供選擇的方案中任何一個(gè)都可能被 B選中，A方必須考慮到對(duì)自己最不利的情況發(fā)生。站在任何一方的立場上畫出來的博弈樹都是一棵與或結(jié)點(diǎn)交替產(chǎn)生的與 /或樹 —稱為博弈樹。 博弈樹的啟發(fā)式搜索策略 ? 博弈樹的特點(diǎn)如下： ? （ 1）博弈的初始格局是初始結(jié)點(diǎn)。 ? （ 2）在博弈樹中 “ 或 ” 結(jié)點(diǎn)和 “ 與 ” 結(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的結(jié)點(diǎn)之間是或關(guān)系，對(duì)方擴(kuò)展結(jié)點(diǎn)之間是與關(guān)系。雙方輪流擴(kuò)展結(jié)點(diǎn)。 ? （ 3）所有使自己獲勝的終局都是本原問題，相應(yīng)的結(jié)點(diǎn)是可解結(jié)點(diǎn)；所有使對(duì)方獲勝的終局都是不可解結(jié)點(diǎn)。 博弈樹的啟發(fā)式搜索策略 ? 極大極小分析法： ? 在二人博弈問題中，為了從眾多可供選擇的方案中選出一個(gè)對(duì)自己有利的行動(dòng)方案就需要對(duì)當(dāng)前情況及將要發(fā)生的情況進(jìn)行分析，從中選出最優(yōu)者。最常用的方法是極大極小分析法。其基本思想是： ? （ 1）設(shè)博弈的一方是 A， 另一方是 B。 極大極小分析就是為其中的一方（例如 A方）尋找最優(yōu)行動(dòng)方案的方法。 ? （ 2）為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行比較。具體地說就是，就是要考慮每一方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并計(jì)算可能的得分。 博弈樹的啟發(fā)式搜索策略 ? （ 3）計(jì)算得分，需要根據(jù)問題的特性信息定義一個(gè)估計(jì)函數(shù)，用來估算當(dāng)前博弈樹端結(jié)點(diǎn)的得分。此時(shí)估算出來的得分稱為靜態(tài)估值。 ? （ 4）當(dāng)端結(jié)點(diǎn)的估值計(jì)算出來后，再推算父結(jié)點(diǎn)的得分。推算的方法是對(duì)“或”結(jié)點(diǎn)，選其子結(jié)點(diǎn)中最大的得分作為父結(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個(gè)對(duì)自己最有利的方案；對(duì)“與”結(jié)點(diǎn)，選其子結(jié)點(diǎn)中一個(gè)最小的得分作為父結(jié)點(diǎn)的得分，這是立足于最壞的情況。這樣計(jì)算出來的父結(jié)點(diǎn)的得分稱為倒退估值。 ? （ 5）如果一個(gè)行動(dòng)方案能獲得較大的倒退估值，則它是當(dāng)前最好的方案。 博弈樹的啟發(fā)式搜索策略 ? 在博弈問題中，每一個(gè)格局可供選擇的行動(dòng)方案都有很多，因此會(huì)產(chǎn)生十分龐大的博弈樹，例如，西洋跳棋完整的博弈樹約有 1040 個(gè)結(jié)點(diǎn)。試圖用完整的博弈樹來進(jìn)行極大極小分析是很困難的?？尚械霓k法是生成一定深度的博弈樹，然后進(jìn)行極大極小化分析找出當(dāng)前最好的行動(dòng)方案。如此進(jìn)行下去，直到找到勝敗的結(jié)果為止。每次生成博弈樹的深度，根據(jù)實(shí)際情況而定。 ? 下面是一個(gè)比較簡單的二人零和全信息非偶然性博弈的例子。 ? 博弈樹的啟發(fā)式搜索策略 ? 例：一字棋游戲，在一個(gè) 3*3的方格棋盤中，由 A、 B兩人對(duì)弈，輪到誰走棋誰就往空格上放上自己的一只棋子，誰先使自己的棋子構(gòu)成三子一線，誰就取得了勝利。設(shè)A的棋子用 a表示， B的棋子用 b表示，假設(shè)每次僅擴(kuò)展兩層。估計(jì)函數(shù)定義如下： ? 設(shè)棋局為 P， 估計(jì)函數(shù)為 e(P) ? (1)若 P是 A必勝的棋局，則 e(P)=+? ? （ 2） 若 P是 B必勝的棋局，則 e(P)= ? ? （ 3） 若 P是勝負(fù)未定的棋局， ? 則 e(P)=e(+P) e(P) ? 其中， e(+P)表示棋局 P上有可能使 a成為三子一線的數(shù)目。 e(P)表示棋局 P上有可能使 b成為三子一線的數(shù)目。 ? 博弈樹的啟發(fā)式搜索策略 ? 例如對(duì)于右面的棋局 ： b ? e(P) = 64 =2 a ? 假定具有對(duì)稱性的兩個(gè)棋局 ? 算作一個(gè)棋局，還假定 A先走棋 ? 我們站在 A的立場上。下圖給出了 A的第一招走棋生成的博弈樹。圖中結(jié)點(diǎn)旁的數(shù)字分別表示相應(yīng)結(jié)點(diǎn)的靜態(tài)估值或倒推值。從圖中可以看出對(duì)于 A來說最好的一著棋是 S3， 因?yàn)?S3比 S2和 S1有較大的倒推值。 ? 在 A走 S3這一著棋后， B的最優(yōu)選擇是 S4， 因?yàn)檫@一著棋的靜態(tài)估值較小，對(duì) A不利。不管 B選擇 S4或 S5， A都要運(yùn)用極大極小化分析法產(chǎn)生深度為 2的博弈樹，以決定下一步應(yīng)該如何走棋，其過程與上面類似。 一字棋 博弈樹的啟發(fā)式搜索 a S0 S1 S2 S3 a a a b a b a b a b a b 1 0 1 0 1 1 2 1 b a 1 b a 0 a b a b 1 0 a b 2 b a 1 S4 b a 2 S5 最佳走步 一字棋的極大極小搜索 博弈樹的啟發(fā)式搜索 ? 從上面的討論當(dāng)中可以看出上面例子中定義的啟發(fā)式函數(shù)考慮的因素太少了，實(shí)際上只給出了路的概念（即整行、整列、整對(duì)角線），并且沒有對(duì)一條路上已有幾個(gè)棋子站位的情況加以區(qū)分，僅僅考慮自己站位的情況。下面定義的一個(gè)啟發(fā)式函數(shù)就比較精確。為此，引入以下概念： ? 0階路：一條路上沒有任何棋子站位。 0階路即可屬于 A方也可屬于 B方，對(duì)得分沒有影響，在估值時(shí)不予考慮。 ? 1階路：如果一條路上僅有 A方（或 B方）的一個(gè)棋子站位，則稱是留給 A方（或 B方）的一階路。 ? 2階路：如果一條路上僅有 A方（或 B方）的兩個(gè)棋子站位，則稱是留給 A方（或 B方）的二階路。 博弈樹的啟發(fā)式搜索 ? 一個(gè)比較好的啟發(fā)函數(shù) h2(n)定義如下： ? 如果 n是非終局結(jié)點(diǎn)，則 A方的靜態(tài)估值函數(shù)是： ? h2(n) = (A方的一階路數(shù) B方的一階路數(shù)） +4（ A方的二階路數(shù) – B方的二階路數(shù)） + a ? 其中 ? +2 若Ａ方出子占了Ｂ方的２階路 ? a = 2 若Ｂ方出子占了Ａ方的２階路 ? 0 其它 ? 博弈樹的啟發(fā)式搜索 ? 例如對(duì)下面的格局按 h2(n)計(jì)算靜態(tài)估值函數(shù)： ? h2(A) = 2 – 1 +4(10)+0 =5 ? h2(B) = 2 – 2 +4(00)+(2) = 2 ? ? b a a A格局 b a a b B格局 ? 博弈樹的啟發(fā)式搜索 ? 請(qǐng)按 A方的觀點(diǎn)用 h2(n)為靜態(tài)估值函數(shù)，給出深度為 4的極大極小分析過程。 b a a b 專家系統(tǒng) ? 專家系統(tǒng)是人工智能應(yīng)用領(lǐng)域中最活躍的一個(gè)分支 ,自 1968年費(fèi)根鮑姆等人研制成功第一個(gè)專家系統(tǒng) DENDRAL以來 ,應(yīng)用于醫(yī)療診斷 、 圖象處理 、石油化工 、 地質(zhì)勘探 、 金融決策 、 實(shí)時(shí)監(jiān)控 、 分子遺傳工程 、 教學(xué) 、 軍事等不同領(lǐng)域中的專家系統(tǒng)就象雨后春筍般涌現(xiàn)出來 。 成功的專家系統(tǒng)不僅取得了極大的社會(huì)效益和經(jīng)濟(jì)效益 ， 同時(shí)也促進(jìn)了人工智能基本理論和基本技術(shù)的研究和發(fā)展 。 專家系統(tǒng) ? 本章將對(duì)專家系統(tǒng)的有關(guān)概念及建造技術(shù)進(jìn)行討論 ， 并給出相應(yīng)的實(shí)例 。 專家系統(tǒng) （ 續(xù) ） ? 什麼是專家系統(tǒng) ？ ? 關(guān)于專家系統(tǒng)到現(xiàn)在尚沒有一個(gè)嚴(yán)格的定義 ， 但專家們共識(shí)： ? 一個(gè)專家系統(tǒng)是一個(gè)智能程序系統(tǒng) ， 它里面應(yīng)具有大量相關(guān)領(lǐng)域?qū)＜业闹R(shí) ， 它能應(yīng)用人工智能技術(shù)模擬領(lǐng)域?qū)＜仪蠼鈫栴}的思維過程進(jìn)行推理 ，解決相關(guān)領(lǐng)域內(nèi)的困難問題 ， 并且達(dá)到甚至超過領(lǐng)域?qū)＜业乃?。 專家系統(tǒng) （ 續(xù) ） ? 專家系統(tǒng)的分類： ? 按照專家系統(tǒng)求解問題的性質(zhì) ， 可以把它分為下列幾種類型 。 ? 1. 解釋專家系統(tǒng) （ expert system for interpretation） ? 解釋專家系統(tǒng)的任務(wù)是通過對(duì)已知信息和數(shù)據(jù)的分析與解釋 ， 確定它們的涵義 。 解釋專家系統(tǒng)具有下列的特點(diǎn)： ? （ 1） 系統(tǒng)處理的數(shù)據(jù)量很大 ， 而且往往是不準(zhǔn)確的 、 有錯(cuò)誤的 、 或不完全的 。 專家系統(tǒng) （ 續(xù) ） ? （ 2） 系統(tǒng)能夠從不完全的信息中得出解釋 ， 并能對(duì)數(shù)據(jù)作出某些假設(shè) 。 ?