第一篇：人工智能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,xii1n1i1)d(xnx1)
其中，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(xj1j) 本题中具体使用的是期望值方法 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算法，采用估价函数 wn，fndnpn其中：dn是搜索树中结点n的深度；wn为结点n的数据库中错放的棋子个数；pn为结点n的数据库中每个棋子与其目标位置之间的距离总和。 ⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是pn的上界的hn的定义，并测试使用该估价函数是否使算法失去可采纳性。 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问题实验报告
第四篇：人工智能实验报告
第五篇：人工智能实验报告-八数码
点击咨询 