第一篇：人工智能TSP旅行商問題實(shí)驗(yàn)報(bào)告
人工智能實(shí)驗(yàn)三實(shí)驗(yàn)報(bào)告
班級(jí)： 姓名： 學(xué)號(hào)：
一 實(shí)驗(yàn)題目
TSP問題的遺傳算法實(shí)現(xiàn)
旅行商問題（Traveling Salesman Problem, TSP），又譯為旅行推銷員問題、貨擔(dān)郎問題，簡(jiǎn)稱為TSP問題，是最基本的路線問題。假設(shè)有n個(gè)可直達(dá)的城市，一銷售商從其中的某一城市出發(fā)，不重復(fù)地走完其余n-1個(gè)城市并回到原出發(fā)點(diǎn)，在所有可能的路徑中求出路徑長(zhǎng)度最短的一條。
應(yīng)用遺傳算法求解30/10個(gè)節(jié)點(diǎn)的TSP（旅行商問題）問題，求問題的最優(yōu)解。
二 實(shí)驗(yàn)?zāi)康?熟悉和掌握遺傳算法的基本概念和基本思想； 理解和掌握遺傳算法的各個(gè)操作算子，能夠用選定的編程語(yǔ)言設(shè)計(jì)簡(jiǎn)單的遺傳優(yōu)化系統(tǒng)； 通過實(shí)驗(yàn)培養(yǎng)學(xué)生利用遺傳算法進(jìn)行問題求解的基本技能。
三 實(shí)驗(yàn)要求
掌握遺傳算法的基本原理、各個(gè)遺傳操作和算法步驟； 2 要求求出問題最優(yōu)解，若得不出最優(yōu)解，請(qǐng)分析原因； 對(duì)實(shí)驗(yàn)中的幾個(gè)算法控制參數(shù)進(jìn)行仔細(xì)定義，并能通過實(shí)驗(yàn)選擇參數(shù)的最佳值；
要求界面顯示每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。
四 數(shù)據(jù)結(jié)構(gòu)
請(qǐng)說明染色體個(gè)體和群體的定義方法。
struct RanSeTi //染色體的個(gè)體的定義方法 { int city[cities];//基因的排列（即城市的順序，路徑的組織）
int adapt;//記錄適應(yīng)度
double p;//記錄其在種群中的幸存概率
} RanSeTi [num], RanSeTi temp[num];//用數(shù)組來存儲(chǔ)染色體群體方法
五 實(shí)驗(yàn)算法 說明算法中對(duì)染色體的編碼方法，適應(yīng)度函數(shù)定義方法
1)染色體的編碼方法:
即為染色體個(gè)體定義過程中生成的基因排列（路徑中城市的順序）
struct RanSeTi //染色體的個(gè)體的定義方法 { int city[cities];//基因的排列（即城市的順序，路徑的組織）
int adapt;//記錄適應(yīng)度
double p;//記錄其在種群中的幸存概率
} RanSeTi [num], RanSeTi temp[num];//用數(shù)組來存儲(chǔ)染色體群體方法
2)適應(yīng)度函數(shù)定義方法：
評(píng)價(jià)函數(shù)即適應(yīng)度函數(shù)，在遺傳算法中用來計(jì)算一個(gè)染色體優(yōu)劣的函數(shù)。在進(jìn)行遺傳操作和種群進(jìn)化的時(shí)候，每個(gè)染色體的適應(yīng)值是決定它是否進(jìn)入下一輪種群進(jìn)化的關(guān)鍵因素。適應(yīng)值高的函數(shù)被選作新一代個(gè)體的可能性就會(huì)大。
TSP問題中適應(yīng)度函數(shù)常取路徑長(zhǎng)度的倒數(shù)（或倒數(shù)的相關(guān)函數(shù)），如：
f(x1,x2,?,xn)?N
?d(x,xii?1n?1i?1)?d(xn?x1)
其中，N是個(gè)調(diào)節(jié)參數(shù)，根據(jù)實(shí)驗(yàn)情況進(jìn)行確定。采用的選擇、交叉、變異操作算子的具體操作
1）選擇操作
我們定義f(xi)為第i（i=1,2,3.....popsize）個(gè)染色體的適應(yīng)度，則每個(gè)個(gè)體被選中的概率
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個(gè)位置存放第j個(gè)染色體 break; } } } //拷貝種群 for(i=0;i for(i=0;i 交叉算子就是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。部分匹配交叉、順序交叉、改進(jìn)的啟發(fā)式順序交叉 //temp1號(hào)染色體和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; } //進(jìn)行基因交配 if(point1>point2)//保證point1<=point2 { temp=point1; point1=point2; point2=temp; } memset(map1,-1,sizeof(map1)); memset(map2,-1,sizeof(map2)); //斷點(diǎn)之間的基因產(chǎn)生映射 for(k=point1;k<=point2;k++) { map1[group[temp1].city[k]]=group[temp2].city[k]; map2[group[temp2].city[k]]=group[temp1].city[k]; } //斷點(diǎn)兩邊的基因互換 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; } //處理產(chǎn)生的沖突基因 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問題中，經(jīng)常采取的變異操作主要有：位點(diǎn)變異、逆轉(zhuǎn)變異、對(duì)換變異、插入變異。//隨機(jī)產(chǎn)生變異概率 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++; } } //變異操作,即交換染色體的兩個(gè)節(jié)點(diǎn) 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; } } 實(shí)驗(yàn)中采用的算法參數(shù)的最佳選擇值是多少 #define cities 10/30 //城市的個(gè)數(shù) #define MAXX 150 //迭代次數(shù) #define pc 0.72 //交配概率 #define pm 0.02 //變異概率 #define num 20 //種群的大小 六 實(shí)驗(yàn)結(jié)果 要求有實(shí)驗(yàn)運(yùn)行結(jié)果截圖，以及必要的說明 以上部分是每次迭代的步驟結(jié)果，通過染色體群體中個(gè)體的交配、變異，從而更改染色體的具體基因組成，通過不斷進(jìn)行適應(yīng)度計(jì)算、存活率的計(jì)算，更新已有數(shù)值； 以上部分為迭代之后的總結(jié)果，輸出最終的種群評(píng)價(jià)，從染色體種群里面取出最佳的染色體，并進(jìn)行輸出。要求說明是否搜索到了最優(yōu)解，如果沒有，請(qǐng)分析原因 本題中根據(jù)隨機(jī)生成的cities個(gè)城市之間的相互距離、隨機(jī)產(chǎn)生初試群，通過TSP算法，通過以下步驟： (1)初始化群體; (2)計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值;(4)按概率Pc進(jìn)行交叉操作;(5)按概率Pm進(jìn)行變異操作;(6)沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入(7)； (7)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。 (3)按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體;成功找到種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。 若失敗，分析可得失敗原因?yàn)椋弘S機(jī)生成的cities個(gè)城市之間的相互距離、隨機(jī)產(chǎn)生初試群有可能不存在適應(yīng)度值最優(yōu)的染色體 七 實(shí)驗(yàn)總結(jié)及體會(huì) 1.同一問題可能有不同的幾種算法相對(duì)應(yīng)解決： 對(duì)于此類旅行者問題，原在數(shù)據(jù)結(jié)構(gòu)和算法課中學(xué)過迪杰斯特拉算法，也可以高效快速的解決給定好初值的最短路徑問題； 在本課中，有學(xué)到了新的算法：TSP算法，此算法從遺傳學(xué)角度，開辟了一個(gè)新的視野。通過每次迭代求出的局部最優(yōu)解和最終求出的全局最優(yōu)解。 兩種不同的算法可以求解同一問題，但是角度完全不一樣，從目前自己實(shí)驗(yàn)的結(jié)果而言，對(duì)于小數(shù)據(jù)量的輸入均可以快速高效的完成題目。但是遺傳算法可以考慮到的問題復(fù)雜度更高，更適合應(yīng)用于實(shí)際。 2.學(xué)習(xí)時(shí)應(yīng)當(dāng)重視動(dòng)手實(shí)踐能力： 課堂上講解的遺傳算法較為簡(jiǎn)單基礎(chǔ)，對(duì)于理論學(xué)習(xí)而言，十分適合。但一旦應(yīng)用于實(shí)踐時(shí)，發(fā)現(xiàn)雖然每個(gè)部分模塊自己都可以理解并且熟悉，但是對(duì)于實(shí)際應(yīng)用，并且切實(shí)地解決實(shí)際問題仍存在較大的困難。 從理論到實(shí)踐，從課本的知識(shí)到解決問題，若不及時(shí)的加以消化并且切實(shí)的應(yīng)用于解決問題，可以看出知識(shí)很難為現(xiàn)實(shí)提供幫助。因而應(yīng)在學(xué)習(xí)之后及時(shí)進(jìn)行上機(jī)實(shí)驗(yàn)，并且達(dá)到熟練掌握與運(yùn)用的階段。 實(shí)驗(yàn)一：知識(shí)表示方法 一、實(shí)驗(yàn)?zāi)康?/p> 狀態(tài)空間表示法是人工智能領(lǐng)域最基本的知識(shí)表示方法之一，也是進(jìn)一步學(xué)習(xí)狀態(tài)空間搜索策略的基礎(chǔ)，本實(shí)驗(yàn)通過牧師與野人渡河的問題，強(qiáng)化學(xué)生對(duì)知識(shí)表示的了解和應(yīng)用，為人工智能后續(xù)環(huán)節(jié)的課程奠定基礎(chǔ)。 二、問題描述 有n個(gè)牧師和n個(gè)野人準(zhǔn)備渡河，但只有一條能容納c個(gè)人的小船，為了防止野人侵犯牧師，要求無論在何處，牧師的人數(shù)不得少于野人的人數(shù)(除非牧師人數(shù)為0)，且假定野人與牧師都會(huì)劃船，試設(shè)計(jì)一個(gè)算法，確定他們能否渡過河去，若能，則給出小船來回次數(shù)最少的最佳方案。 三、基本要求 輸入：牧師人數(shù)(即野人人數(shù))：n；小船一次最多載人量：c。 輸出：若問題無解，則顯示Failed，否則，顯示Successed輸出一組最佳方案。用三元組(X1, X2, X3)表示渡河過程中的狀態(tài)。并用箭頭連接相鄰狀態(tài)以表示遷移過程：初始狀態(tài)->中間狀態(tài)->目標(biāo)狀態(tài)。 例：當(dāng)輸入n=2，c=2時(shí)，輸出：221->110->211->010->021->000 其中：X1表示起始岸上的牧師人數(shù)；X2表示起始岸上的野人人數(shù)；X3表示小船現(xiàn)在位置(1表示起始岸，0表示目的岸)。 要求：寫出算法的設(shè)計(jì)思想和源程序，并以圖形用戶界面實(shí)現(xiàn)人機(jī)交互，進(jìn)行輸入和輸出結(jié)果，如： Please input n: 2 Please input c: 2 Successed or Failed?: Successed Optimal Procedure: 221->110->211->010->021->000 四、實(shí)驗(yàn)組織運(yùn)行要求 本實(shí)驗(yàn)采用集中授課形式，每個(gè)同學(xué)獨(dú)立完成上述實(shí)驗(yàn)要求。 五、實(shí)驗(yàn)條件 每人一臺(tái)計(jì)算機(jī)獨(dú)立完成實(shí)驗(yàn)。 六、實(shí)驗(yàn)代碼 Main.cpp #include //主函數(shù) 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: }; //河岸狀態(tài) class State Boat(int pastor, int savage);static int c;int pastor;//牧師 int savage;//野人 { public: }; //過河問題 class RiverCrossing { private: };bool move(State *nowState, Boat *boat);//進(jìn)行一次決策 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;//獲取一個(gè)狀態(tài)為當(dāng)前狀態(tài) State *nowState = openList.front();openList.pop_front();closeList.push_back(nowState);//從當(dāng)前狀態(tài)開始決策 if(nowState->iBoatAtSide == 1){//船在此岸 } //過河的人越多越好，且野人優(yōu)先 int count = nowState->getTotalCount();count =(Boat::c >= count ? count : Boat::c);for(int capticy = count;capticy >= 1;--capticy){ } //把船開回來的人要最少，且牧師優(yōu)先 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){//船在彼岸 //實(shí)施一步?jīng)Q策，將得到的新狀態(tài)添加到列表，返回是否達(dá)到目標(biāo)狀態(tài) bool RiverCrossing::move(State *nowState, Boat *boat){ //獲得下一個(gè)狀態(tài) State *destState;if(nowState->iBoatAtSide == 1){ } destState = new State(*nowState1< iSavage<<“,”< iBoatAtSide;if(st.size()> 0)cout<<“-> ”;cout< cout<<“==”< 七、實(shí)驗(yàn)結(jié)果 實(shí)驗(yàn)二：九宮重排 一、實(shí)驗(yàn)?zāi)康?/p> A*算法是人工智能領(lǐng)域最重要的啟發(fā)式搜索算法之一，本實(shí)驗(yàn)通過九宮重排問題，強(qiáng)化學(xué)生對(duì)A*算法的理解與應(yīng)用，為人工智能后續(xù)環(huán)節(jié)的課程奠定基礎(chǔ)。 二、問題描述 給定九宮格的初始狀態(tài)，要求在有限步的操作內(nèi)，使其轉(zhuǎn)化為目標(biāo)狀態(tài)，且所得到的解是代價(jià)最小解(即移動(dòng)的步數(shù)最少)。如： 三、基本要求 輸入：九宮格的初始狀態(tài)和目標(biāo)狀態(tài) 輸出：重排的過程，即途徑的狀態(tài) 四、實(shí)驗(yàn)組織運(yùn)行要求 本實(shí)驗(yàn)采用集中授課形式，每個(gè)同學(xué)獨(dú)立完成上述實(shí)驗(yàn)要求。 五、實(shí)驗(yàn)條件 每人一臺(tái)計(jì)算機(jī)獨(dú)立完成實(shí)驗(yàn)。 六、實(shí)驗(yàn)代碼 Main.cpp #include //主函數(shù) 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 { }; //九宮格狀態(tài) class State { public: int moves;//到此狀態(tài)的移動(dòng)次數(shù) int value;//價(jià)值 State *pPrevious;//前一個(gè)狀態(tài) State(string &grid, State *pPrevious = NULL);int getReversedCount();//獲取逆序數(shù) void evaluate();//評(píng)價(jià)函數(shù) bool check(Move move);//檢查是否可以移動(dòng) string grid;//用字符串保存當(dāng)前棋盤狀態(tài) int x, y;//空格所在位置 static State *pEndState;//指向目標(biāo)狀態(tài)，用于評(píng)價(jià)h的值 UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3 };State takeMove(Move move);//實(shí)施移動(dòng)，生成子狀態(tài) //重載==運(yùn)算符，判斷兩個(gè)狀態(tài)是否相等 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”=======================*/ //構(gòu)造函數(shù) 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();//比較逆序數(shù)奇偶性是否相同 bool takeMove(State *nowState, Move move);//進(jìn)行一次決策 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;//求該狀態(tài)的逆序數(shù) //逆序數(shù)定義為： // 不計(jì)空格，將棋盤按順序排列，// 對(duì)于grid[i]，存在j 所有棋子的逆序總數(shù)為逆序數(shù)。int State::getReversedCount(){ } /*=====================Methods for class “NineGrid”=====================*/ //顯示信息 void NineGrid::ShowInfo(){ } //構(gòu)造函數(shù) 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){ { } //當(dāng)初始狀態(tài)和目標(biāo)狀態(tài)的逆序數(shù)的奇偶性相同時(shí)，問題才有解 bool NineGrid::compareReversed(){ 2;} //解決問題 bool NineGrid::solve(){ } //實(shí)施一步?jīng)Q策，將得到的新狀態(tài)添加到列表，返回是否達(dá)到目標(biāo)狀態(tài) } print(NULL);return false; } //從當(dāng)前狀態(tài)開始決策 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()){ //獲取一個(gè)狀態(tài)為當(dāng)前狀態(tài) State *nowState = openList.back();openList.pop_back();closeList.push_back(nowState);cout<<“==”< cout<<“初始狀態(tài)和目標(biāo)狀態(tài)的逆序數(shù)的奇偶性不同，問題無解！”< bool NineGrid::takeMove(State *nowState, Move move){ } //檢查給定狀態(tài)是否存在于列表中 State* NineGrid::findInList(vector } //根據(jù)達(dá)到的目標(biāo)狀態(tài)，回溯打印出求解過程 void NineGrid::print(State *endState){ cout<<“Search successed!”< addSymptom(pDisease, strInput);} else { ioFile.close();return true;//添加一個(gè)疾病，返回此疾病信息的指針 Disease* Expert::addDisease(const string &name){ } //添加疾病的癥狀 void Expert::addSymptom(Disease *disease,const string &symptom){ } //診斷函數(shù) 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列表中不存在這個(gè)癥狀，則詢問 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(yù) 癥狀B 癥狀C 癥狀D [疾病2] 癥狀A(yù) 癥狀B 癥狀C [疾病3] 癥狀A(yù) 癥狀B 癥狀D 癥狀E [疾病4] 癥狀A(yù) 癥狀C 癥狀D [疾病5] 癥狀B 癥狀C 癥狀D 癥狀E [疾病6] 癥狀A(yù) 癥狀B [疾病7] 癥狀A(yù) 癥狀C 癥狀E [疾病8] 癥狀A(yù) 癥狀D [疾病9] 癥狀B 癥狀C 癥狀E [疾病10] 癥狀B 癥狀D [疾病11] 癥狀C 癥狀D 癥狀E 六、實(shí)驗(yàn)結(jié)果 人工智能實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)六 遺傳算法實(shí)驗(yàn)II 一、實(shí)驗(yàn)?zāi)康模?/p> 熟悉和掌握遺傳算法的原理、流程和編碼策略，并利用遺傳求解函數(shù)優(yōu)化問題，理解求解TSP問題的流程并測(cè)試主要參數(shù)對(duì)結(jié)果的影響。 二、實(shí)驗(yàn)原理： 旅行商問題，即TSP問題（Traveling Salesman Problem）是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問題是一個(gè)組合優(yōu)化問題。該問題可以被證明具有NPC計(jì)算復(fù)雜性。因此，任何能使該問題的求解得以簡(jiǎn)化的方法，都將受到高度的評(píng)價(jià)和關(guān)注。 遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過程。它把問題的參數(shù)用基因代表，把問題的解用染色體代表（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由具有不同染色體的個(gè)體組成的群體。這個(gè)群體在問題特定的環(huán)境里生存競(jìng)爭(zhēng)，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代。后代隨機(jī)化地繼承了父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過程。群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一族最適應(yīng)環(huán)境的類似個(gè)體，即得到問題最優(yōu)的解。要求利用遺傳算法求解TSP問題的最短路徑。 三、實(shí)驗(yàn)內(nèi)容： 1、參考實(shí)驗(yàn)系統(tǒng)給出的遺傳算法核心代碼，用遺傳算法求解TSP的優(yōu)化問題，分析遺傳算法求解不同規(guī)模TSP問題的算法性能。 2、對(duì)于同一個(gè)TSP問題，分析種群規(guī)模、交叉概率和變異概率對(duì)算法結(jié)果的影響。 3、增加1種變異策略和1種個(gè)體選擇概率分配策略，比較求解同一TSP問題時(shí)不同變異策略及不同個(gè)體選擇分配策略對(duì)算法結(jié)果的影響。 4、上交源代碼。 四、實(shí)驗(yàn)報(bào)告要求： 1、畫出遺傳算法求解TSP問題的流程圖。 2、分析遺傳算法求解不同規(guī)模的TSP問題的算法性能。 規(guī)模越大，算法的性能越差，所用時(shí)間越長(zhǎng)。 3、對(duì)于同一個(gè)TSP問題，分析種群規(guī)模、交叉概率和變異概率對(duì)算法結(jié)果的影響。 （1） 種群規(guī)模對(duì)算法結(jié)果的影響 x 0 1.1 3.5 4.5 y 1.1 5.1 4.5 實(shí)驗(yàn)次數(shù)：10 最大迭代步數(shù):100 交叉概率：0.85 變異概率：0.15 種群規(guī)模 平均適應(yīng)度值 最優(yōu)路徑 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,最優(yōu)路徑為1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到這是一圈，順時(shí)針或者逆時(shí)針都可以。當(dāng)種群規(guī)模為10，20時(shí)，并沒有找到最優(yōu)解。因此并不是種群規(guī)模越小越好。 （2） 交叉概率對(duì)算法結(jié)果的影響 x 1.1 3.5 3.5 4.5 y 1.1 5.1 8.5 實(shí)驗(yàn)次數(shù)：15 種群規(guī)模：25 最大迭代步數(shù):100 變異概率：0.15 實(shí)驗(yàn)結(jié)果： 交叉概率 最好適應(yīng)度 最差適應(yīng)度 平均適應(yīng)度 最優(yōu)解 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 （注:紅色表示非最優(yōu)解） 在該情況下，交叉概率過低將使搜索陷入遲鈍狀態(tài)，得不到最優(yōu)解。 （3） 變異概率對(duì)算法結(jié)果的影響 x 1.1 3.5 3.5 4.5 y 1.1 5.1 8.5 實(shí)驗(yàn)次數(shù)：10 種群規(guī)模：25 最大迭代步數(shù):100 交叉概率：0.85 實(shí)驗(yàn)結(jié)果： 變異概率 最好適應(yīng)度 最差適應(yīng)度 平均適應(yīng)度 最優(yōu)解 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 從該表可知，當(dāng)變異概率過大或過低都將導(dǎo)致無法得到最優(yōu)解。 4、增加1種變異策略和1種個(gè)體選擇概率分配策略，比較求解同一TSP問題時(shí)不同變異策略及不同個(gè)體選擇分配策略對(duì)算法結(jié)果的影響。 不同變異策略和不同個(gè)體選擇分配策略幾乎不影響算法運(yùn)行的時(shí)間，但會(huì)影響適應(yīng)度。 五、實(shí)驗(yàn)心得與體會(huì) 通過本實(shí)驗(yàn)，更加深入體會(huì)了參數(shù)設(shè)置對(duì)算法結(jié)果的影響。同一個(gè)算法，參數(shù)值不同，獲得的結(jié)果可能會(huì)完全不同。 同時(shí)通過本次實(shí)驗(yàn)，使自己對(duì)遺傳算法有了更進(jìn)一步的了解。遺傳算法是一種智能優(yōu)化算法，它能較好的近似求解TSP問題，在問題規(guī)模比較大的時(shí)候，遺傳算法的優(yōu)勢(shì)就明顯體現(xiàn)出來，當(dāng)然不能完全保證能得到最優(yōu)解。 人工智能課內(nèi)實(shí)驗(yàn)報(bào)告 （8次） 學(xué) 院： 自動(dòng)化學(xué)院 班 級(jí)： 智能1501 姓 名： 劉少鵬（34）學(xué) 號(hào)： 06153034 目 錄 課內(nèi)實(shí)驗(yàn)1：猴子摘香蕉問題的VC編程實(shí)現(xiàn)????????1 課內(nèi)實(shí)驗(yàn)2：編程實(shí)現(xiàn)簡(jiǎn)單動(dòng)物識(shí)別系統(tǒng)的知識(shí)表示???5 課內(nèi)實(shí)驗(yàn)3：盲目搜索求解8數(shù)碼問題?????????18 課內(nèi)實(shí)驗(yàn)4：回溯算法求解四皇后問題?????????33 課內(nèi)實(shí)驗(yàn)5：編程實(shí)現(xiàn)一字棋游戲???????????37 課內(nèi)實(shí)驗(yàn)6：字句集消解實(shí)驗(yàn)?????????????46 課內(nèi)實(shí)驗(yàn)7：簡(jiǎn)單動(dòng)物識(shí)別系統(tǒng)的產(chǎn)生式推理??????66 課內(nèi)實(shí)驗(yàn)8：編程實(shí)現(xiàn)D-S證據(jù)推理算法????????78 人工智能課內(nèi)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)1：猴子摘香蕉問題的VC編程實(shí)現(xiàn) 學(xué) 院： 自動(dòng)化學(xué)院 班 級(jí)： 智能1501 姓 名： 劉少鵬（33）學(xué) 號(hào)： 06153034 日 期： 2017-3-8 10:15-12:00 實(shí)驗(yàn)1：猴子摘香蕉問題的VC編程實(shí)現(xiàn) 一、實(shí)驗(yàn)?zāi)康?/p> （1）熟悉謂詞邏輯表示法； （2）掌握人工智能謂詞邏輯中的經(jīng)典例子——猴子摘香蕉問題的編程實(shí)現(xiàn)。 二、編程環(huán)境 VC語(yǔ)言 三、問題描述 房子里有一只猴子（即機(jī)器人），位于a處。在c處上方的天花板上有一串香蕉，猴子想吃，但摘不到。房間的b處還有一個(gè)箱子，如果猴子站到箱子上，就可以摸著天花板。如圖1所示，對(duì)于上述問題，可以通過謂詞邏輯表示法來描述知識(shí)。要求通過VC語(yǔ)言編程實(shí)現(xiàn)猴子摘香蕉問題的求解過程。 圖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運(yùn)到%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(“請(qǐng)用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();} 五、實(shí)驗(yàn)結(jié)果相關(guān)截圖 六、心得體會(huì) 通過本次實(shí)驗(yàn)，我初步了學(xué)會(huì)了使用VC的新建工程，并且進(jìn)行簡(jiǎn)單的程序編寫。此外我還學(xué)會(huì)如何使用一些謂詞來解決生活中的一些簡(jiǎn)單問題，并且用VC編程給出具體的操作步驟,感覺對(duì)VC編程有了新的認(rèn)識(shí)。在實(shí)驗(yàn)中我也遇到過許多問題，比如在我寫完代碼進(jìn)行編譯時(shí)總是會(huì)出現(xiàn)一個(gè)錯(cuò)誤“ fatal error C1010: 在查找預(yù)編譯頭時(shí)遇到意外的文件結(jié)尾，是否忘記了向源中添加“#include ‘stdafx.h’”關(guān)于這個(gè)錯(cuò)誤我我問了幾個(gè)同學(xué)得不出答案后，我決定通過上網(wǎng)查找，最終找到了解決方法，需要在該項(xiàng)目的每一個(gè)cpp結(jié)尾的文件屬性中設(shè)置不使用預(yù)編譯頭即可。在這個(gè)過程中也鍛煉了自己解決問題的能力。 人工智能課內(nèi)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)2：編程實(shí)現(xiàn)簡(jiǎn)單動(dòng)物識(shí)別系統(tǒng)的知識(shí)表示 學(xué) 院： 自動(dòng)化學(xué)院 班 級(jí)： 智能1501 姓 名： 劉少鵬（33）學(xué) 號(hào)： 06153034 日 期： 2017-3-13 10:15-12:00 實(shí)驗(yàn)2：編程實(shí)現(xiàn)簡(jiǎn)單動(dòng)物識(shí)別系統(tǒng)的知識(shí)表示 一、實(shí)驗(yàn)?zāi)康?/p> 1、理解和掌握產(chǎn)生式知識(shí)表示方法； 2、能夠通過VC編程語(yǔ)言實(shí)現(xiàn)產(chǎn)生式系統(tǒng)的規(guī)則庫(kù)。 二、實(shí)驗(yàn)內(nèi)容 1、以動(dòng)物識(shí)別系統(tǒng)的產(chǎn)生式規(guī)則為例； 2、用選定的編程語(yǔ)言建造規(guī)則庫(kù)和綜合數(shù)據(jù)庫(kù)，并能對(duì)它們進(jìn)行增加、刪除和修改操作。 三、實(shí)驗(yàn)步驟 1、確定需要識(shí)別的動(dòng)物及其屬性 本次實(shí)驗(yàn)的簡(jiǎn)單動(dòng)物識(shí)別系統(tǒng)總共能識(shí)別7種動(dòng)物，即：老虎、金錢豹、斑馬、長(zhǎng)頸鹿、企鵝、鴕鳥和信天翁。 2、建立識(shí)別七種動(dòng)物識(shí)別系統(tǒng)的規(guī)則 3、選定編程語(yǔ)言并確定綜合數(shù)據(jù)庫(kù)和規(guī)則庫(kù)結(jié)構(gòu)（1）選用C語(yǔ)言作為編程語(yǔ)言 （2）綜合數(shù)據(jù)庫(kù)的建立（3）規(guī)則庫(kù)的建立 四、程序源代碼 #include { int count;char pre[255];char back[255];int mark;};void check();RULES r[100] = { { 1,“有毛發(fā)”,“哺乳動(dòng)物”,0 }, { 1,“有奶”,“哺乳動(dòng)物”,0 }, { 1,“有羽毛”,“鳥”,0 }, { 2,“會(huì)飛&下蛋&”,“鳥”,0 }, { 1,“吃肉”,“食肉動(dòng)物”,0 }，//所有規(guī)則靜態(tài)數(shù)據(jù)庫(kù) { 3,“有鋒利的牙齒&有爪&眼睛盯著前方&”,“食肉動(dòng)物”,0 }, { 2,“哺乳動(dòng)物&有蹄&”,“有蹄類哺乳動(dòng)物”,0 }, { 2,“哺乳動(dòng)物&反芻&”,“有偶蹄類哺乳動(dòng)物”,0 }, { 4,“哺乳動(dòng)物&食肉動(dòng)物&黃褐色&有暗斑&”,“金錢豹”,0 }, { 4,“哺乳動(dòng)物&食肉動(dòng)物&黃褐色&黑色條紋&”,“老虎”,0 }, { 4,“有蹄類哺乳動(dòng)物&有長(zhǎng)脖子&有長(zhǎng)腿&有暗斑&”,“長(zhǎng)頸鹿”,0 }, { 2,“有蹄類哺乳動(dòng)物&黑條紋&”,“斑馬”,0 }, { 5,“鳥&不會(huì)飛&有長(zhǎng)脖子&有長(zhǎng)腿&黑白色&”,“鴕鳥”,0 }, { 4,“鳥&不會(huì)飛&會(huì)游泳&黑白色&”,“企鵝”,0 }, { 2,“鳥&會(huì)飛&”,“信天翁”,0 }, { 1,“反芻”,“哺乳動(dòng)物”,0 } };int number;int m;int cat = 15;int a;int length;void input(){ //輸入的事實(shí)長(zhǎng)度 string f[255]; //輸入的事實(shí)數(shù)組 while(1){ cat++;cout << “number” << endl;cin >> r[cat].count;cout << “輸入事實(shí)，兩種以上的事實(shí)請(qǐng)?jiān)诿總€(gè)事實(shí)后加上‘&’符號(hào)” << endl;cin >> r[cat].pre;cout << “輸入結(jié)果” << endl;cin >> r[cat].back;r[cat].mark = 0;while(1){ cout << “輸入“1”繼續(xù)添加規(guī)則,輸入“2”查看規(guī)則庫(kù)” << endl;int p;cin >> p;if(p == 1){ } else { if(p == 2){ input(); } } check();else { } cout << “輸入錯(cuò)誤，重新輸入” << endl;} } void delate(){ } cout << “輸入要?jiǎng)h除的條數(shù)” << 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 << “請(qǐng)輸入棋子的坐標(biāo)xy: ”; }; } else { } cout << “非法輸入！”;goto L1;int Tic::s_count = 0;//初始化棋盤狀態(tài)節(jié)點(diǎn)總數(shù)，剛開始置為 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 << “計(jì)算機(jī)走棋” << endl;PrintQP();if(IsWin(States[0])== 1){ } else if(IsWin(States[0])==-1){ } return false; cout << “抱歉你輸了，計(jì)算機(jī)獲勝！” << endl;return true;cout << “恭喜您獲勝！” << endl;return true; };} void main(){ cout << “****項(xiàng)目名稱：一字棋游戲的實(shí)現(xiàn)****” << endl;cout << “****班 級(jí)：智 能 1 5 0 1 ****” << endl;cout << “****姓 名：劉 少 鵬****” << endl;cout << “****學(xué) 號(hào)：0 6 1 5 3 0 3 4 ****” << endl;cout << “****說 明：-1代表人落子位置,1代表電腦落子位置,0代表該位置無棋子 ****” << endl; system(“title #子棋智能小游戲”);system(“color A2”);char IsFirst;bool IsFinish;cout << “若您為先手，請(qǐng)輸入'Y'！反之，請(qǐng)輸入'N':” << endl;cin >> IsFirst;demo *p = new demo();p->init();cout << “棋盤的初始狀態(tài):” << 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、實(shí)驗(yàn)運(yùn)行結(jié)果截圖 4、實(shí)驗(yàn)心得 本次實(shí)驗(yàn)，我通過學(xué)習(xí)用VC編程語(yǔ)言設(shè)計(jì)簡(jiǎn)單的博弈游戲，從而理解和掌握博弈樹的啟發(fā)式搜索過程，熟悉博弈中兩種最基本的搜索方法——極大極小過程和???過程。并且將這種思想通過代碼表現(xiàn)出來。 本次實(shí)驗(yàn)我最大的收獲不僅僅是學(xué)到了課本上的知識(shí)，更是學(xué)會(huì)了如何主動(dòng)的求解問題的答案。實(shí)驗(yàn)中我遇到了許多困難，不僅僅是有關(guān)編程算法方面的，還有一些代碼邏輯流程的設(shè)計(jì)。這些困難我通過上網(wǎng)和去圖書館查找資料或者向同學(xué)請(qǐng)教等方式，逐一解決了困難，我收獲良多。 人工智能課內(nèi)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)6：子句集消解實(shí)驗(yàn) 學(xué) 院： 自動(dòng)化學(xué)院 班 級(jí)： 智能1501 姓 名： 劉少鵬（33）學(xué) 號(hào)： 06153034 日 期： 2017-05-8 10:15-12:00 實(shí)驗(yàn)6子句集消解實(shí)驗(yàn) 一、實(shí)驗(yàn)?zāi)康?/p> （1）熟悉子句集化簡(jiǎn)的九個(gè)步驟； （2）理解消解規(guī)則，能把任意謂詞公式轉(zhuǎn)換成子句集。 二、編程環(huán)境 Visual Studio 2017 三、實(shí)驗(yàn)原理 在謂詞邏輯中，任何一個(gè)謂詞公式都可以通過應(yīng)用等價(jià)關(guān)系及推理規(guī)則化成相應(yīng)的子句集。 其化簡(jiǎn)步驟如下： (1)消去連接詞“→”和“?” 反復(fù)使用如下等價(jià)公式： P→Q ?﹁ P∨Q P?Q ?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。(2)減少否定符號(hào)的轄域 反復(fù)使用雙重否定率 ﹁(﹁P)? P 摩根定律 ﹁(P∧Q)?﹁P∨﹁Q ﹁(P∨Q)?﹁P∧﹁Q 量詞轉(zhuǎn)換率 ﹁(?x)P(x)?(?x)﹁P(x) ﹁(?x)P(x)?(?x)￢P(x)將每個(gè)否定符號(hào)“﹁”移到僅靠謂詞的位置，使得每個(gè)否定符號(hào)最多只作用于一個(gè)謂詞上。 (3)對(duì)變?cè)獦?biāo)準(zhǔn)化 在一個(gè)量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變?cè)坑昧硗庖粋€(gè)沒有出現(xiàn)過的任意變?cè)?，使不同量詞約束的變?cè)胁煌拿帧?/p> (4)化為前束范式 化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動(dòng)時(shí)不能改變其相對(duì)順序。 (5)消去存在量詞 (6)化為Skolem標(biāo)準(zhǔn)形 對(duì)上述前束范式的母式應(yīng)用以下等價(jià)關(guān)系 P∨(Q∧R)?(P∨Q)∧(P∨R)(7)消去全稱量詞(8)消去合取詞 在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個(gè)元素都是一個(gè)子句。 (9)更換變量名稱 對(duì)子句集中的某些變量重新命名，使任意兩個(gè)子句中不出現(xiàn)相同的變量名。 四、實(shí)驗(yàn)結(jié)果及代碼 //化簡(jiǎn)子句集的九步法演示 //作者:劉少鵬 //時(shí)間:2017.5 #include void initString(string &ini);//初始化 string del_inlclue(string temp);//消去蘊(yùn)涵符號(hào) string dec_neg_rand(string temp);//減少否定符號(hào)的轄域 string standard_var(string temp);//對(duì)變量標(biāo)準(zhǔn)化 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);//消去連接符號(hào)合取% string change_name(string temp);//更換變量名稱 //輔助函數(shù)定義 bool isAlbum(char temp);//是字母 string del_null_bracket(string temp);//刪除多余的括號(hào) string del_blank(string temp);//刪除多余的空格 void checkLegal(string temp);//檢查合法性 char numAfectChar(int temp);//數(shù)字顯示為字符 //主函數(shù) 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 《人工智能》實(shí)驗(yàn)一題目 實(shí)驗(yàn)一 啟發(fā)式搜索算法 1.實(shí)驗(yàn)內(nèi)容： 使用啟發(fā)式搜索算法求解8數(shù)碼問題。 ⑴ 編制程序?qū)崿F(xiàn)求解8數(shù)碼問題A?算法，采用估價(jià)函數(shù) ??w?n?，f?n??d?n???pn????其中：d?n?是搜索樹中結(jié)點(diǎn)n的深度；w?n?為結(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)；p?n?為結(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中每個(gè)棋子與其目標(biāo)位置之間的距離總和。 ⑵ 分析上述⑴中兩種估價(jià)函數(shù)求解8數(shù)碼問題的效率差別，給出一個(gè)是p?n?的上界的h?n?的定義，并測(cè)試使用該估價(jià)函數(shù)是否使算法失去可采納性。 2.實(shí)驗(yàn)?zāi)康?/p> 熟練掌握啟發(fā)式搜索A算法及其可采納性。3.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) 該搜索為一個(gè)搜索樹。為了簡(jiǎn)化問題，搜索樹節(jié)點(diǎn)設(shè)計(jì)如下： typedef struct Node//棋盤 {//節(jié)點(diǎn)結(jié)構(gòu)體 int data[9];double f,g;struct Node * parent;//父節(jié)點(diǎn) }Node,*Lnode;int data[9];數(shù)碼數(shù)組：記錄棋局?jǐn)?shù)碼擺放狀態(tài)。struct Chess * Parent;父節(jié)點(diǎn)：指向父親節(jié)點(diǎn)。下一步可以通過啟發(fā)搜索算法構(gòu)造搜索樹。 1、局部搜索樹樣例： ? 2、搜索過程 搜索采用廣度搜索方式，利用待處理隊(duì)列輔助，逐層搜索（跳過劣質(zhì)節(jié)點(diǎn)）。搜索過程如下： （1）、把原棋盤壓入隊(duì)列； （2）、從棋盤取出一個(gè)節(jié)點(diǎn)； （3）、判斷棋盤估價(jià)值，為零則表示搜索完成，退出搜索； （4）、擴(kuò)展子節(jié)點(diǎn)，即從上下左右四個(gè)方向移動(dòng)棋盤，生成相應(yīng)子棋盤； （5）、對(duì)子節(jié)點(diǎn)作評(píng)估，是否為優(yōu)越節(jié)點(diǎn)（子節(jié)點(diǎn)估價(jià)值小于或等于父節(jié)點(diǎn)則為優(yōu)越節(jié)點(diǎn)），是則把子棋盤壓入隊(duì)列，否則拋棄； （5）、跳到步驟（2）； 3、算法的評(píng)價(jià) 完全能解決簡(jiǎn)單的八數(shù)碼問題，但對(duì)于復(fù)雜的八數(shù)碼問題還是無能為力?，F(xiàn)存在的一些優(yōu)缺點(diǎn)。 1、可以改變數(shù)碼規(guī)模（N），來擴(kuò)展成N*N的棋盤，即擴(kuò)展為N數(shù)碼問題的求解過程。 2、內(nèi)存泄漏。由于采用倒鏈表的搜索樹結(jié)構(gòu)，簡(jiǎn)化了數(shù)據(jù)結(jié)構(gòu)，但有部分被拋棄節(jié)點(diǎn)的內(nèi)存沒有很好的處理，所以會(huì)造成內(nèi)存泄漏； 3、采用了屏蔽方向，有效防止往回搜索（節(jié)點(diǎn)的回推），但沒能有效防止循環(huán)搜索，所以不能應(yīng)用于復(fù)雜度較大的八數(shù)碼問題； 源碼： #include typedef struct Node {//節(jié)點(diǎn)結(jié)構(gòu)體 int data[9];double f,g;struct Node * parent;}Node,*Lnode; typedef struct Stack {//OPEN CLOSED 表結(jié)構(gòu)體 Node * npoint;struct Stack * next;}Stack,* Lstack; Node * Minf(Lstack * Open){//選取OPEN表上f值最小的節(jié)點(diǎn)，返回該節(jié)點(diǎn)地址 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){//判斷節(jié)點(diǎn)是否相等，相等，不相等 for(int i = 0;i < 9;i ++) if(suc->data[i]!= goal->data[i])return 0; return 1;} Node * Belong(Node * suc,Lstack * list){//判斷節(jié)點(diǎn)是否屬于OPEN表或CLOSED表，是則返回節(jié)點(diǎn)地址，否則返回空地址 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){//把節(jié)點(diǎn)放入OPEN 或CLOSED 表中 Stack * temp;temp =(Stack *)malloc(sizeof(Stack));temp->npoint = suc;temp->next =(*list)->next;(*list)->next = temp;} ///////////////計(jì)算f值部分-開始////////////////////////////// double Fvalue(Node suc, Node goal, int m){//計(jì)算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){//計(jì)算錯(cuò)位個(gè)數(shù) 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){//計(jì)算方格的錯(cuò)位距離 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));} ///////////////計(jì)算f值部分-結(jié)束////////////////////////////// ///////////////////////擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)-開始///////////////// int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,int m){//判斷子節(jié)點(diǎn)是否屬于OPEN或CLOSED表并作出相應(yīng)的處理 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){//判斷空格可否向該方向移動(dòng)，，表示空格向上向下向左向右移 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){//擴(kuò)展child節(jié)點(diǎn)的字節(jié)點(diǎn)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){//擴(kuò)展后繼節(jié)點(diǎn)總函數(shù) int i;Node * child;for(i = 0;i < 4;i++){ if(Canspread(**suc, i+1)) //判斷某個(gè)方向上的子節(jié)點(diǎn)可否擴(kuò)展 { child =(Node *)malloc(sizeof(Node)); //擴(kuò)展子節(jié)點(diǎn) child->g =(*suc)->g +1; //算子節(jié)點(diǎn)的g值 child->parent =(*suc); //子節(jié)點(diǎn)父指針指向父節(jié)點(diǎn) Spreadchild(child, i); //向該方向移動(dòng)空格生成子節(jié)點(diǎn) if(BelongProgram(&child, Open, Closed, goal, m))// 判斷子節(jié)點(diǎn)是否屬于OPEN或CLOSED表并作出相應(yīng)的處理 free(child); } } } ///////////////////////擴(kuò)展后繼節(jié)點(diǎn)部分的函數(shù)-結(jié)束////////////////////////////////// Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, int m){//總執(zhí)行函數(shù) while(1){ if((*Open)->next == NULL)return NULL; //判斷OPEN表是否為空，為空則失敗退出 Node * minf = Minf(Open); //從OPEN表中取出f值最小的節(jié)點(diǎn) Putinto(minf, Closed); //將節(jié)點(diǎn)放入CLOSED表中 if(Equal(minf, *goal))return minf; //如果當(dāng)前節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則成功退出 Spread(&minf, Open, Closed, **goal, m); //當(dāng)前節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)時(shí)擴(kuò)展當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) } } int Shownum(Node * result){//遞歸顯示從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)的移動(dòng)方法 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(“含有非法字符或數(shù)字!n請(qǐng)重新輸入:n”); else if(flag ==-2)printf(“輸入的數(shù)字有重復(fù)!n請(qǐng)重新輸入:n”); } else if(i < 9)printf(“輸入的有效數(shù)字不夠!n請(qǐng)重新輸入:n”); i = 0; flag = 0; } } } int meassure(Lstack s){ int k=0;while((s->next)!=NULL){ k++; s=s->next;} return k;} void main(){//主函數(shù) //初始操作，建立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; //初始狀態(tài)節(jié)點(diǎn) org->f =1;org->g =1; Node * goal =(Node *)malloc(sizeof(Node)); //目標(biāo)狀態(tài)節(jié)點(diǎn) Node * result;int m;char c;int k; printf(“=================================n”);printf(“說明:狀態(tài)矩陣由0-8 九個(gè)數(shù)字表示,n請(qǐng)依次按照九宮格上的行列順序輸入,每個(gè)數(shù)字間用空格隔開。n”); printf(“=================================n”);printf(“請(qǐng)輸入初始狀態(tài)(0-8 9個(gè)數(shù)字以空格隔開回車表示輸入結(jié)束):n”);Checkinput(org);printf(“請(qǐng)輸入目標(biāo)狀態(tài)(0-8 9個(gè)數(shù)字以空格隔開回車表示輸入結(jié)束):n”);Checkinput(goal);if(Canslove(org, goal)){//A*算法開始，先將初始狀態(tài)放入OPEN表 printf(“請(qǐng)選擇：1.按w(n)搜索 2.按p(n)搜索 n”); scanf(“%d”,&m); while((c = getchar())!= 10); printf(“搜索中，請(qǐng)耐心等待(如果您覺得時(shí)間太久請(qǐng)重新執(zhí)行程序并輸入更快的速度,默認(rèn)值為)......n”); Putinto(org,&Open); result = Process(&org, &goal, &Open, &Closed, m);//進(jìn)行剩余的操作 printf(“總步數(shù):%d”,Shownum(result)-1); printf(“n”); k=meassure(Closed); printf(“擴(kuò)展節(jié)點(diǎn)數(shù)：n”); printf(“%dn”,k); printf(“Press Enter key to exit!”); while((c = getchar())!= 10);} else printf(“程序認(rèn)定該起始狀態(tài)無法道達(dá)目標(biāo)狀態(tài)!n”);}第二篇：人工智能_實(shí)驗(yàn)報(bào)告
第三篇：遺傳算法求解TSP問題實(shí)驗(yàn)報(bào)告
第四篇：人工智能實(shí)驗(yàn)報(bào)告
第五篇：人工智能實(shí)驗(yàn)報(bào)告-八數(shù)碼
點(diǎn)擊咨詢 