第一篇：人工智能TSP旅行商問題實驗報告
人工智能實驗三實驗報告
班級： 姓名： 學號：
一 實驗題目
TSP問題的遺傳算法實現
旅行商問題（Traveling Salesman Problem, TSP），又譯為旅行推銷員問題、貨擔郎問題，簡稱為TSP問題，是最基本的路線問題。假設有n個可直達的城市，一銷售商從其中的某一城市出發，不重復地走完其余n-1個城市并回到原出發點，在所有可能的路徑中求出路徑長度最短的一條。
應用遺傳算法求解30/10個節點的TSP（旅行商問題）問題，求問題的最優解。
二 實驗目的 熟悉和掌握遺傳算法的基本概念和基本思想； 理解和掌握遺傳算法的各個操作算子，能夠用選定的編程語言設計簡單的遺傳優化系統； 通過實驗培養學生利用遺傳算法進行問題求解的基本技能。
三 實驗要求
掌握遺傳算法的基本原理、各個遺傳操作和算法步驟； 2 要求求出問題最優解，若得不出最優解，請分析原因； 對實驗中的幾個算法控制參數進行仔細定義，并能通過實驗選擇參數的最佳值；
要求界面顯示每次迭代求出的局部最優解和最終求出的全局最優解。
四 數據結構
請說明染色體個體和群體的定義方法。
struct RanSeTi //染色體的個體的定義方法 { int city[cities];//基因的排列（即城市的順序，路徑的組織）
int adapt;//記錄適應度
double p;//記錄其在種群中的幸存概率
} RanSeTi [num], RanSeTi temp[num];//用數組來存儲染色體群體方法
五 實驗算法 說明算法中對染色體的編碼方法，適應度函數定義方法
1)染色體的編碼方法:
即為染色體個體定義過程中生成的基因排列（路徑中城市的順序）
struct RanSeTi //染色體的個體的定義方法 { int city[cities];//基因的排列（即城市的順序，路徑的組織）
int adapt;//記錄適應度
double p;//記錄其在種群中的幸存概率
} RanSeTi [num], RanSeTi temp[num];//用數組來存儲染色體群體方法
2)適應度函數定義方法：
評價函數即適應度函數，在遺傳算法中用來計算一個染色體優劣的函數。在進行遺傳操作和種群進化的時候，每個染色體的適應值是決定它是否進入下一輪種群進化的關鍵因素。適應值高的函數被選作新一代個體的可能性就會大。
TSP問題中適應度函數常取路徑長度的倒數（或倒數的相關函數），如：
f(x1,x2,?,xn)?N
?d(x,xii?1n?1i?1)?d(xn?x1)
其中，N是個調節參數，根據實驗情況進行確定。采用的選擇、交叉、變異操作算子的具體操作
1）選擇操作
我們定義f(xi)為第i（i=1,2,3.....popsize）個染色體的適應度，則每個個體被選中的概率
popsize
for(i=0;i n1= RanSeTi [i].city[j-1]; n2= RanSeTi [i].city[j]; sumdistance+=distance[n1][n2];} RanSeTi [i].adapt=sumdistance;//每條染色體的路徑總和 biggestsum+=sumdistance;//種群的總路徑 } 是： P(xi)?f(xi) ?f(xj?1j) 本題中具體使用的是期望值方法 for(i=0;i } gradient[0]=group[0].p;for(i=1;i if(xuanze[i] { xuan[i]=j;//第i個位置存放第j個染色體 break; } } } //拷貝種群 for(i=0;i for(i=0;i 交叉算子就是把兩個父代個體的部分結構加以替換重組而生成新個體的操作。部分匹配交叉、順序交叉、改進的啟發式順序交叉 //temp1號染色體和temp2染色體交配 for(i=0;i { point1=rand()%cities; point2=rand()%cities; for(j=temp1;j if(jiaopeiflag[j]==1) { temp1=j; break; } for(j=temp1+1;j if(jiaopeiflag[j]==1) { temp2=j; break; } //進行基因交配 if(point1>point2)//保證point1<=point2 { temp=point1; point1=point2; point2=temp; } memset(map1,-1,sizeof(map1)); memset(map2,-1,sizeof(map2)); //斷點之間的基因產生映射 for(k=point1;k<=point2;k++) { map1[group[temp1].city[k]]=group[temp2].city[k]; map2[group[temp2].city[k]]=group[temp1].city[k]; } //斷點兩邊的基因互換 for(k=0;k { temp=group[temp1].city[k]; group[temp1].city[k]=group[temp2].city[k]; group[temp2].city[k]=temp; } for(k=point2+1;k { temp=group[temp1].city[k]; group[temp1].city[k]=group[temp2].city[k]; group[temp2].city[k]=temp; } //處理產生的沖突基因 for(k=0;k { for(kk=point1;kk<=point2;kk++) if(group[temp1].city[k]==group[temp1].city[kk]) { group[temp1].city[k]=map1[group[temp1].city[k]]; break; } } for(k=point2+1;k { for(kk=point1;kk<=point2;kk++) if(group[temp1].city[k]==group[temp1].city[kk]) { group[temp1].city[k]=map1[group[temp1].city[k]]; break; } } for(k=0;k { for(kk=point1;kk<=point2;kk++) if(group[temp2].city[k]==group[temp2].city[kk]) { group[temp2].city[k]=map2[group[temp2].city[k]]; break; } } for(k=point2+1;k { for(kk=point1;kk<=point2;kk++) if(group[temp2].city[k]==group[temp2].city[kk]) { group[temp2].city[k]=map2[group[temp2].city[k]]; break; } } temp1=temp2+1; } 3）變異操作 TSP問題中，經常采取的變異操作主要有：位點變異、逆轉變異、對換變異、插入變異。//隨機產生變異概率 srand((unsigned)time(NULL)); for(i=0;i { bianyip[i]=(rand()%100); bianyip[i]/=100; } //確定可以變異的染色體 t=0; for(i=0;i { if(bianyip[i] { bianyiflag[i]=1; t++; } } //變異操作,即交換染色體的兩個節點 srand((unsigned)time(NULL)); for(i=0;i { if(bianyiflag[i]==1) { temp1=rand()%10; temp2=rand()%10; point=group[i].city[temp1]; group[i].city[temp1]=group[i].city[temp2]; group[i].city[temp2]=point; } } 實驗中采用的算法參數的最佳選擇值是多少 #define cities 10/30 //城市的個數 #define MAXX 150 //迭代次數 #define pc 0.72 //交配概率 #define pm 0.02 //變異概率 #define num 20 //種群的大小 六 實驗結果 要求有實驗運行結果截圖，以及必要的說明 以上部分是每次迭代的步驟結果，通過染色體群體中個體的交配、變異，從而更改染色體的具體基因組成，通過不斷進行適應度計算、存活率的計算，更新已有數值； 以上部分為迭代之后的總結果，輸出最終的種群評價，從染色體種群里面取出最佳的染色體，并進行輸出。要求說明是否搜索到了最優解，如果沒有，請分析原因 本題中根據隨機生成的cities個城市之間的相互距離、隨機產生初試群，通過TSP算法，通過以下步驟： (1)初始化群體; (2)計算群體上每個個體的適應度值;(4)按概率Pc進行交叉操作;(5)按概率Pm進行變異操作;(6)沒有滿足某種停止條件，則轉第(2)步，否則進入(7)； (7)輸出種群中適應度值最優的染色體作為問題的滿意解或最優解。 (3)按由個體適應度值所決定的某個規則選擇將進入下一代的個體;成功找到種群中適應度值最優的染色體作為問題的滿意解或最優解。 若失敗，分析可得失敗原因為：隨機生成的cities個城市之間的相互距離、隨機產生初試群有可能不存在適應度值最優的染色體 七 實驗總結及體會 1.同一問題可能有不同的幾種算法相對應解決： 對于此類旅行者問題，原在數據結構和算法課中學過迪杰斯特拉算法，也可以高效快速的解決給定好初值的最短路徑問題； 在本課中，有學到了新的算法：TSP算法，此算法從遺傳學角度，開辟了一個新的視野。通過每次迭代求出的局部最優解和最終求出的全局最優解。 兩種不同的算法可以求解同一問題，但是角度完全不一樣，從目前自己實驗的結果而言，對于小數據量的輸入均可以快速高效的完成題目。但是遺傳算法可以考慮到的問題復雜度更高，更適合應用于實際。 2.學習時應當重視動手實踐能力： 課堂上講解的遺傳算法較為簡單基礎，對于理論學習而言，十分適合。但一旦應用于實踐時，發現雖然每個部分模塊自己都可以理解并且熟悉，但是對于實際應用，并且切實地解決實際問題仍存在較大的困難。 從理論到實踐，從課本的知識到解決問題，若不及時的加以消化并且切實的應用于解決問題，可以看出知識很難為現實提供幫助。因而應在學習之后及時進行上機實驗，并且達到熟練掌握與運用的階段。 實驗一：知識表示方法 一、實驗目的 狀態空間表示法是人工智能領域最基本的知識表示方法之一，也是進一步學習狀態空間搜索策略的基礎，本實驗通過牧師與野人渡河的問題，強化學生對知識表示的了解和應用，為人工智能后續環節的課程奠定基礎。 二、問題描述 有n個牧師和n個野人準備渡河，但只有一條能容納c個人的小船，為了防止野人侵犯牧師，要求無論在何處，牧師的人數不得少于野人的人數(除非牧師人數為0)，且假定野人與牧師都會劃船，試設計一個算法，確定他們能否渡過河去，若能，則給出小船來回次數最少的最佳方案。 三、基本要求 輸入：牧師人數(即野人人數)：n；小船一次最多載人量：c。 輸出：若問題無解，則顯示Failed，否則，顯示Successed輸出一組最佳方案。用三元組(X1, X2, X3)表示渡河過程中的狀態。并用箭頭連接相鄰狀態以表示遷移過程：初始狀態->中間狀態->目標狀態。 例：當輸入n=2，c=2時，輸出：221->110->211->010->021->000 其中：X1表示起始岸上的牧師人數；X2表示起始岸上的野人人數；X3表示小船現在位置(1表示起始岸，0表示目的岸)。 要求：寫出算法的設計思想和源程序，并以圖形用戶界面實現人機交互，進行輸入和輸出結果，如： Please input n: 2 Please input c: 2 Successed or Failed?: Successed Optimal Procedure: 221->110->211->010->021->000 四、實驗組織運行要求 本實驗采用集中授課形式，每個同學獨立完成上述實驗要求。 五、實驗條件 每人一臺計算機獨立完成實驗。 六、實驗代碼 Main.cpp #include //主函數 void main(){ } system(“pause”);RiverCrossing riverCrossing(n, c);riverCrossing.solve();int n, c;cout<<“Please input n: ”;cin>>n;cout<<“Please input c: ”;cin>>c;RiverCrossing::ShowInfo(); RiverCrossing.h #pragma once #include //船 class Boat { public: }; //河岸狀態 class State Boat(int pastor, int savage);static int c;int pastor;//牧師 int savage;//野人 { public: }; //過河問題 class RiverCrossing { private: };bool move(State *nowState, Boat *boat);//進行一次決策 State* findInList(std::list State operator +(Boat &boat);State operatorboat.pastor, iSavage1);ret.pPrevious = this;return ret;State ret(iPastor + boat.pastor, iSavage + boat.savage, iBoatAtSide + 1);ret.pPrevious = this;return ret; } openList.push_back(new State(State::n, State::n, 1));while(!openList.empty()){ } print(NULL);return false;//獲取一個狀態為當前狀態 State *nowState = openList.front();openList.pop_front();closeList.push_back(nowState);//從當前狀態開始決策 if(nowState->iBoatAtSide == 1){//船在此岸 } //過河的人越多越好，且野人優先 int count = nowState->getTotalCount();count =(Boat::c >= count ? count : Boat::c);for(int capticy = count;capticy >= 1;--capticy){ } //把船開回來的人要最少，且牧師優先 for(int capticy = 1;capticy <= Boat::c;++capticy){ } for(int i = 0;i <= capticy;++i){ } Boat boat(capticyi);if(move(nowState, &boat)) return true;} else if(nowState->iBoatAtSide == 0){//船在彼岸 //實施一步決策，將得到的新狀態添加到列表，返回是否達到目標狀態 bool RiverCrossing::move(State *nowState, Boat *boat){ //獲得下一個狀態 State *destState;if(nowState->iBoatAtSide == 1){ } destState = new State(*nowState1< iSavage<<“,”< iBoatAtSide;if(st.size()> 0)cout<<“-> ”;cout< cout<<“==”< 七、實驗結果 實驗二：九宮重排 一、實驗目的 A*算法是人工智能領域最重要的啟發式搜索算法之一，本實驗通過九宮重排問題，強化學生對A*算法的理解與應用，為人工智能后續環節的課程奠定基礎。 二、問題描述 給定九宮格的初始狀態，要求在有限步的操作內，使其轉化為目標狀態，且所得到的解是代價最小解(即移動的步數最少)。如： 三、基本要求 輸入：九宮格的初始狀態和目標狀態 輸出：重排的過程，即途徑的狀態 四、實驗組織運行要求 本實驗采用集中授課形式，每個同學獨立完成上述實驗要求。 五、實驗條件 每人一臺計算機獨立完成實驗。 六、實驗代碼 Main.cpp #include //主函數 void main(){ NineGrid::ShowInfo(); } string start, end;cout<<“Please input the initial state:(ex:134706582)”< NineGrid.h #pragma once #include #define SPACE '0' #define AT(s, x, y)(s)[(x)* 3 +(y)] enum Move { }; //九宮格狀態 class State { public: int moves;//到此狀態的移動次數 int value;//價值 State *pPrevious;//前一個狀態 State(string &grid, State *pPrevious = NULL);int getReversedCount();//獲取逆序數 void evaluate();//評價函數 bool check(Move move);//檢查是否可以移動 string grid;//用字符串保存當前棋盤狀態 int x, y;//空格所在位置 static State *pEndState;//指向目標狀態，用于評價h的值 UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3 };State takeMove(Move move);//實施移動，生成子狀態 //重載==運算符，判斷兩個狀態是否相等 inline bool operator ==(State &state){ return grid == state.grid;} //九宮重排問題 class NineGrid { private: }; NineGrid.cpp #include “NineGrid.h” #include State* State::pEndState = NULL; /*=======================Methods for class “State”=======================*/ //構造函數 State::State(string &grid, State *pPrevious){ this->grid = grid;NineGrid(string &start, string &dest);bool solve();//求解問題 //用于排序 static bool greater_than(const State *state1, const State *state2);static void ShowInfo();//顯示信息 bool compareReversed();//比較逆序數奇偶性是否相同 bool takeMove(State *nowState, Move move);//進行一次決策 State* findInList(vector public: } this->pPrevious = pPrevious;if(this->pPrevious)this->moves = pPrevious->moves + 1;this->moves = 0;else this->value = 0;evaluate();for(int i = 0;i < 3;++i){ } for(int j = 0;j < 3;++j){ } if(AT(grid, i, j)== SPACE){ } x = i;y = j;return;bool State::check(Move move){ } State State::takeMove(Move move){ switch(move){ case UP: } return true;if(x1 < 0)return false;break;if(y + 1 >= 3)return false;break;case DOWN: case LEFT: case RIGHT: } int destX, destY;switch(move){ case UP: } string tGrid = grid;char t = AT(tGrid, destX, destY);AT(tGrid, destX, destY)= AT(tGrid, x, y);AT(tGrid, x, y)= t;return State(tGrid, this);destX = x1;break;destX = x;destY = y + 1;break;case DOWN: case LEFT: case RIGHT: void State::evaluate(){ for(int ii = 0;ii < 3;++ii){ for(int jj = 0;jj < 3;++jj){ if(AT(grid, i, j)== AT(pEndState->grid, ii, jj)){ h += abs(ijj);int g = moves, h = 0;for(int i = 0;i < 3;++i){ for(int j = 0;j < 3;++j){ //if(AT(grid, i, j)!= AT(pEndState->grid, i, j))// ++h; if(AT(grid, i, j)== SPACE)continue;if(!pEndState)return; } } } } } } this->value = g + h;//求該狀態的逆序數 //逆序數定義為： // 不計空格，將棋盤按順序排列，// 對于grid[i]，存在j 所有棋子的逆序總數為逆序數。int State::getReversedCount(){ } /*=====================Methods for class “NineGrid”=====================*/ //顯示信息 void NineGrid::ShowInfo(){ } //構造函數 NineGrid::NineGrid(string &start, string &dest): startState(start), endState(dest)cout<<“************************************************”< } return count; } if(grid[i] > grid[j])++count;int count = 0;for(int i = 0;i < 9;++i){ if(grid[i] == SPACE) continue;if(grid[j] == SPACE)continue;for(int j = 0;j < i;++j){ { } //當初始狀態和目標狀態的逆序數的奇偶性相同時，問題才有解 bool NineGrid::compareReversed(){ 2;} //解決問題 bool NineGrid::solve(){ } //實施一步決策，將得到的新狀態添加到列表，返回是否達到目標狀態 } print(NULL);return false; } //從當前狀態開始決策 for(int i = 0;i < 4;++i){ } Move move =(Move)i;if(nowState->check(move)){ } if(takeMove(nowState, move)) return true; openList.push_back(new State(startState));while(!openList.empty()){ //獲取一個狀態為當前狀態 State *nowState = openList.back();openList.pop_back();closeList.push_back(nowState);cout<<“==”< cout<<“初始狀態和目標狀態的逆序數的奇偶性不同，問題無解！”< bool NineGrid::takeMove(State *nowState, Move move){ } //檢查給定狀態是否存在于列表中 State* NineGrid::findInList(vector } //根據達到的目標狀態，回溯打印出求解過程 void NineGrid::print(State *endState){ cout<<“Search successed!”< addSymptom(pDisease, strInput);} else { ioFile.close();return true;//添加一個疾病，返回此疾病信息的指針 Disease* Expert::addDisease(const string &name){ } //添加疾病的癥狀 void Expert::addSymptom(Disease *disease,const string &symptom){ } //診斷函數 void Expert::diagnosis(){ cout<<“【癥狀詢問】”< vector vector for(vector bool remove = false;//是否從findList列表中排除本疾病 for(unsigned int j = 0;j <(*ite)->symptomList.size();++j){ Disease *pDisease = *ite;if(find(symptomNotHave.begin(), symptomNotHave.end()，//在symptomNotHave列表中找到此癥狀，直接排除 remove = true;break;findList.end();){ if(symptomInput == “不確定”){ } //添加所有疾病到findList列表中 for(unsigned int i = 0;i < m_DiseaseList.size();++i){ } //添加有此癥狀的疾病到findList列表中 for(unsigned int i = 0;i < m_DiseaseList.size();++i){ } //添加輸入的癥狀到symptomHave列表中 symptomHave.push_back(symptomInput);Disease *pDisease = &m_DiseaseList[i];for(unsigned int j = 0;j < pDisease->symptomList.size();++j){ } if(symptomInput == pDisease->symptomList[j]){ } findList.push_back(pDisease);findList.push_back(&m_DiseaseList[i]);} else { pDisease->symptomList[j])!= symptomNotHave.end()){ } else if(find(symptomHave.begin(), symptomHave.end()，//在symptomHave，symptomNotHave列表中不存在這個癥狀，則詢問 if(optionSelect(“->是否有癥狀”“ + pDisease->symptomList[j] + } //詢問得知有此癥狀，添加癥狀到symptomHave列表中 symptomHave.push_back(pDisease->symptomList[j]);//詢問得知沒有此癥狀，添加癥狀到symptomNotHave列表中，并排除symptomNotHave.push_back(pDisease->symptomList[j]);remove = true;break;pDisease->symptomList[j])== symptomHave.end()){ ”“?n(y/n): ”)){ } else { 此疾病 } } } } if(remove){ } //需要排除此疾病 ite = findList.erase(ite);//迭代器后移 ++ite;} else { cout< } cout< for(unsigned int i = 0;i < findList.size();++i){ } cout< bool Expert::optionSelect(const string &question){ cout< switch(option){ case 'Y': case 'y': return true;case 'N': case 'n': } return false; } return false; Disease.txt [疾病1] 癥狀A 癥狀B 癥狀C 癥狀D [疾病2] 癥狀A 癥狀B 癥狀C [疾病3] 癥狀A 癥狀B 癥狀D 癥狀E [疾病4] 癥狀A 癥狀C 癥狀D [疾病5] 癥狀B 癥狀C 癥狀D 癥狀E [疾病6] 癥狀A 癥狀B [疾病7] 癥狀A 癥狀C 癥狀E [疾病8] 癥狀A 癥狀D [疾病9] 癥狀B 癥狀C 癥狀E [疾病10] 癥狀B 癥狀D [疾病11] 癥狀C 癥狀D 癥狀E 六、實驗結果 人工智能實驗報告 實驗六 遺傳算法實驗II 一、實驗目的： 熟悉和掌握遺傳算法的原理、流程和編碼策略，并利用遺傳求解函數優化問題，理解求解TSP問題的流程并測試主要參數對結果的影響。 二、實驗原理： 旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。 遺傳算法的基本思想正是基于模仿生物界遺傳學的遺傳過程。它把問題的參數用基因代表，把問題的解用染色體代表（在計算機里用二進制碼表示），從而得到一個由具有不同染色體的個體組成的群體。這個群體在問題特定的環境里生存競爭，適者有最好的機會生存和產生后代。后代隨機化地繼承了父代的最好特征，并也在生存環境的控制支配下繼續這一過程。群體的染色體都將逐漸適應環境，不斷進化，最后收斂到一族最適應環境的類似個體，即得到問題最優的解。要求利用遺傳算法求解TSP問題的最短路徑。 三、實驗內容： 1、參考實驗系統給出的遺傳算法核心代碼，用遺傳算法求解TSP的優化問題，分析遺傳算法求解不同規模TSP問題的算法性能。 2、對于同一個TSP問題，分析種群規模、交叉概率和變異概率對算法結果的影響。 3、增加1種變異策略和1種個體選擇概率分配策略，比較求解同一TSP問題時不同變異策略及不同個體選擇分配策略對算法結果的影響。 4、上交源代碼。 四、實驗報告要求： 1、畫出遺傳算法求解TSP問題的流程圖。 2、分析遺傳算法求解不同規模的TSP問題的算法性能。 規模越大，算法的性能越差，所用時間越長。 3、對于同一個TSP問題，分析種群規模、交叉概率和變異概率對算法結果的影響。 （1） 種群規模對算法結果的影響 x 0 1.1 3.5 4.5 y 1.1 5.1 4.5 實驗次數：10 最大迭代步數:100 交叉概率：0.85 變異概率：0.15 種群規模 平均適應度值 最優路徑 25.264 4-5-8-7-6-3-1-0-9-2 26.3428 2-9-1-0-3-6-7-5-8-4 25.1652 1-3-6-7-5-8-4-2-9-0 25.1652 0-1-3-6-7-5-8-4-2-9 25.1652 9-0-1-3-6-7-5-8-4-2 25.1652 1-0-9-2-4-8-5-7-6-3 150 25.1652 5-8-4-2-9-0-1-3-6-7 200 25.1652 1-3-6-7-5-8-4-2-9-0 250 25.1652 3-1-0-9-2-4-8-5-7-6 300 25.1652 5-8-4-2-9-0-1-3-6-7 如表所示，顯然最短路徑為25.1652m,最優路徑為1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到這是一圈，順時針或者逆時針都可以。當種群規模為10，20時，并沒有找到最優解。因此并不是種群規模越小越好。 （2） 交叉概率對算法結果的影響 x 1.1 3.5 3.5 4.5 y 1.1 5.1 8.5 實驗次數：15 種群規模：25 最大迭代步數:100 變異概率：0.15 實驗結果： 交叉概率 最好適應度 最差適應度 平均適應度 最優解 0.001 28.0447 36.6567 32.6002 9-2-6-0-5-4-8-7-3-1 0.01 27.0935 34.9943 32.1495 7-8-3-1-9-2-6-0-5-4 0.1 28.0447 35.3033 31.9372 7-3-1-9-2-6-0-5-4-8 0.15 28.0447 34.1175 31.2183 0-5-4-8-7-3-1-9-2-6 0.2 28.7108 33.9512 30.9035 3-1-9-2-6-5-0-4-7-8 0.25 28.0447 35.1623 30.7456 1-3-7-8-4-5-0-6-2-9 0.3 27.0935 31.9941 29.9428 8-3-1-9-2-6-0-5-4-7 0.35 27.0935 32.8085 30.9945 9-1-3-8-7-4-5-0-6-2 0.4 27.0935 32.5313 30.1534 1-3-8-7-4-5-0-6-2-9 0.45 27.0935 33.2014 30.1757 8-3-1-9-2-6-0-5-4-7 0.5 28.0934 33.6307 30.9026 5-0-2-6-9-1-3-8-7-4 0.55 27.0935 33.5233 29.1304 1-9-2-6-0-5-4-7-8-3 0.6 27.0935 33.2512 30.7836 3-1-9-2-6-0-5-4-7-8 0.65 28.0447 33.7003 30.9371 5-4-8-7-3-1-9-2-6-0 0.7 27.0935 32.0927 29.9502 9-1-3-8-7-4-5-0-6-2 0.75 28.0447 32.4488 30.3699 0-5-4-8-7-3-1-9-2-6 0.8 27.0935 32.1551 29.9382 7-4-5-0-6-2-9-1-3-8 0.85 27.0935 34.5399 30.3594 5-0-6-2-9-1-3-8-7-4 0.9 27.0935 32.6273 30.69 6-0-5-4-7-8-3-1-9-2 0.95 27.0935 32.4672 29.919 6-2-9-1-3-8-7-4-5-0 （注:紅色表示非最優解） 在該情況下，交叉概率過低將使搜索陷入遲鈍狀態，得不到最優解。 （3） 變異概率對算法結果的影響 x 1.1 3.5 3.5 4.5 y 1.1 5.1 8.5 實驗次數：10 種群規模：25 最大迭代步數:100 交叉概率：0.85 實驗結果： 變異概率 最好適應度 最差適應度 平均適應度 最優解 0.001 29.4717 34.732 32.4911 0-6-2-1-9-3-8-7-4-5 0.01 29.0446 34.6591 32.3714 8-4-5-0-2-6-9-1-3-7 0.1 28.0934 34.011 30.9417 5-0-2-6-9-1-3-8-7-4 0.15 27.0935 32.093 30.2568 6-0-5-4-7-8-3-1-9-2 0.2 27.0935 32.2349 30.3144 8-7-4-5-0-6-2-9-1-3 0.25 27.0935 32.718 30.1572 4-5-0-6-2-9-1-3-8-7 0.3 27.0935 32.4488 30.2854 0-5-4-7-8-3-1-9-2-6 0.35 27.0935 33.3167 30.7748 1-3-8-7-4-5-0-6-2-9 0.4 29.0446 34.3705 31.3041 2-0-5-4-8-7-3-1-9-6 0.45 27.0935 31.374 29.6816 2-6-0-5-4-7-8-3-1-9 0.5 27.0935 32.3752 30.2211 2-9-1-3-8-7-4-5-0-6 0.55 27.0935 33.3819 30.6623 1-3-8-7-4-5-0-6-2-9 0.6 28.0934 33.2512 30.36 1-3-8-7-4-5-0-2-6-9 0.65 27.0935 32.7491 30.0201 3-1-9-2-6-0-5-4-7-8 0.7 28.7108 32.4238 30.785 1-3-8-7-4-0-5-6-2-9 0.75 27.0935 31.8928 30.2451 1-9-2-6-0-5-4-7-8-3 0.8 28.0934 31.6135 30.3471 9-1-3-8-7-4-5-0-2-6 0.85 29.662 33.2392 31.1585 2-9-1-3-7-8-4-0-5-6 0.9 28.0447 32.0387 30.4152 0-5-4-8-7-3-1-9-2-6 0.95 28.0447 31.3036 30.0067 9-1-3-7-8-4-5-0-6-2 從該表可知，當變異概率過大或過低都將導致無法得到最優解。 4、增加1種變異策略和1種個體選擇概率分配策略，比較求解同一TSP問題時不同變異策略及不同個體選擇分配策略對算法結果的影響。 不同變異策略和不同個體選擇分配策略幾乎不影響算法運行的時間，但會影響適應度。 五、實驗心得與體會 通過本實驗，更加深入體會了參數設置對算法結果的影響。同一個算法，參數值不同，獲得的結果可能會完全不同。 同時通過本次實驗，使自己對遺傳算法有了更進一步的了解。遺傳算法是一種智能優化算法，它能較好的近似求解TSP問題，在問題規模比較大的時候，遺傳算法的優勢就明顯體現出來，當然不能完全保證能得到最優解。 人工智能課內實驗報告 （8次） 學 院： 自動化學院 班 級： 智能1501 姓 名： 劉少鵬（34）學 號： 06153034 目 錄 課內實驗1：猴子摘香蕉問題的VC編程實現????????1 課內實驗2：編程實現簡單動物識別系統的知識表示???5 課內實驗3：盲目搜索求解8數碼問題?????????18 課內實驗4：回溯算法求解四皇后問題?????????33 課內實驗5：編程實現一字棋游戲???????????37 課內實驗6：字句集消解實驗?????????????46 課內實驗7：簡單動物識別系統的產生式推理??????66 課內實驗8：編程實現D-S證據推理算法????????78 人工智能課內實驗報告 實驗1：猴子摘香蕉問題的VC編程實現 學 院： 自動化學院 班 級： 智能1501 姓 名： 劉少鵬（33）學 號： 06153034 日 期： 2017-3-8 10:15-12:00 實驗1：猴子摘香蕉問題的VC編程實現 一、實驗目的 （1）熟悉謂詞邏輯表示法； （2）掌握人工智能謂詞邏輯中的經典例子——猴子摘香蕉問題的編程實現。 二、編程環境 VC語言 三、問題描述 房子里有一只猴子（即機器人），位于a處。在c處上方的天花板上有一串香蕉，猴子想吃，但摘不到。房間的b處還有一個箱子，如果猴子站到箱子上，就可以摸著天花板。如圖1所示，對于上述問題，可以通過謂詞邏輯表示法來描述知識。要求通過VC語言編程實現猴子摘香蕉問題的求解過程。 圖1 猴子摘香蕉問題 四、源代碼 #include printf(“Step %d:monkey從%c走到%cn”, ++i, x, y);//x表示猴子的位置，y為箱子的} void Monkey_Move_Box(char x, char y){ 位置 printf(“Step %d:monkey把箱子從%c運到%cn”, ++i, x, y);//x表示箱子的位置，y為} void Monkey_On_Box(){ 香蕉的位置 printf(“Step %d:monkey爬上箱子n”, ++i);} void Monkey_Get_Banana(){ printf(“Step %d:monkey摘到香蕉n”, ++i);} void main(){ unsigned char Monkey, Box, Banana;printf(“********智能1501班**********n”);printf(“********06153034************n”);printf(“********劉少鵬**************n”);printf(“請用a b c來表示猴子箱子香蕉的位置n”);printf(“Monkeytboxtbananan”);scanf(“%c”, &Monkey);getchar();printf(“t”);scanf(“%c”, &Box);getchar();printf(“tt”);scanf(“%c”, &Banana);getchar();printf(“n操作步驟如下n”);if(Monkey!= Box){ Monkey_Go_Box(Monkey, Box);} if(Box!= Banana){ Monkey_Move_Box(Box, Banana);} Monkey_On_Box();Monkey_Get_Banana();printf(“n”); getchar();} 五、實驗結果相關截圖 六、心得體會 通過本次實驗，我初步了學會了使用VC的新建工程，并且進行簡單的程序編寫。此外我還學會如何使用一些謂詞來解決生活中的一些簡單問題，并且用VC編程給出具體的操作步驟,感覺對VC編程有了新的認識。在實驗中我也遇到過許多問題，比如在我寫完代碼進行編譯時總是會出現一個錯誤“ fatal error C1010: 在查找預編譯頭時遇到意外的文件結尾，是否忘記了向源中添加“#include ‘stdafx.h’”關于這個錯誤我我問了幾個同學得不出答案后，我決定通過上網查找，最終找到了解決方法，需要在該項目的每一個cpp結尾的文件屬性中設置不使用預編譯頭即可。在這個過程中也鍛煉了自己解決問題的能力。 人工智能課內實驗報告 實驗2：編程實現簡單動物識別系統的知識表示 學 院： 自動化學院 班 級： 智能1501 姓 名： 劉少鵬（33）學 號： 06153034 日 期： 2017-3-13 10:15-12:00 實驗2：編程實現簡單動物識別系統的知識表示 一、實驗目的 1、理解和掌握產生式知識表示方法； 2、能夠通過VC編程語言實現產生式系統的規則庫。 二、實驗內容 1、以動物識別系統的產生式規則為例； 2、用選定的編程語言建造規則庫和綜合數據庫，并能對它們進行增加、刪除和修改操作。 三、實驗步驟 1、確定需要識別的動物及其屬性 本次實驗的簡單動物識別系統總共能識別7種動物，即：老虎、金錢豹、斑馬、長頸鹿、企鵝、鴕鳥和信天翁。 2、建立識別七種動物識別系統的規則 3、選定編程語言并確定綜合數據庫和規則庫結構（1）選用C語言作為編程語言 （2）綜合數據庫的建立（3）規則庫的建立 四、程序源代碼 #include { int count;char pre[255];char back[255];int mark;};void check();RULES r[100] = { { 1,“有毛發”,“哺乳動物”,0 }, { 1,“有奶”,“哺乳動物”,0 }, { 1,“有羽毛”,“鳥”,0 }, { 2,“會飛&下蛋&”,“鳥”,0 }, { 1,“吃肉”,“食肉動物”,0 }，//所有規則靜態數據庫 { 3,“有鋒利的牙齒&有爪&眼睛盯著前方&”,“食肉動物”,0 }, { 2,“哺乳動物&有蹄&”,“有蹄類哺乳動物”,0 }, { 2,“哺乳動物&反芻&”,“有偶蹄類哺乳動物”,0 }, { 4,“哺乳動物&食肉動物&黃褐色&有暗斑&”,“金錢豹”,0 }, { 4,“哺乳動物&食肉動物&黃褐色&黑色條紋&”,“老虎”,0 }, { 4,“有蹄類哺乳動物&有長脖子&有長腿&有暗斑&”,“長頸鹿”,0 }, { 2,“有蹄類哺乳動物&黑條紋&”,“斑馬”,0 }, { 5,“鳥&不會飛&有長脖子&有長腿&黑白色&”,“鴕鳥”,0 }, { 4,“鳥&不會飛&會游泳&黑白色&”,“企鵝”,0 }, { 2,“鳥&會飛&”,“信天翁”,0 }, { 1,“反芻”,“哺乳動物”,0 } };int number;int m;int cat = 15;int a;int length;void input(){ //輸入的事實長度 string f[255]; //輸入的事實數組 while(1){ cat++;cout << “number” << endl;cin >> r[cat].count;cout << “輸入事實，兩種以上的事實請在每個事實后加上‘&’符號” << endl;cin >> r[cat].pre;cout << “輸入結果” << endl;cin >> r[cat].back;r[cat].mark = 0;while(1){ cout << “輸入“1”繼續添加規則,輸入“2”查看規則庫” << endl;int p;cin >> p;if(p == 1){ } else { if(p == 2){ input(); } } check();else { } cout << “輸入錯誤，重新輸入” << endl;} } void delate(){ } cout << “輸入要刪除的條數” << endl;int bar;cin >> bar;for(int t = 0;t <= cat;t++){ r[bar'0' >= 0 && temp[i]'0' >= 0 && temp[j]'0';target[j] = temp[j]3);break;case 2: /* down */ if(blank<6)swap(m + blank, m + blank + 3);break;case 3: /* left */ if(blank!= 0 && blank!= 3 && blank!= 6)swap(m + blank, m + blank1][y1][y-1] =-1; bool flag = true;int i = 0;for(i = 0;i<3;i++)for(int j = 0;j<3;j++)if(s.QP[i][j] == 0)flag = false;if(flag)return NO_BLANK;if(IsWin(s)==-1)return-MAX_NUM;if(IsWin(s)== 1)return MAX_NUM;int count = 0;for(i = 0;i<3;i++) for(int j = 0;j<3;j++) if(s.QP[i][j] == 0)tmpQP[i][j] = 1;else tmpQP[i][j] = s.QP[i][j];for(i = 0;i<3;i++) count +=(tmpQP[i][0] + tmpQP[i][1] + tmpQP[i][2])/ 3;count +=(tmpQP[0][i] + tmpQP[1][i] + tmpQP[2][i])/ 3;for(i = 0;i<3;i++)count +=(tmpQP[0][0] + tmpQP[1][1] + tmpQP[2][2])/ 3;count +=(tmpQP[2][0] + tmpQP[1][1] + tmpQP[0][2])/ 3;for(i = 0;i<3;i++) for(int j = 0;j<3;j++) if(s.QP[i][j] == 0)tmpQP[i][j] =-1;else tmpQP[i][j] = s.QP[i][j];for(i = 0;i<3;i++) count +=(tmpQP[i][0] + tmpQP[i][1] + tmpQP[i][2])/ 3;count +=(tmpQP[0][i] + tmpQP[1][i] + tmpQP[2][i])/ 3;for(i = 0;i<3;i++) count +=(tmpQP[0][0] + tmpQP[1][1] + tmpQP[2][2])/ 3;count +=(tmpQP[2][0] + tmpQP[1][1] + tmpQP[0][2])/ 3;return count;return false;L1: cout << “請輸入棋子的坐標xy: ”; }; } else { } cout << “非法輸入！”;goto L1;int Tic::s_count = 0;//初始化棋盤狀態節點總數，剛開始置為 class demo : public Tic { public: demo(){} bool Judge(){ } virtual bool AutoDone(){ int a, b, i, j, m, n, max, min, x, y;if(IsWin(States[0])==-1){ } a = 0, b = 0;max =-10000;for(x = 0;x<3;x++) for(y = 0;y<3;y++)States[11].QP[x][y] = States[0].QP[x][y];cout << “恭喜您獲勝！” << endl;return true;int i, j, a = 0;for(i = 0;i<3;i++)for(j = 0;j<3;j++)if(States[0].QP[i][j] == 0)a++;if(a == 0)return true;return false;for(i = 0;i<3;i++)for(j = 0;j<3;j++){ if(States[0].QP[i][j] == 0){ a = 1; for(x = 0;x<3;x++) for(y = 0;y<3;y++) } } States[a].QP[x][y] = States[0].QP[x][y]; States[a].QP[i][j] = 1;min = 10000; for(m = 0;m<3;m++) for(n = 0;n<3;n++){ } if(States[a].QP[m][n] == 0){ } b = 1; for(x = 0;x<3;x++) for(y = 0;y<3;y++) States[10].QP[x][y] = States[a].QP[x][y]; States[10].QP[m][n] =-1; States[10].e_fun = e_fun(States[10]); if(States[10].e_fun States[a].e_fun = min;if(States[a].e_fun>max){ } max = States[a].e_fun;for(x = 0;x<3;x++) for(y = 0;y<3;y++) States[11].QP[x][y] = States[a].QP[x][y];for(x = 0;x<3;x++)for(y = 0;y<3;y++)States[0].QP[x][y] = States[11].QP[x][y];cout << “計算機走棋” << endl;PrintQP();if(IsWin(States[0])== 1){ } else if(IsWin(States[0])==-1){ } return false; cout << “抱歉你輸了，計算機獲勝！” << endl;return true;cout << “恭喜您獲勝！” << endl;return true; };} void main(){ cout << “****項目名稱：一字棋游戲的實現****” << endl;cout << “****班 級：智 能 1 5 0 1 ****” << endl;cout << “****姓 名：劉 少 鵬****” << endl;cout << “****學 號：0 6 1 5 3 0 3 4 ****” << endl;cout << “****說 明：-1代表人落子位置,1代表電腦落子位置,0代表該位置無棋子 ****” << endl; system(“title #子棋智能小游戲”);system(“color A2”);char IsFirst;bool IsFinish;cout << “若您為先手，請輸入'Y'！反之，請輸入'N':” << endl;cin >> IsFirst;demo *p = new demo();p->init();cout << “棋盤的初始狀態:” << endl;p->PrintQP();do { if(!p->Judge()){ } if(p->Judge())IsFinish = true;if(IsFirst == 'Y'){ } else if(IsFirst == 'N'){ } IsFinish = p->AutoDone();if(!p->Judge()){ } if(!IsFinish){ p->UserInput();p->PrintQP();} p->UserInput();p->PrintQP();if(!p->Judge()){ } IsFinish = p->AutoDone();} while(!IsFinish);if((p->IsWin(p->States[0])== 0)&& p->Judge()){ } } cout << “平局” << endl;system(“pause”);3.2、實驗運行結果截圖 4、實驗心得 本次實驗，我通過學習用VC編程語言設計簡單的博弈游戲，從而理解和掌握博弈樹的啟發式搜索過程，熟悉博弈中兩種最基本的搜索方法——極大極小過程和???過程。并且將這種思想通過代碼表現出來。 本次實驗我最大的收獲不僅僅是學到了課本上的知識，更是學會了如何主動的求解問題的答案。實驗中我遇到了許多困難，不僅僅是有關編程算法方面的，還有一些代碼邏輯流程的設計。這些困難我通過上網和去圖書館查找資料或者向同學請教等方式，逐一解決了困難，我收獲良多。 人工智能課內實驗報告 實驗6：子句集消解實驗 學 院： 自動化學院 班 級： 智能1501 姓 名： 劉少鵬（33）學 號： 06153034 日 期： 2017-05-8 10:15-12:00 實驗6子句集消解實驗 一、實驗目的 （1）熟悉子句集化簡的九個步驟； （2）理解消解規則，能把任意謂詞公式轉換成子句集。 二、編程環境 Visual Studio 2017 三、實驗原理 在謂詞邏輯中，任何一個謂詞公式都可以通過應用等價關系及推理規則化成相應的子句集。 其化簡步驟如下： (1)消去連接詞“→”和“?” 反復使用如下等價公式： P→Q ?﹁ P∨Q P?Q ?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。(2)減少否定符號的轄域 反復使用雙重否定率 ﹁(﹁P)? P 摩根定律 ﹁(P∧Q)?﹁P∨﹁Q ﹁(P∨Q)?﹁P∧﹁Q 量詞轉換率 ﹁(?x)P(x)?(?x)﹁P(x) ﹁(?x)P(x)?(?x)￢P(x)將每個否定符號“﹁”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。 (3)對變元標準化 在一個量詞的轄域內，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現過的任意變元代替，使不同量詞約束的變元有不同的名字。 (4)化為前束范式 化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。 (5)消去存在量詞 (6)化為Skolem標準形 對上述前束范式的母式應用以下等價關系 P∨(Q∧R)?(P∨Q)∧(P∨R)(7)消去全稱量詞(8)消去合取詞 在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。 (9)更換變量名稱 對子句集中的某些變量重新命名，使任意兩個子句中不出現相同的變量名。 四、實驗結果及代碼 //化簡子句集的九步法演示 //作者:劉少鵬 //時間:2017.5 #include void initString(string &ini);//初始化 string del_inlclue(string temp);//消去蘊涵符號 string dec_neg_rand(string temp);//減少否定符號的轄域 string standard_var(string temp);//對變量標準化 string del_exists(string temp);//消去存在量詞 string convert_to_front(string temp);//化為前束形 string convert_to_and(string temp);//把母式化為合取范式 string del_all(string temp);//消去全稱量詞 string del_and(string temp);//消去連接符號合取% string change_name(string temp);//更換變量名稱 //輔助函數定義 bool isAlbum(char temp);//是字母 string del_null_bracket(string temp);//刪除多余的括號 string del_blank(string temp);//刪除多余的空格 void checkLegal(string temp);//檢查合法性 char numAfectChar(int temp);//數字顯示為字符 //主函數 void main(){ cout << “------------------求子句集九步法演示-----------------------” << endl;system(“color 0A”);//orign = “Q(x,y)%~(P(y)”;//orign = “(@x)(P(y)>P)”;//orign = “~(#x)y(x)”;//orign = “~((@x)x!b(x))”;//orign = “~(x!y)”;//orign = “~(~a(b))”;string orign, temp;char command, command0, command1, command2, command3, command4, command5，48 《人工智能》實驗一題目 實驗一 啟發式搜索算法 1.實驗內容： 使用啟發式搜索算法求解8數碼問題。 ⑴ 編制程序實現求解8數碼問題A?算法，采用估價函數 ??w?n?，f?n??d?n???pn????其中：d?n?是搜索樹中結點n的深度；w?n?為結點n的數據庫中錯放的棋子個數；p?n?為結點n的數據庫中每個棋子與其目標位置之間的距離總和。 ⑵ 分析上述⑴中兩種估價函數求解8數碼問題的效率差別，給出一個是p?n?的上界的h?n?的定義，并測試使用該估價函數是否使算法失去可采納性。 2.實驗目的 熟練掌握啟發式搜索A算法及其可采納性。3.數據結構與算法設計 該搜索為一個搜索樹。為了簡化問題，搜索樹節點設計如下： typedef struct Node//棋盤 {//節點結構體 int data[9];double f,g;struct Node * parent;//父節點 }Node,*Lnode;int data[9];數碼數組：記錄棋局數碼擺放狀態。struct Chess * Parent;父節點：指向父親節點。下一步可以通過啟發搜索算法構造搜索樹。 1、局部搜索樹樣例： ? 2、搜索過程 搜索采用廣度搜索方式，利用待處理隊列輔助，逐層搜索（跳過劣質節點）。搜索過程如下： （1）、把原棋盤壓入隊列； （2）、從棋盤取出一個節點； （3）、判斷棋盤估價值，為零則表示搜索完成，退出搜索； （4）、擴展子節點，即從上下左右四個方向移動棋盤，生成相應子棋盤； （5）、對子節點作評估，是否為優越節點（子節點估價值小于或等于父節點則為優越節點），是則把子棋盤壓入隊列，否則拋棄； （5）、跳到步驟（2）； 3、算法的評價 完全能解決簡單的八數碼問題，但對于復雜的八數碼問題還是無能為力。現存在的一些優缺點。 1、可以改變數碼規模（N），來擴展成N*N的棋盤，即擴展為N數碼問題的求解過程。 2、內存泄漏。由于采用倒鏈表的搜索樹結構，簡化了數據結構，但有部分被拋棄節點的內存沒有很好的處理，所以會造成內存泄漏； 3、采用了屏蔽方向，有效防止往回搜索（節點的回推），但沒能有效防止循環搜索，所以不能應用于復雜度較大的八數碼問題； 源碼： #include typedef struct Node {//節點結構體 int data[9];double f,g;struct Node * parent;}Node,*Lnode; typedef struct Stack {//OPEN CLOSED 表結構體 Node * npoint;struct Stack * next;}Stack,* Lstack; Node * Minf(Lstack * Open){//選取OPEN表上f值最小的節點，返回該節點地址 Lstack temp =(*Open)->next,min =(*Open)->next,minp =(*Open);Node * minx; while(temp->next!= NULL){ if((temp->next->npoint->f)<(min->npoint->f)) { min = temp->next; minp = temp; } temp = temp->next;} minx = min->npoint;temp = minp->next;minp->next = minp->next->next;free(temp);return minx;} int Canslove(Node * suc, Node * goal){//判斷是否可解 int a = 0,b = 0,i,j;for(i = 1;i< 9;i++) for(j = 0;j < i;j++) { if((suc->data[i] > suc->data[j])&& suc->data[j]!= 0)a++; if((goal->data[i] > goal->data[j])&& goal->data[j]!= 0)b++; } if(a%2 == b%2)return 1;else return 0;} int Equal(Node * suc,Node * goal){//判斷節點是否相等，相等，不相等 for(int i = 0;i < 9;i ++) if(suc->data[i]!= goal->data[i])return 0; return 1;} Node * Belong(Node * suc,Lstack * list){//判斷節點是否屬于OPEN表或CLOSED表，是則返回節點地址，否則返回空地址 Lstack temp =(*list)-> next;if(temp == NULL)return NULL;while(temp!= NULL){ if(Equal(suc,temp->npoint))return temp-> npoint; temp = temp->next;} return NULL;} void Putinto(Node * suc,Lstack * list){//把節點放入OPEN 或CLOSED 表中 Stack * temp;temp =(Stack *)malloc(sizeof(Stack));temp->npoint = suc;temp->next =(*list)->next;(*list)->next = temp;} ///////////////計算f值部分-開始////////////////////////////// double Fvalue(Node suc, Node goal, int m){//計算f值 switch(m){ case 1:{ int error(Node,Node); int w=0; w=error(suc,goal); return w+suc.g; } case 2:{ double Distance(Node,Node,int); double p = 0; for(int i = 1;i <= 8;i++) p = p + Distance(suc, goal, i); return p + suc.g;//f = h + g; } default: break;} } int error(Node suc,Node goal){//計算錯位個數 int w,i;w=0;for(i=0;i<9;i++){ if(suc.data[i]!=goal.data[i]) w++;} return w;} double Distance(Node suc, Node goal, int i){//計算方格的錯位距離 int k,h1,h2;for(k = 0;k < 9;k++){ if(suc.data[k] == i)h1 = k; if(goal.data[k] == i)h2 = k;} return double(fabs(h1/3h2%3));} ///////////////計算f值部分-結束////////////////////////////// ///////////////////////擴展后繼節點部分的函數-開始///////////////// int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,int m){//判斷子節點是否屬于OPEN或CLOSED表并作出相應的處理 Node * temp = NULL;int flag = 0;if((Belong(*suc,Open)!= NULL)||(Belong(*suc,Closed)!= NULL)){ if(Belong(*suc,Open)!= NULL)temp = Belong(*suc,Open); else temp = Belong(*suc,Closed); if(((*suc)->g)<(temp->g)) { temp->parent =(*suc)->parent; temp->g =(*suc)->g; temp->f =(*suc)->f; flag = 1; } } else { Putinto(* suc, Open); (*suc)->f = Fvalue(**suc, goal, m);} return flag;} int Canspread(Node suc, int n){//判斷空格可否向該方向移動，，表示空格向上向下向左向右移 int i,flag = 0;for(i = 0;i < 9;i++) if(suc.data[i] == 0)break;switch(n){ case 1: if(i/3!= 0)flag = 1;break;case 2: if(i/3!= 2)flag = 1;break;case 3: if(i%3!= 0)flag = 1;break;case 4: if(i%3!= 2)flag = 1;break;default:break;} return flag;} void Spreadchild(Node * child,int n){//擴展child節點的字節點n表示方向，，表示空格向上向下向左向右移 int i,loc,temp;for(i = 0;i < 9;i++) child->data[i] = child->parent->data[i];for(i = 0;i < 9;i++) if(child->data[i] == 0)break;if(n==0) loc = i%3+(i/3-1)*3;else if(n==1) loc = i%3+(i/3 + 1)*3;else if(n==2) loc = i%3-1+(i/3)*3;else loc = i%3+1+(i/3)*3;temp = child->data[loc];child->data[i] = temp;child->data[loc] = 0;} void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, int m){//擴展后繼節點總函數 int i;Node * child;for(i = 0;i < 4;i++){ if(Canspread(**suc, i+1)) //判斷某個方向上的子節點可否擴展 { child =(Node *)malloc(sizeof(Node)); //擴展子節點 child->g =(*suc)->g +1; //算子節點的g值 child->parent =(*suc); //子節點父指針指向父節點 Spreadchild(child, i); //向該方向移動空格生成子節點 if(BelongProgram(&child, Open, Closed, goal, m))// 判斷子節點是否屬于OPEN或CLOSED表并作出相應的處理 free(child); } } } ///////////////////////擴展后繼節點部分的函數-結束////////////////////////////////// Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, int m){//總執行函數 while(1){ if((*Open)->next == NULL)return NULL; //判斷OPEN表是否為空，為空則失敗退出 Node * minf = Minf(Open); //從OPEN表中取出f值最小的節點 Putinto(minf, Closed); //將節點放入CLOSED表中 if(Equal(minf, *goal))return minf; //如果當前節點是目標節點，則成功退出 Spread(&minf, Open, Closed, **goal, m); //當前節點不是目標節點時擴展當前節點的后繼節點 } } int Shownum(Node * result){//遞歸顯示從初始狀態到達目標狀態的移動方法 if(result == NULL)return 0;else { int n = Shownum(result->parent); printf(“第%d步：”,n); for(int i = 0;i < 3;i++) { printf(“n”); for(int j = 0;j < 3;j++) { if(result->data[i*3+j]!= 0) printf(“ %d ”,result->data[i*3+j]); else printf(“ 0 ”); } } printf(“n”); return n+1;} } void Checkinput(Node *suc){//檢查輸入 int i = 0,j = 0,flag = 0;char c;while(i < 9){ while(((c = getchar())!= 10)) { if(c == ' ') { if(flag >= 0)flag = 0; } else if(c >= '0' && c <= '8') { if(flag == 0) { suc->data[i] =(c-'0'); flag = 1; for(j =0;j < i;j++) if(suc->data[j] == suc->data[i])flag =-2; i++; } else if(flag >= 0)flag =-1; } else if(flag >= 0)flag =-1; } if(flag <0 || i < 9) { if(flag < 0) { if(flag ==-1)printf(“含有非法字符或數字!n請重新輸入:n”); else if(flag ==-2)printf(“輸入的數字有重復!n請重新輸入:n”); } else if(i < 9)printf(“輸入的有效數字不夠!n請重新輸入:n”); i = 0; flag = 0; } } } int meassure(Lstack s){ int k=0;while((s->next)!=NULL){ k++; s=s->next;} return k;} void main(){//主函數 //初始操作，建立open和closed表 Lstack Open =(Stack *)malloc(sizeof(Stack));Open->next = NULL;Lstack Closed =(Stack *)malloc(sizeof(Stack));Closed->next = NULL;Node * org =(Node *)malloc(sizeof(Node));org->parent = NULL; //初始狀態節點 org->f =1;org->g =1; Node * goal =(Node *)malloc(sizeof(Node)); //目標狀態節點 Node * result;int m;char c;int k; printf(“=================================n”);printf(“說明:狀態矩陣由0-8 九個數字表示,n請依次按照九宮格上的行列順序輸入,每個數字間用空格隔開。n”); printf(“=================================n”);printf(“請輸入初始狀態(0-8 9個數字以空格隔開回車表示輸入結束):n”);Checkinput(org);printf(“請輸入目標狀態(0-8 9個數字以空格隔開回車表示輸入結束):n”);Checkinput(goal);if(Canslove(org, goal)){//A*算法開始，先將初始狀態放入OPEN表 printf(“請選擇：1.按w(n)搜索 2.按p(n)搜索 n”); scanf(“%d”,&m); while((c = getchar())!= 10); printf(“搜索中，請耐心等待(如果您覺得時間太久請重新執行程序并輸入更快的速度,默認值為)......n”); Putinto(org,&Open); result = Process(&org, &goal, &Open, &Closed, m);//進行剩余的操作 printf(“總步數:%d”,Shownum(result)-1); printf(“n”); k=meassure(Closed); printf(“擴展節點數：n”); printf(“%dn”,k); printf(“Press Enter key to exit!”); while((c = getchar())!= 10);} else printf(“程序認定該起始狀態無法道達目標狀態!n”);}第二篇：人工智能_實驗報告
第三篇：遺傳算法求解TSP問題實驗報告
第四篇：人工智能實驗報告
第五篇：人工智能實驗報告-八數碼
點擊咨詢 