人工智能a算法(推薦文檔)

1、1啟發(fā)式搜索算法A啟發(fā)式搜索算法A,般簡稱為A算法，是一種典型的啟發(fā)式搜索算法。其基本思想是：定義一個評價函數(shù)f,對當(dāng)前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。評價函數(shù)的形式如下：f(n)=g(n)+h(n)其中n是被評價的節(jié)點。f(n)、g(n)和h(n)各自表述什么含義呢？我們先來定義下面幾個函數(shù)的含義，它們與f(n)、g(n)和h(n)的差別是都帶有一個*號。g*(n):表示從初始節(jié)點s到節(jié)點n的最短路徑的耗散值；h*(n)：表示從節(jié)點n到目標(biāo)節(jié)點g的最短路徑的耗散值；f*(n)=g*(n)+h*(n)：表示從初始節(jié)點s經(jīng)過節(jié)點n到目標(biāo)節(jié)點g的最短路徑的耗散值。而f(n)、g(

2、n)和h(n)則分別表示是對f*(n)、g*(n)和h*(n)三個函數(shù)值的的估計值。是一種預(yù)測。A算法就是利用這種預(yù)測，來達到有效搜索的目的的。它每次按照f(n)值的大小對OPEN表中的元素進行排序，f值小的節(jié)點放在前面，而f值大的節(jié)點則被放在OPEN表的后面，這樣每次擴展節(jié)點時，都是選擇當(dāng)前f值最小的節(jié)點來優(yōu)先擴展。利用評價函數(shù)f(n)=g(n)+h(n)來排列OPEN表節(jié)點順序的圖搜索算法稱為算法A。過程AOPEN:=(s),f(s):=g(s)+h(s);LOOP：IFOPEN=()THENEXIT(FAIL)；n:=FIRST(OPEN)；IFGOAL(n)THENEXIT(SUCCE

3、SS)；REMOVE(n,OPEN),ADD(n,CLOSED)；EXPAND(n)fmi,計算f(n,mi)=g(n,mi)+h(mi)；g(n,mi)是從s通過n到mi的耗散值，f(n,mi)是從s通過n、mi到目標(biāo)節(jié)點耗散值的估計。ADD(mj,OPEN)，標(biāo)記mi到n的指針。IFf(n,mk)f(mk)THENf(mk):=f(n,mk)，標(biāo)記mk至Un的指針；比較f(n,mk)和f(mk),f(mk)是擴展n之前計算的耗散值。IFf(n,ml)f(ml)THENf(ml):=f(n,ml)，標(biāo)記ml到n的指針，ADD(ml,OPEN)；當(dāng)f(n,ml)g*(n)oh(n)則依賴于啟發(fā)

4、信息，通常稱為啟發(fā)函數(shù)，是要對未來擴展的方向作出估計。算法A是按f(n)遞增的順序來排列OPEN表的節(jié)點，因而優(yōu)先擴展f(n)值小的節(jié)點,體現(xiàn)了好的優(yōu)先搜索思想，所以算法A是一個好的優(yōu)先的搜索策略。圖2.6表示出當(dāng)前要擴展節(jié)點n之前的搜索圖，擴展n后新生成的子節(jié)點ml(Wmj)、m2(Wmk)、m3(Wml)要分別計算其評價函數(shù)值：圖2.6搜索示意圖f(m1)=g(m1)+h(m1)f(n，m2)=g(n，m2)+h(m2)f(n，m3)=g(n，m3)+h(m3)然后按第6步條件進行指針設(shè)置和第7步重排OPEN表節(jié)點順序，以便確定下一次要擴展的節(jié)點。用A算法來求解一個問題，最主要的就是要定義

5、啟發(fā)函數(shù)h(n)。對于8數(shù)碼問題，一種簡單的啟發(fā)函數(shù)的定義是：h(n)=不在位的將牌數(shù)什么是不在位的將牌數(shù)呢？我們來看下面的兩個圖。其中左邊的圖是8數(shù)碼問題的一個初始狀態(tài)，右邊的圖是8數(shù)碼問題的目標(biāo)狀態(tài)。我們拿初始狀態(tài)和目標(biāo)狀態(tài)相比較，看初始狀態(tài)的哪些將牌不在目標(biāo)狀態(tài)的位置上，這些將牌的數(shù)目之和，就是不在位的將牌數(shù)。比較上面兩個圖，發(fā)現(xiàn)1、2、6和8四個將牌不在目標(biāo)狀態(tài)的位置上，所以初始狀態(tài)的不在位的將牌數(shù)就是4,也就是初始狀態(tài)的h值。其他狀態(tài)的h值，也按照此方法計算。下面再以八數(shù)碼問題為例說明好的優(yōu)先搜索策略的應(yīng)用過程。設(shè)評價函數(shù)f(n)形式如下：f(n)=d(n)+W(n)其中d(n)代表

6、節(jié)點的深度，取g(n)=d(n)表示討論單位耗散的情況；取h(n)=W(n)表示不在位的將牌個數(shù)作為啟發(fā)函數(shù)的度量,這時f(n)可估計出通向目標(biāo)節(jié)點的希望程度。圖2.7表示使用這種評價函數(shù)時的搜索樹,圖中括弧中的數(shù)字表示該節(jié)點的評價函數(shù)值f。算法每一循環(huán)結(jié)束時，其OPEN表和CLOSED表的排列如下：初始化第1狷環(huán)結(jié)束第2循環(huán)結(jié)束第M循環(huán)結(jié)束第4循環(huán)結(jié)束第了狷環(huán)結(jié)束第五狷環(huán)結(jié)束-第了狷環(huán)結(jié)束OPEN表CLODED表)L(S(4)4(B(4)0(6)4(D(5)玖習(xí)C(6)F(6)4(玖習(xí)A(6)C(6)F(6)G(6)H)4(1(5)A(6)C(6)F(6)G(6)HJ)4(K(5)A(6)0(6)F(6)G(6)HJ)4(U5)A(6)C(6)FG(6)HJM)第四歩成功退出4()4(s(4)B(4)P(s(4)B(4)D(5)4(s(4)B(4)D(5)玖習(xí))A(s(4)B(4)D(5)玖習(xí)1(5)4(s(4)B(4)D(5)玖習(xí)1(5)K(5)J根據(jù)目標(biāo)節(jié)點L返回到s的指針，可得解路徑S(4),B(5),E(5),1(5),K(5),L(5)圖2.7給出的是使用A算法求解8數(shù)碼問題的搜索圖。其中A、B、C等符號，只是為了標(biāo)記節(jié)點的名稱，沒有特殊意義。這些符號旁邊括弧中的數(shù)字是該節(jié)點的評價函數(shù)值f。而圓圈中的值，則表示節(jié)點的擴展順序。從圖