人工智能课程设计报告.docx

人工智能课程设计报告班级：191134学号：学生姓名：指导老师：日期： 2015年11月目录第 1 章1罗马利亚度假问题11.1题目内容11.2需求分析11.3设计11.3.1设计思想11.3.2设计表示101.4调试分析101.4.1调试结果与比较101.4.2算法比较与总结111.4.3调试中遇到的问题111.5用户手册121.6测试数据及结果121.7源程序清单12第 2 章13n皇后问题132.1题目内容132.2需求分析132.3设计132.3.1设计思想132.3.2算法代码142.4调试分析162.4.1调试中遇到的问题162.4.2调试截图162.4.3对比和总结192.5用户手册202.6测试数据及测试结果202.7源程序清单20人工智能课程报告第 1 章罗马利亚度假问题1.1 题目内容分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法和a*算法求解“罗马利亚度假问题”。1.2 需求分析本题是简单的路径搜索问题 读入数据 建图，以及相关方法 分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法和a*算法求解路径 打印路径，路径长度和扩展点数 对比扩展点数，对比算法优劣1.3 设计1.3.1 设计思想（1）数据结构设计本软件用的主体数据结构就是有向图。这里我用了有向图的存储结构有两种：邻接矩阵和邻接表。下面是数据结构的声明：（1）邻接矩阵类：#001 class adjmwgraph#002 #003 private:#004seqlist vertices;/顶点顺序表#005wt edgemaxverticesmaxvertices;/边权值数组#006int numofedges;/边的个数#007void depthfirstsearch(const int v, int visited, void visit(vt item);#008void broadfirstsearch(const int v, int visited, void visit(vt item);#009 public:#010adjmwgraph(const int sz = maxvertices);/构造函数#011adjmwgraph(void);/析构函数#012int numofvertices(void)const/取顶点个数#013return vertices.size();#014int numofedges(void)const/取边的个数#015return numofedges;#016vt getvalue(const int v)const;/取顶点数值#017wt getweight(const int v1, const int v2)const;/取边的权值#018void insertvertex(const vt &vertex);/插入顶点#019void insertedge(const int v1, const int v2, wt weight);/插入边#020void deletevertex(const int v);/删除顶点#021void deleteedge(const int v1, const int v2);/删除边#022int getfirstneighbor(const int v)const;/取第一个邻接顶点#023int getnextneighbor(const int v1, const int v2)const;/取下一个邻接顶点#024void depthfirstsearch(void visit(vt item);/深度优先遍历#025void broadfirstsearch(void visit(vt item);/广度优先遍历/增加函数#026int isvertex(vt vertex)const;/*判断顶点vertex是否是有向图g的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1。*/#027int isvertex(int v)const;#028int isedge(int v1,int v2)const;/*判断第v1个顶点到第v2个顶点的边是否是有向图g的边，是则返回1，否则返回0。 */#029int indegree(int v)const;/*在带权有向图g中求第v个顶点的入度*/#030int outdegree(int v)const;/*在带权有向图g中求第v个顶点的出度*/#031int degree(int v)const;/*在带权有向图g中求第v个顶点的度*/#032 ;邻接表的边链表的结点的结构体如下：#001 struct edgelistnode#002 #003int dest;/*与该顶点邻接的邻接顶点的序号*/#004wt weight;/权值#005 edgelistnode *next;/*指向下一条边或弧结点*/#006 edgelistnode(edgelistnode * ptr =null):next(ptr)#007edgelistnode(int d, wt w, edgelistnode * ptr = null):dest(d), weight(w), #008 next(ptr)/构造函数2#009 ;邻接表的顶点的结构体如下：#001 struct vertex#002 #003vt data;/顶点信息#004edgelistnode *adjhead;/*指向第一条依附该顶点的边*/#005vertex(edgelistnode * ptr =null):adjhead(ptr)#006vertex(vt d, edgelistnode * ptr =null):data(d),adjhead(ptr)#007 ;（2）邻接表类：#001 class adjlwgraph#002 #003 private:#004seqlist vertices;/顶点顺序表#005int numofedges;/边数#006#007void depthfirstsearch(const int v, int visited, void visit(vt#008 vertex);/私有的深度优先搜索函数#009void broadfirstsearch(const int v, int visited, void visit(vt#010 vertex);/私有的广度优先搜索函数#011 public:#012adjlwgraph(const int sz = maxvertices);/构造函数#013adjlwgraph(void);/析构函数#014#015int numofvertices(void)const/返回顶点数目#016return vertices.size();#017int numofedges(void)const/返回边数目#018return numofedges;#019vt getvalue(const int i)const;/返回第i个顶点的信息#020wt getweight(const int v1, const int v2)const;/返回第v1个顶点到第v2个#021 顶点的边的权值#022void insertvertex(const vt &vertex);/在图的邻接表中插入值为vertex的顶点#023void insertedge(const int v1, const int v2, wt weight);/在图的邻接表中#024 插入第v1个顶点到第v2个顶点、权值为weight的边#025void deletevertex(const int v);/在图的邻接表中删除第v个顶点#026void deleteedge(const int v1, const int v2);/在图的邻接表中删除第v1个顶#027 点到第v2个顶点的#028int getfirstneighbor(const int v);/返回第v个顶点的第一个邻接顶点#029int getnextneighbor(const int v1, const int v2);/返回第v个顶点的v2#030 个顶点之后的下一个邻接顶点#031void depthfirstsearch(void visit(vt vertex);/公有的深度优先搜索函数#032void broadfirstsearch(void visit(vt vertex);/公有的广度优先搜索函数#033 /补充六个函数#034int isvertex(vt vertex)const;/*判断顶点vertex是否是有向图g的顶点，#035 是则返回顶点在顶点顺序表中的序号，否则返回-1。*/#036int isvertex(int v)const;/*判断有向图g是否有第i个顶点，有则返回#037 1，没有则返回0。*/#038int isedge(int v1,int v2)const;/*判断第v1个顶点到第v2个顶点的边是否是#039 有向图g的边，是则返回1，否则返回0。 */#040int indegree(int v)const;/*在带权有向图g中求第v个顶点的入度*/#041int outdegree(int v)const;/*在带权有向图g中求第v个顶点的出度*/#042int degree(int v)const;/*在带权有向图g中求第v个顶点的度*/#043 邻接表和邻接矩阵示意图如下：（2）算法设计要找出城市之间的路径首先需要将城市之间的路径图画出，就这个题目我设计了两种构造图的方法，方法设计如下：#001 struct rowcolweight#002 #003int row;/行下标#004int col;/列下标#005wt weight;/权值#006 ;#007 void creatgraph(adjmwgraph &g, vt v, int n, rowcolweight e,int e)#008 /在图g中插入n个顶点v和e条边e#009 #010/在图g中插入n个顶点#011for(int i = 0; i n; i+) #012g.insertvertex(vi);#013/在图g中插入e条边#014for(int k = 0; k e; k+) #015g.insertedge(ek.row, ek.col, ek.weight);#016 #017 void creatgraph(adjlwgraph &g, vt v, int n, rowcolweight e,int e)#018 /在图g中插入n个顶点v和e条边e#019 #020/在图g中插入n个顶点#021for(int i = 0; i n; i+) #022g.insertvertex(vi);#023/在图g中插入e条边#024for(int k = 0; k e; k+) #025g.insertedge(ek.row, ek.col, ek.weight);#026 ;（3）算法思想l 代价一致宽度优先从根节点开始将扩展点的子节点入优先队列，选择最小的路径的子节点作为下一个扩展点重复，直到队列为空或找到目标节点为止#1 void dijkstra(graphtype &g, int v0,int v1,wt distance, int path,int &expand) /最短路径算法#2 #3 int n = g.numofvertices();#4 int *s = new intn;#5 wt mindis;#6 int i, j, u;#7 int sumexpand = 0;#8 for (i = 0; i n; i+)#9 #10 distancei = g.getweight(v0, i);#11 si = 0;#12 if (i != v0&distancei maxweight)#13 pathi = v0;#14 else pathi = -1;#15 #16 sv0 = 1;#17 for (i = 1; i n; i+)#18 #19 mindis = maxweight;#20 for (j = 0; j n; j+)#21 #22 if (sj = 0 & distancej mindis)#23 #24 u = j;#25 mindis = distancej;#26 #27 #28 if (mindis = maxweight|u=v1)return;#29#30 su = 1;#31 for (j = 0; j n; j+)#32 if (sj = 0 & g.getweight(u, j) maxweight! distanceu + g.getweight(u, j) distancej)#34 #35 sumexpand+;#36 distancej = distanceu + g.getweight(u, j);#37 pathj = u;#38 #39 expand = sumexpand;#40 #41 l 有限制的深度搜索从根节点开始若没有超过搜索层数将扩展点的子节点入栈，选择栈顶元素作为下一个扩展点重复，直到栈为空或找到目标节点为止#1 void non_recdfs(adjmwgraph &g, vt a, vt b, vector &path,int *expand)#2 #3#4 int tempa = g.isvertex(a);#5 int tempb = g.isvertex(b);#6 int n = g.numofvertices();#7 int e = g.numofedges();#8 int sumexpand = 0;/扩展节点总数#9 seqstack s;/节点栈#10 int *visited = new intn;/访问节点标记数组#11 int tempw; /记录下一个访问节点#12 memset(visited, 0, n*sizeof(int);#13 s.push(tempa);#14 visitedtempa = 1;#15 while (true)#16 #17 int temptop = s.gettop();#18#19 tempw = g.getfirstneighbor(temptop);#20 while (visitedtempw = 1)#21 #22 tempw = g.getnextneighbor(temptop, tempw);#23 #24 while (tempw = -1)#25 #26 s.pop();#27 temptop = s.gettop();#28#29 tempw = g.getfirstneighbor(temptop);#30 while (visitedtempw = 1)#31 #32 tempw = g.getnextneighbor(temptop, tempw);#33 #34 #35#36 s.push(tempw);#37 sumexpand+;#38 visitedtempw = 1;#39 if (tempw = tempb)break;#40 #41 *expand = sumexpand;#42 if (!s.notempty()#43 #44 std:cout 搜索失败！ endl;#45 #46 else#47 #48 while (s.notempty()#49 #50 int temptop = s.pop();#51 path.push_back(temptop);#52 #53 #54 l 贪婪搜索算法从根节点开始将扩展点的子节点入优先队列，选择最小的启发函数值的子节点作为下一个扩展点重复，直到队列为空或找到目标节点为止#1 void greedy(adjmwgraph &g, vt a, vt b, int h, int path, wt distance,int *expand)#2 #3 int tempa = g.isvertex(a);#4 int tempb = g.isvertex(b);#5 int n = g.numofvertices();#6 int e = g.numofedges();#7 node = new noden;#8 int sumexpand = 0; /扩展节点总数#9 int cur; /当前节点#10 int *visited = new intn;/访问节点标记数组#11 int tempw; /记录下一个访问节点#12 memset(visited, 0, n*sizeof(int);#13 for (int i = 0; i n; i+)#14 distancei = 0;#15 for (int i = 0; i n; i+)#16 #17 nodei.set(i, hi);#18 #19 priority_queue q;#20 q.push(nodetempa);#21 visitedtempa = 1;#22 while (!q.empty()#23 #24 cur = q.top().index;#25 q.pop();#26 sumexpand+;#27 tempw = g.getfirstneighbor(cur);#28 if (visitedtempw = 1)#29 tempw = g.getnextneighbor(cur, tempw);#30#31 while (tempw != -1)#32 #33 /nodetempw.set(tempw, g.getweight(cur, tempw)+nodecur.priority);#34 pathtempw = cur;#35 distancetempw = g.getweight(cur, tempw) + distancecur;#36 if (tempw = tempb) return;#37 q.push(nodetempw);#38 visitedtempw = 1;#39 tempw = g.getnextneighbor(cur, tempw);#40 #41 *expand = sumexpand;#42 #43 #44 l a*搜索算法从根节点开始将扩展点的子节点入优先队列，选择最小的路径与启发函数值之和的子节点作为下一个扩展点重复，直到队列为空或找到目标节点为止void asearch(adjmwgraph &g, vt a, vt b, int h, int path, wt distance, int *expand)int tempa = g.isvertex(a);int tempb = g.isvertex(b);int n = g.numofvertices();int e = g.numofedges();node = new noden;int sumexpand = 0; /扩展节点总数int cur; /当前节点int *visited = new intn;/访问节点标记数组int tempw; /记录下一个访问节点memset(visited, 0, n*sizeof(int);for (int i = 0; i n; i+)distancei = 0;priority_queue q;nodetempa.set(tempa, htempa);q.push(nodetempa);visitedtempa = 1;while (!q.empty()cur = q.top().index;q.pop();sumexpand+;tempw = g.getfirstneighbor(cur);if (visitedtempw = 1)tempw = g.getnextneighbor(cur, tempw);while (tempw != -1&visitedtempw=0)pathtempw = cur;distancetempw = g.getweight(cur, tempw) + distancecur;nodetempw.set(tempw, distancetempw + htempw);if (tempw = tempb) return;q.push(nodetempw);visitedtempw = 1;tempw = g.getnextneighbor(cur, tempw);*expand = sumexpand;1.3.2 设计表示主要的函数:#001 dijkprintload/代价一致的宽度优先#002 non_recdfs/有限制的深度优先#003 greedy/贪婪搜索算法#004 asearch/a*算法1.4 调试分析 1.4.1 调试结果与比较1. 代价一致的宽度优先2. 有限制的深度优先3. 贪婪搜索算法4. a*算法1.4.2 算法比较与总结节点数路径长度效率optimality: completeness: bfs114182noyesdfs 126053nonogreedy24501nonoa*算法34504yesyes1.4.3 调试中遇到的问题在程序运行时，解环复原的时候需要传入std:vector，此时容易出现内存泄漏问题。这个时候需要将std:vector定义为全局变量，并采用引用传值方式销毁std:vector，避免内存泄漏。一开始在建环的时候直接调用了链表的删除函数，导致程序陷入死循环，应直接将后续节点销毁，注意，此处可链表删除完全不同。1.5 用户手册直接运行程序即可，没有用户要操作的地方。1.6 测试数据及结果请看第1.4.1节。1.7 源程序清单adjmwgraph.cppadjwgraphapp.hcreatadjwgraph.hread.cppseqlist.hseqqueue.hseqstack.hgraphmindtest.cpp20第 2 章n皇后问题2.1 题目内容设计目的： 分别用回溯法（递归）、ga算法和csp的最小冲突法求解n皇后问题。设计内容： 1. 输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率，并列表给出结果。2. 比较同一算法在n不相同时的运行时间，分析算法的时间复杂性，并列表给出结果。2.2 需求分析n皇后问题：在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上2.3 设计2.3.1 设计思想（1） 回溯法回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：找到一个可能存在的正确的答案在尝试了所有可能的分步方法后宣告该问题没有答案在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。（2） 遗传算法遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。（3） csp最小冲突法约束满足问题（csp）是一类数学问题，它的定义为一组状态必须满足于若干约束或限制的对象(object)。 cpss表示的是问题中的实体，有限数量、同类型的约束加之于变量之上, 这类问题通过 约束满足 方法解决。csps是人工智能和运筹学 的热门主题, 这是因为它们公式中的规律提供了一个分析和解决很多不相关问题的共同基础。 csps通常表现出高复杂性, 需要结合启发式搜索 和 联合搜索 方法来在合理的时间内解决问题。 布尔可满足性问题 (sat), ,可满足性的理论 (smt)和回答集编程 (asp) 大致可以认为是特定形式的约束满足问题2.3.2 算法代码（1） 回溯法#1 void solve(int rowcurrent, int *&nqueen, int n, int &count)#2 #3 if (count = 0)#4 #5 if (rowcurrent = n) /当前行数触底，即完成了一个矩阵，将它输出#6 #7 count+;#8 return;#9 #10 for (int i = 0; i n; i+)#11 #12 nqueenrowcurrent = i; /row行i列试一试#13 if (check(rowcurrent, nqueen)#14 #15 solve(rowcurrent + 1, nqueen, n, count); /移向下一行#16 #17 #18 #19 （2） 遗传算法#1 void evolution()#2 #3 #4 int i = 0, mate1, mate2;#5 while (ipopsize)#6 #7 mate1 = select();#8 mate2 = select();#9 /coutmate1 mate2endl;#10 crossover(oldpopmate1, oldpopmate2, newpopi, newpopi + 1);#11 mutation(newpopi);#12 newpopi.fitness = fitness_count(newpopi);#13 mutation(newpopi + 1);#14 newpopi + 1.fitness = fitness_count(newpopi + 1);#15 i += 2;#16 #17 本函数为产生新的种群函数，其中 select（）为选择操作，crossover（）为交叉操作（3） csp最小冲突#1 bool adjust_row(int row) #2 int cur_col = rrow;#3 int optimal_col = cur_col;/最佳列号，设置为当前列，然后更新#4 int min_conflict = coloptimal_col + pdiaggetp(row, optimal_col) - 1#5 + cdiaggetc(row, optimal_col) - 1;/对角线冲突数为当前对角线皇后数减一#6 for (int i = 0; i n; i+) /逐个检查第row行的每个位置#7 if (i = cur_col) #8 continue;#9 #10 int conflict = coli + pdiaggetp(row, i) + cdiaggetc(row, i);#11 if (conflict 30时，用回溯法已不能较好的解决n皇后问题（2） 遗传算法遗传算法优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间长，且容易受参数的影响。（3） 最小冲突算法这个算法也不能找到所有解，有可能也要多次初始化，因为有可能从某个初始状态开始，按照最小冲突准则无论怎么调整都达不到终止条件（即没有冲突）。这里的最小冲突准则有点“贪心”的味道，而贪心算法常常达不到最优解。（不过实际实现时发现1次初始化总是能得到解当然