人工智能實驗報告

1、人工智能課內(nèi)實驗報告主觀貝葉斯方法的研究一、 實驗題目主觀Bayes方法的研究。二、 實驗目的在證據(jù)不確定的情況下，根據(jù)充分性量度LS、必要性量度LN、E的先驗概率P(E)和H的先驗概率P(H)作為前提條件，分析P(H/S)和P(E/S)的關(guān)系。三、 實驗原理 1、 證據(jù)不確定性的表示 1. 在主觀Bayes方法中，證據(jù)的不確定性用概率表示。對于證據(jù)E，由用戶根據(jù)觀察S給出P(E|S)，即動態(tài)強度。用P(E|S)描述證據(jù)的不確定性 （證據(jù)E不是可以直接觀測的）。 2. 證據(jù)肯定存在時，P(E|S)=1；3. 證據(jù)肯定不存在時， P(E|S)=0；4. 證據(jù)具有不確定性時， 0P(E|S)1且L

2、N1的取值因為： LS1：表明證據(jù)E是對H有利的證據(jù)。 LN1：表明證據(jù)E是對H有利的證據(jù)。3. 不能出現(xiàn)LS1且LN1的取值因為：LS1: 表明證據(jù) E是對H不利的證據(jù)。 LN1， LN1。 3、證據(jù)不確定的情況 在現(xiàn)實中，證據(jù)肯定存在和肯定不存在的極端情況是不多的，更多的是介于二者之間的不確定情況。對初始證據(jù)來說，由于用戶對客觀事物或現(xiàn)象的觀察不是很精確，因而所提供的證據(jù)是不確定的；另外，一條知識的證據(jù)往往來源于另一條知識推出的結(jié)論，一般也具有某種程度的不確定性。所以我們要在S對E的觀察的先驗概率0P(E/S)1的情況下確定H的后驗概率P(H/S)。 在證據(jù)確定的情況下，我們因該用杜達等人

3、1976年證明了的公式來進一步討論：分四種情況討論這個公式：1. P(E/S)=1當P(E/S)=1時，P(-E/S)=0。此時公式變成(肯定存在的情況)：2. P(E/S)=0當P(E/S)=0時，P(-E/S)=1.此時公式變成(肯定不存在的情況)：3. P(E/S)=P(E)當P(E/S)=P(E)時，表示E與S無關(guān)。利用全概率公式就將公式變?yōu)椋?. 當P(E/S)為其它值時，通過分段線性插值就可得到計算P(H/S)的公式：該公式稱為EH公式或UED公式。四、實驗程序ls=input(ls=);ln=input(ln=);ph=input(ph=);pe=input(pe=);phe=(

4、ls*ph)/(ls-1)*ph+1);phfe=(ln*ph)/(ln-1)*ph+1);phs=;for pes=0:0.01:1 if pesM（mi），G：=ADD（mi，G）針對M中子節(jié)點的不同情況，分別進行如下處理：對于那些未曾在G中出現(xiàn)過的M成員設置一個指向父節(jié)點（n）的指針，并把它放入OPEN表；對于那些先前已在G中出現(xiàn)過的M成員，確定是否要修改指向父節(jié)點的指針；對于那些先前已在G中出現(xiàn)，并且已經(jīng)擴展了的M成員，確定是否需要修改其后繼結(jié)點指向父節(jié)點的指針。（6)按某種搜索策略對OPEN表中的節(jié)點進行排序（7)轉(zhuǎn)第2步。2.2.2A*算法我在實驗中采用A*算法實現(xiàn)重排九宮格。A*

5、算法是一種全局擇優(yōu)的啟發(fā)式算法，可以證明它具有最優(yōu)性。A*算法可以描述為f(n）=h（n）+g（n）的形式。其中，h（n）被稱作啟發(fā)函數(shù)，是當前結(jié)點到目標結(jié)點的代價描述；而g（n）是代價函數(shù)，描述了起始結(jié)點到當前結(jié)點的代價；f（n）是估價函數(shù)。A*算法是不回溯的，每次都選擇f值最小的路徑推進。在程序中，我按如下思路實現(xiàn)了A*算法。其中，啟發(fā)函數(shù)h（n）我選取的是當前結(jié)點和目標結(jié)點狀態(tài)不同的個數(shù)。（1）建立一個鏈表，計算初始結(jié)點的估價函數(shù)f，并將初始結(jié)點入表，設置鏈表頭和尾指針。（2）取出頭（頭指針所指）結(jié)點，如果該結(jié)點是目標結(jié)點，則輸出路徑，程序結(jié)束。否則對結(jié)點進行擴展。（3）檢查擴展出的新結(jié)

6、點是否與鏈表中的結(jié)點重復，若與不能再擴展的結(jié)點重復（位于頭指針之前），則將它拋棄；若新結(jié)點與待擴展的結(jié)點重復（位于頭指針之后），則比較兩個結(jié)點的估價函數(shù)中g(shù)的大小，保留較小g值的結(jié)點。跳至第五步。（4）如果擴展出的新結(jié)點與鏈表中的結(jié)點不重復，則按照它的估價函數(shù)f大小將它插入頭結(jié)點后待擴展結(jié)點的適當位置，使它們按從小到大的順序排列，最后更新尾指針。（5）如果頭結(jié)點還可以擴展，直接返回第二步。否則將頭指針指向下一結(jié)點，再返回第二步。四、實驗程序#include #include #include #include /#includeusing namespace std;const int ROW

7、 = 3;/行數(shù)const int COL = 3;/列數(shù)const int MAXDISTANCE = 10000;/最多可以有的表的數(shù)目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; / distance between one state and the destination一個表和目的表的距離 int dep; / the depth of node深度 / So the comment function = dist + dep.估價函數(shù)值 int index; / point to

8、the location of parent父節(jié)點的位置 Node;Node src, dest;/ 父節(jié)表 目的表vector node_v; / store the nodes存儲節(jié)點bool isEmptyOfOPEN() /open表是否為空 for (int i = 0; i node_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true;bool isEqual(int index, int digitCOL) /判斷這個最優(yōu)的節(jié)點是否和目的節(jié)點一樣 for (int i = 0; i ROW; i+

9、) for (int j = 0; j COL; j+) if (node_vindex.digitij != digitij) return false; return true;ostream& operator(ostream& os, Node& node) for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) os node.digitij ; os endl; return os;void PrintSteps(int index, vector& rstep_v)/輸出每一個遍歷的節(jié)點 深度遍歷 rstep_v.push_ba

10、ck(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; cout - = 0; i-)/輸出每一步的探索過程 cout step： rstep_v.size() - i endl rstep_vi endl-endl;void Swap(int& a, int& b) int t; t = a; a = b; b = t;void Assign(Node& node, int index) for (int

11、i = 0; i ROW; i+) for (int j = 0; j COL; j+) node.digitij = node_vindex.digitij;int GetMinNode() /找到最小的節(jié)點的位置 即最優(yōu)節(jié)點 int dist = MAXNUM; int loc; / the location of minimize node for (int i = 0; i node_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) dist) loc = i;

12、 dist = node_vi.dist + node_vi.dep; return loc;bool isExpandable(Node& node) for (int i = 0; i node_v.size(); i+) if (isEqual(i, node.digit) return false; return true;int Distance(Node& node, int digitCOL) int distance = 0; bool flag = false; for(int i = 0; i ROW; i+) for (int j = 0; j COL; j+) for

13、(int k = 0; k ROW; k+) for (int l = 0; l COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance;int MinDistance(int a, int b) return (a b ? a : b);void ProcessNode(int index) int x, y; bool flag; for (int i =

14、0; i ROW; i+) for (int j = 0; j 0) Swap(node_up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up); Node node_down; Assign(node_down, index);/向下擴

15、展的節(jié)點 int dist_down = MAXDISTANCE; if (x 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex.dep + 1; node_v.push_back(node_left); Node node_right;

16、Assign(node_right, index);/向右擴展的節(jié)點 int dist_right = MAXDISTANCE; if (y 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right; node_right.dep = node_vindex.dep + 1; node_v

17、.push_back(node_right); node_vindex.dist = MAXNUM;int main() / 主函數(shù) int number; cout 起始九宮格： endl; for (int i = 0; i ROW; i+)/輸入初始的數(shù)據(jù) for (int j = 0; j number; src.digitij = number; src.index = 0; src.dep = 1; cout 目標九宮格： endl;/輸入目的數(shù)據(jù) for (int m = 0; m ROW; m+) for (int n = 0; n number; dest.digitmn =

18、 number; node_v.push_back(src);/在容器的尾部加一個數(shù)據(jù) clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout 無解！ endl; return -1; else int loc; / the location of the minimize node最優(yōu)節(jié)點的位置 loc = GetMinNode(); if(isEqual(loc, dest.digit) vector rstep_v; cout 起始的九宮格為： endl; cout src endl; PrintSteps(loc, rst

19、ep_v); cout 成功！ endl; break; else ProcessNode(loc); return 0;五、實驗結(jié)果六、實驗總結(jié)這次實驗讓我對狀態(tài)空間的搜索問題有了更深刻的了解，對于學好人工智能這門課程幫助頗大讀書報告-各種各樣的知識表示方法及其應用知識是人類進行一切活動的基礎(chǔ)。具有相對性，不確定性，可表示性與可利用性。人類的智能活動過程是一個獲取知識并運用知識的過程；人工智能問題求解是以知識為基礎(chǔ)；知識的獲取、知識的表示和運用知識進行推理是人工智能學科要研究的主要問題。 人工智能研究的目的是要建立一個模擬人類智能行為的系統(tǒng)，為達到這個目的就必須研究人類智能行為在計算機上的表

20、示形式，只有這樣才能把知識存儲到計算機中去。知識表示是研究用計算機表示知識的可能性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的作用。知識表示實際上就是對人類知識的一種描述，以把人類知識表示成計算機能夠處理的數(shù)據(jù)結(jié)構(gòu)。對知識進行表示的過程就是把知識編碼成某種數(shù)據(jù)結(jié)構(gòu)的過程。按照人們從不同角度進行探索以及對問題的不同理解，知識表示方法可分為陳述性知識表示和過程性知識表示兩大類。對同一知識，一般都可以用多種方法進行表示，不同的方法對同一知識的表示效果是不一樣的，有時需要把幾種表示模式結(jié)合起來，作為一個整體來表示領(lǐng)域知識。知識的表示方法多種多樣，但目前還沒有哪種表

21、示方法可以適應于一切知識系統(tǒng)，不同的知識表示方法各有特色，適用于不同的領(lǐng)域。知識的常見表示方法有：一、經(jīng)典邏輯表示法 一階謂詞邏輯表示法：謂詞邏輯是一種知識表示方法，是到目前為止能夠表達人類思維活動規(guī)律的一種最精確的形式語言；謂詞邏輯與人類的自然語言較接近，又可方便的存儲到計算機中，并被計算機做精確處理。謂詞邏輯是一種最早應用于人工智能中的知識表示方法。知識的謂詞邏輯表示法：1、人類的一條知識一般可以由具有完整意義的由一句話或幾句話表示出來，而這些知識要用謂詞表示出來，一般是一個謂詞公式；2、謂詞公式是用謂詞聯(lián)接符號將一些謂詞聯(lián)接起來所形成的公式；3、用謂詞公式既可以表示事物的狀態(tài)、屬性、概念

22、等事實性的知識，也可以表示事物間具有確定因果關(guān)系的規(guī)則性知識。4、對事實性知識，謂詞邏輯的表示法通常是由以合取符號（）和析取符號（）聯(lián)接形成的謂詞公式表示。一階謂詞邏輯是一種形式語言系統(tǒng)，它用數(shù)理邏輯的方法研究推理的規(guī)律，即條件和結(jié)論之間的蘊含關(guān)系。特點是：1）、自然性。2）、適宜于精確性知識的表示，而不適宜不確定性知識的表示。3）、易實現(xiàn)。4）、有與謂詞邏輯表示法相對應的推理方法（歸結(jié)推理方法或消解法）二、產(chǎn)生式表示法“產(chǎn)生式”是1943年由美國數(shù)學家Post首先提出，他根據(jù)“串替代”規(guī)則提出了一種稱為Post機的計算模型，模型中的每一條規(guī)則稱為一個產(chǎn)生式（產(chǎn)生式表示法又稱為產(chǎn)生式規(guī)則表示法

23、）。1972年，A.Newell和Simon在研究人類的認知模型中開發(fā)了基于規(guī)則的產(chǎn)生式系統(tǒng)。目前，產(chǎn)生式表示法已成為人工智能中應用最多的一種知識表示方法。1、可表示的知識種類適合于表示事實性知識和規(guī)則性知識。在表示事實性知識時又可根據(jù)知識是確定性的還是不確定性的分別進行表示。2、產(chǎn)生式的基本形式產(chǎn)生式通常用于表示因果關(guān)系的知識，基本形式為PQ或者IFPTHENQ其中，P是產(chǎn)生式的前提，用于指出該產(chǎn)生式是否可用的條件；Q是一組結(jié)論或操作，用于指出前提P所指示的條件被滿足時，應該得出的結(jié)論或應該執(zhí)行的操作。3、產(chǎn)生式與謂詞邏輯中蘊含式的區(qū)別（1）產(chǎn)生式的基本形式與謂詞邏輯中的蘊含式具有相同的形式

24、。蘊含式只是產(chǎn)生式的一個特殊情況。（2）蘊含式只能表示精確性的知識。（3）產(chǎn)生式不僅可以表示精確性的知識，而且可以表示不精確性知識。（4）在產(chǎn)生式表示知識的智能系統(tǒng)中，決定一條知識是否可用，只要前提條件與已知事實的相似度達到某個指定的范圍，就認為是可匹配的。（5）在謂詞邏輯中，蘊含式前提條件的匹配總是要求精確匹配。4、產(chǎn)生式系統(tǒng)的組成把一組產(chǎn)生式放在一起，讓它們互相配合，協(xié)同作用，一個產(chǎn)生式生成的結(jié)論可以供另一個產(chǎn)生式作為已知事實使用，以求得問題的解決，這樣的系統(tǒng)稱為產(chǎn)生式系統(tǒng)。產(chǎn)生式系統(tǒng)由三個基本部分組成：規(guī)則庫、綜合數(shù)據(jù)庫和推理機。規(guī)則庫是用于描述某領(lǐng)域內(nèi)知識的產(chǎn)生式集合。綜合數(shù)據(jù)庫又稱為

25、事實庫，用于存放輸入的事實、外部數(shù)據(jù)庫輸入的事實以及中間結(jié)果（事實）和最后結(jié)果的工作區(qū)推理機是一個或一組程序，用來控制和協(xié)調(diào)規(guī)則庫與綜合數(shù)據(jù)庫的運行，包含了推理方式和控制 策略。控制策略的作用就是確定選用什么規(guī)則或如何應用規(guī)則。5、產(chǎn)生式系統(tǒng)推理機的推理方式有正向推理、反向推理、雙向推理。6、產(chǎn)生式表示的特點 (1)清晰性。產(chǎn)生式表示格式固定，形式簡單，規(guī)則間相互較為獨立。 (2)模塊性。知識庫與推理機是分開的。 (3)自然性。產(chǎn)生式表示法用“如果，則”的形式表示知識，是人們常用的表示因果關(guān)系的知識表示形式。產(chǎn)生式既可以表示確定性知識又可以表示不確定性知識，更符合人們?nèi)粘Ｒ姷降膯栴}。三、層次結(jié)構(gòu)表示法1、框架理論：1957年美國著名的人工智能學者明斯基在其論文“