《人工智能導論》試驗 河南理工大學《人工智能》試驗指導試驗內容試驗一狀態空間搜尋試驗試驗二A*算法試驗試驗三子句消解試驗試驗四化為子句集的九步法試驗試驗五BP網絡試驗溫馨提示：上述試驗可以承受任何自己生疏的語言來實現0《人工智能導論》試驗 河南理工大學試驗一 狀態空間搜尋試驗——八數碼問題〔必修，2學時〕一、試驗目的及內容試驗目的：理解和把握狀態空間搜尋的策略試驗內容要求：3X31—8求實現這個問題:將該九宮風格整為某種有序的形式，調整的原則為每次只能將空格〔上、下、左、右〕相鄰的一個數字平移到空格中，試編程實現這一問題的求解二、試驗原理及根本技術路線圖〔方框原理圖或程序流程圖〕試驗原理：算法分析：試驗流程圖：三、所用儀器、材料〔設備名稱、型號、規格等或使用軟件〕四、試驗方法、步驟〔或：程序代碼或操作過程〕試驗步驟試驗源程序六、試驗結果、分析和結論1《人工智能導論》試驗 河南理工大學試驗二 A*算法試驗〔2學時〕一、試驗目的：A*算法求解N數碼難題，理解求解流程和搜尋挨次。二、試驗原理：A*算法是一種有序搜尋算法，其特點在于對估價函數的定義上。對于一般的有序搜尋，總是選擇f值最小的節點作為擴展節點。因此，f是依據需要找到一條最小代價路徑的觀點來估算節點的，所以，可考慮每個節點n的估價函數值為兩個重量：從起始節點到節點n的代價以及從節點n到達目標節點的代價。三、試驗條件：N數碼難題演示程序。IE6.0以上，可以上Internet。三、試驗內容：815數碼為例實際求解A*算法。畫出A*算法求解框圖。分析估價函數對搜尋算法的影響。分析A*算法的特點。四、試驗步驟：開頭演示。進入N815數碼，點擊“選擇數碼”按鈕確定。第一次啟動后，點擊兩次“缺省”或者“隨機”按鈕，才會消滅圖片。2點擊“缺省棋局列的初始節點。算法執行。點擊“連續執行”則程序自動搜尋求解，并演示每一步結果；點擊“單步運行”則每次執行一步求解流程15數碼15數碼難題演示實例。算法流程的任一時刻的相關狀態,openclose5種形式在按鈕上方同步顯示,便于深入學習理解A*算法。依據程序運行過程畫出A*算法框圖。其它可參考幫助文件。五、試驗報告要求：A*算法流程圖和算法框圖。試分析估價函數的值對搜尋算法速度的影響。依據A*算法分析啟發式搜尋的特點。3《人工智能導論》試驗 河南理工大學試驗三子句消解試驗〔2〕一、試驗目的：理解含有變量的子句如何使用消解規章，把握子句消解的原理和規章，能嫻熟進展任意兩個子句的消解，了解消解推理的某些常用規章。二、試驗原理：對子句集進展消解推理，得到相應的結論。為了對含有變量的子句使用消解規章，我們必需找到一個置換，作用于父輩子句使其含有互補文字。消解兩個子句時，可能有一個以上的消解式，不過，在任何狀況下最多有有限個消解式。三、試驗條件子句消解推理演示程序。IE6.以上，可以上Internt四、試驗內容：運行并觀看演示實例。輸入的子句，檢查消解結果。依據消解過程理解消解原理和常用規章。五、試驗步驟：默認例如演示。進入演示實例，點擊“演示實例1消解結果。分別運行“演示實例”和“演示實例4用。自定義消解子句。點擊“系統重置”按鈕，再通過鍵盤與兩個按鈕“～”與“∨”結果。重復步驟3，屢次輸入不同子句進展消解，生疏消解過程。六、試驗結論：生疏消解過程，理解子句消解規章。給出自己輸入的待消解子句、消解結果和具體過程。5《人工智能導論》試驗 河南理工大學試驗四化為子句集的九步法試驗〔2學時〕一、試驗目的：理解和把握消解原理，生疏謂詞公式化為子句集的九個步驟，理解消解推理規章，能把任意謂詞公式轉換成子句集。二、試驗原理消解是可用于肯定的子句公式的重要推理規章，任一謂詞演算公式可以化成一個子句集。通過九步法消解可以從這兩個父輩子句推導出一個子句。九步法消解包括消去蘊涵符號、減否認符轄域、對變量標準化、消去存在量詞、化為前束型、化為合取范式、消去全程量詞、消去合取符、更換變量名，依次變換即可得到子句集。三、試驗條件：子句集轉換演示程序。IE6.0以上，可以上Internet。四、試驗內容：理解消解原理，生疏謂詞公式轉換成子句集的步驟。五、試驗步驟：6程的九個步驟按鈕，得到消解結果。自定義消解目標。點擊“去除”刪除默認公式，利用界面鍵盤輸入的消解目標，語法檢查。點擊“語法檢查”檢查輸入謂詞公式的語法錯誤。如無錯誤，則依次點擊步驟按鈕進展消解。重復運行2、3步，生疏消解原理和消解過程。六、試驗報告要求：了解每一步消解的規章和原則。給出一個謂詞公式消解的具體過程和結果。分析消解原理的特點和原理。7《人工智能導論》試驗 河南理工大學試驗五 BP網絡試驗〔4學時〕一、試驗目的：播公式。通過構建BP網絡實例，生疏前饋網絡的原理及構造。二、試驗原理反向傳播(BP)BP算法過程從輸出節點開頭，反向地向第一隱含層(即最接近輸入層的隱含層)傳播由總誤差引起的權值修正。BP(層)節點。輸入信號先向前傳遞到隱節點，經過作用后，再把隱節點的輸出信息傳遞到輸出節點，最終給出輸出結果。三、試驗條件：BP網絡演示程序。IE5.0以上版本，能連通Internet。四、試驗內容：通過BP網絡各項參數的不同設置，觀看BP算法的學習效果。觀看比較BP網絡各項參數變化對于訓練結果的影響。五、試驗步驟：設置各層神經元個數設置。用戶點擊下拉列表框選擇輸入、隱含、輸出各層神經元個數，其中隱含層神經元個數自動設為輸入層神經元個數(n)2n+1個，然后再點擊“確定”BP神經網絡示意圖以及系統隨機生成默認的各層權值。動量因子、迭代次數參數值。各層權值設置，假設用戶使用系統隨機生成默認的各層權值，則進展第4步。用戶8或選中“自定義權”單項選擇框自定義權各層權，在權值設置文本域設置權值后，單擊其后“確定”按鈕?；螂p擊下方列表框選項，相應權值會在權值設置文本域消滅，則進“確定”后兩種方式均會成功地激活“確定”按鈕。學習樣本設置，單文本域中消滅“入層”字樣表示在單文本域中設置輸入層神經元信號向量。單文本域中消滅“出層”字樣表示在單文本域中設置輸出層神經元信號如選中，則“校正網絡”按鈕會成功地激活。樣本列表框也具有如步3的雙擊修改功能。“校正網絡”按鈕成功地激活后，單擊“校正網絡”按鈕，進展網絡學習。當學習完成后〔重設置初始權值、或學習樣本等方式〕讓網絡重“學習六、試驗結論：BP網絡的根本構造及BP算法的訓練過程。試述閾值函數和權值變化對BP網絡推理結果的影響。9《人工智能導論》試驗 河南理工大學試驗一狀態空間搜尋試驗樣例——八數碼問題一、試驗目的及內容試驗目的：理解和把握狀態空間搜尋的策略試驗內容要求：3X31—8求實現這個問題:將該九宮風格整為某種有序的形式，調整的原則為每次只能將空格〔上、下、左、右〕相鄰的一個數字平移到空格中，試編程實現這一問題的求解〕試驗原理：也就是奇數排列和偶數排列。我們可以把一個隨機排列的數組從左到右從上到下用一個數組表示，例如｛８，７，１，５，２，６，３，４，０｝其中０代表空格。它在奇序列位置上。在這個數組中我們首先計算它能夠重排列出來的結果，公式就是：∑〔Ｆ〔Ｘ〕〕＝Ｙ，其中Ｆ〔Ｘ〕，就是一個數他前面比這個數小的數的個數，Ｙ為奇數和偶數個有一種解法。那么上面的數組我們就可以解出它的結果。算法分析：九宮問題的求解方法就是交換空格〔０〕位置，直至到達目標位置為止。圖形表示就是：因此可知：九宮的所以排列有９！種，也就是３６２８８０種排法，數據量是格外大的，我使用廣度搜尋，需要記住每一個結點的排列形式，要是用數組記錄的話會占用很多的內存，我們把數據進展適當的壓縮。使用ＤＷＯＲＤ形式保存，壓縮形式是每個數字用３位表示，這樣就是３×９＝２７個字節，由于８的二進制表示形式１０００，不能用３位表示，我使用了一個小技巧就是將８表示位０００，然后用多出來的５個字表示８所在的位置，就可以用ＤＷＯＲＤ表示了。用移位和或操作將數據逐個移入，比乘法速度要快點。定義了幾個結10果來存儲遍歷到了結果和搜尋完成后保存最優路徑。試驗流程圖：開頭開頭0~8數碼序列建立一個隊列，將初始結點入隊，并設置隊列頭和尾指取出隊列頭〔頭指針所指〕的結點進展擴展，從它擴展出子結點，并將這些結點按擴展的挨次參加隊列推斷擴展出的結點與隊列中的結點是否重復否是隊列頭的結點可以擴展，直接返回其次步。否則將隊列頭指針指向下一結點，再返回其次步。否推斷擴展出的結點是否是目標結點，是顯示路徑程序完畢三、所用儀器、材料〔設備名稱、型號、規格等或使用軟件〕硬件:個人計算機 一臺,MicrosoftVisualC++6.0四、試驗方法、步驟〔或：程序代碼或操作過程〕11試驗步驟C++6.0得文檔。輸入源程序代碼，進展編譯，調試運行。運行結果，按提示要求輸入1—8這八個數，進展程序測驗。試驗源程序#include<stdio.h>#include<stdlib.h>#include<windows.h>#include<queue>#include<stack>usingnamespacestd;#defineHashTableSize362881#defineNOT !#defineUP 0#defineDOWN 1#defineLEFT 2#defineRIGHT 3#defineBit typedefstructmaps{Bitdetail[9];intmyindex; //記錄自己節點在hash表中的位置Bitposition; //記錄空格〔0〕在序列中的位置}Map,*PMap;Map org; // 初始狀態int EndIndex; 目標//上移，下移， 左移 ，右移intconstderection[4]={-3 ,3 , -1 ,1};//可移動的四個方向intconstFactorial[9]={40320,5040,720,120,24,6,2,1,1};intHashTable[HashTableSize]={0};//hash表,其中記錄的是上一個父節點對應的位置voidinput12{inti,j;intsum,count,index;for(i=0;i<9;i++){scanf(“%1d“,&org.detail[i]);org.detail[i]||(org.position=i);}for(i0i9i //計算逆序{if(0==org.detail[i])continue;for(j=0;j<i;j++)sum+=(0!=org.detail[j]&&org.detail[j]<org.detail[i]);}for(i0index0i9i //hash{for(j=0,count=0;j<i;j++)count+=org.detail[j]>org.detail[i];index+=Factorial[org.detail[i]]*count;}org.myindex=index+1;EndIndexsum%2161328:322561; return;}/***hash值的計算*Parenthash*direcinlineintHashValue(Map&Parentint&direct{inti=Parent.position;intnewindex=Parent.myindex;Bit*p=Parent.detail;switch(direct){caseUP:{newindex-=3*40320;newindex+=(p[i-2]>p[i-3])?(Factorial[p[i-3]]):(-Factorial[p[i-2]]);newindex+=(p[i-1]>p[i-3])?(Factorial[p[i-3]]):(-Factorial[p[i-1]]);13break;}caseDOWN:{newindex+=3*40320;newindex-=(p[i+2]>p[i+3])?(Factorial[p[i+3]]):(-Factorial[p[i+2]]);newindex-=(p[i+1]>p[i+3])?(Factorial[p[i+3]]):(-Factorial[p[i+1]]);break;}caseLEFT:returnnewindex-40320;break;caseRIGHT:returnnewindex+40320;break;}returnnewindex;}/**** 寬度優先搜尋***/voidBfs{queue<Map>Queue;Queue.push(org);HashTable[org.myindex]=-1;while(NOTQueue.empty){Mapnode=Queue.front;Queue.pop;for(intk=0;k<4;k++){Maptmp=node;tmp.position=node.position+derection[k];if(tmp.position<0||tmp.position>8||(k>1&&tmp.position/3!=node.position/3))continue;tmp.myindex=HashValue(node,k);if(0!=HashTable[tmp.myindex])continue;tmp.detail[node.positiontmp.detail[tmp.position//移動空格tmp.detail[tmp.position]=0;HashTable[tmp.myindex]node.myindex; //狀態記錄到hashtable中if(node.myindex==EndIndex)return;Queue.push(tmp);}14}return;}/****通過hash表中記錄的進展查找路徑***/voidFindPath{intnowindex;intcount=0;intnixu[9],result[9];inti,j,k;stack<int>Stack;Stack.push(EndIndex);nowindex=EndIndex;while(-1!=HashTable[nowindex]){Stack.push(HashTable[nowindex]);nowindex=HashTable[nowindex];}printf(%d\n“,Stack.size-1);getchar;while(NOTStack.empty){nowindex=Stack.top-1;Stack.pop;for(i0i9;i //計算出逆序{nixu[i]=nowindex/Factorial[i];nowindex%=Factorial[i];}memset(result,-1,9*sizeof(int));for(i=0i9i //依據逆序計算排列{for(j=0,k=nixu[i];j<9;j++){if(result[