人工智能大作业报告材料.pdf
实用文档人工智能课程大作业人工智能课程大作业基于回溯搜索的地图着色基于回溯搜索的地图着色班级：20110616学号：2011061624姓名：曾江东 2014 2014 年年 1111 月月 2626 号号实用文档摘要摘要：人工智能是 20 世纪 50 年代中期兴起的一门边缘学科。人工智能领域中，地图着色问题是一典型的优化的问题。由它引发的“四色猜想”是全世界的难题，直到 1975 年由三台超高速电子计算机，经过 1200 小时的计算才终于正明了“四色定理”。这是世界上最长的证明。本文并不是想证明，而只是想基于回溯法来给地图着色，求出最少用色。本文着重介绍利用MFC 设计界面来对中国省级地图着色进行演示。计算机视觉是研究为完成在复杂的环境中运动和在复杂的场景中识别物体所需要哪些视觉信息，以及如何从图像中获取这些信息的科学领域。关键词关键词：地图着色；回溯搜索；MFC本组成员本组成员：曾江东，杨星，俞洋本人分工本人分工：本人主要基于回溯搜索算法的代码的编写。1 1 引言引言人，现在社会的发展中心都离不开这个人字，人是发展的本体，人类的自然智能伴随到处都是，本次实验研究什么是人工智能，人工智能又能如何的运用在生活和学习中。人工智能(ArtificialIntelligence)，英文缩写为 AI。它是研究、开发用于模拟、延伸和扩 展 人 的 智 能 的 理 论、方 法、技 术 及 应 用 系 统 的 一 门 新 的 技 术 科 学。人 工 智 能（ArtificialIntelligence，AI）是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，但没有一个统一的定义。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。本次实验研究的是关于人工智能中搜索的功能，实现用回溯法对地图不同地区的着色问题，地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。地图着色的算法比较多，但是切实可行的算法很少，回溯法在地图区域较大，邻接关系复杂的情况下，回溯次数将会大大增多，严重影响了程序执行效率。不过本次作业则是采用修改后的回溯法，在一定的条件下，执行效率还是很高。本次实验是要对中国地图中的省级行政区最多使用四种颜色来进行着色，编程实现回溯算法用于地图自动着色。我负责得是改进的回溯算法的代码的编写。2 2 算法原理与系统设计算法原理与系统设计2.12.1回溯算法原理回溯算法原理要解决地图着色的问题，本文采用的是回溯法。回溯法是一种系统地搜索问题解的搜索算法。回溯法递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。其基本步骤：1.定义一个解空间，它包含问题的解。2.利用适于搜索的方法组织解空间。3.利用深度优先法搜索解空间。4.利用限界函数避免移动到不可能产生解的子空间。而地图着色的问题可以处理为：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。则着色问题变成了对解问题的最优搜索算法的实现。我利用分枝定界法对候选解进行系统检查，能以较高效率的找到最优解。2.22.2详细设计详细设计地图着色功能流程图如图2-1 所示：实用文档开始Colr0=0,i=1,colr=0,pl=nullinext是Pl不空是colr+否Colri=colr结束图 2-1地图颜色确定流程图在窗口上着色时，用到的是广度算法的思想，搜索遍历一个省区域内的所有像素点。实用文档着色是各省渐变着色，感观上能看见是从省中间向边缘扩散。在对一个省进行着色时，用深度优先的算法实现，共用 4 种颜色，分别是红，绿，蓝，黄。每次给当前省份4 种颜色中的一种，然后判断是否合理，如不合理则换另一种颜色值，根据图的4 色定理一定能从 4 种颜色中找到一个合适的颜色，直到当前省份找到合适颜色后，进行下个省份的判断。在着色时，以这个省份的中心点为基准，由环形向外进行着色，采用深度优先搜索算法，并根据标记的二维数组来进行边界检测，以保证着色的准确性。在本次设计中，用到了关于地图信息的两个文件，一个是地图标记点文档，如图2-2 所示。它里边存储的是地图的每个省份的中间点的像素坐标，如“新疆125123”，代表的是新疆在地图中的坐标位置，一共32 个省。另一个是相邻之间的关系的文档，如图2-3 所示。它里边存储的是省与省之间的相邻接关系，比如“1 3”，代表省 1，省 3 相邻。这里的 0 和 1 是根据 node 表中的顺序得来的，0 代表新疆，1 代表西藏。当两个省相临时，他们不能着相同的颜色。程序不要求用户输入，运行程序后自动从文件中读取地图信息，并加载原始地图，出现可操作的可视化界面。图 2-2 地图标记点文件图 2-3 相邻之间的关系文件3 3 系统实现系统实现3-13-1 回溯算法回溯算法我采用的是深度优先搜索算法，它就是把最近刚产生的结点优先扩展，直到达到一定的深度限制。若未找到目标或无法再扩展时，再回溯到另一个结点继续扩展。它类似于树的先根搜索，是树的先根搜索的推广。3-23-2 代码实现代码实现地图涂色用到深度优先搜索算法void CMyDlg:On_Color()/TODO:Add your control notification handler code hereALgraph G;int i,s,d;listnode*p,*q;ifstream ifile(C:地图(邻接表)text2.txt,ios:in);实用文档G.vexnum=32;G.arcnum=68;for(i=1;i=32;i+)G.vexsi.first=NULL;for(i=1;isd;p=new listnode;p-adjvex=d;p-next=G.vexss.first;G.vexss.first=p;q=new listnode;q-adjvex=s;q-next=G.vexsd.first;G.vexsd.first=q;ifstream ifile1(C:地图(邻接表)坐标 1.txt,ios:in);for(i=0;iPi.xPi.y;int j,aMAXVER;int colorMAXVER;color0=1;for(i=0;iMAXVER;i+)ai=0;for(i=1;iMAXVER;i+)colori=1;for(i=1;i=32;i+)int count=1;listnode*p;p=G.vexsi.first;while(p!=NULL)if(iadjvex)p=p-next;elseacount=p-adjvex;实用文档count+;p=p-next;if(count1)int t=1;for(j=1;j=n;j+)int flag=1;for(t=1;tcount;t+)if(j=colorat)flag=0;break;if(flag=1)colori=j;break;for(i=1;i=32;i+)CDC*pdc=GetDC();Color(Pi-1.x,Pi-1.y,ccolori-1,pdc);4 4 实验或测试结果实验或测试结果程序运行后出现如下界面：实用文档图 4-1 地图初始化点击着色后，开始着色：图 4-2 地图着色中实用文档图 4-3 地图着色完成在调试过程中，我们发现地图着色非常缓慢，我们分析是由于我们是对点像素的遍历，而图的范围又非常广，导致遍历速度很慢，程序效率不快。5 5 结论结论在这次利用回溯搜索算法实现中国地图着色的实验中，我负责的是回溯搜索算法的编写，其实基本的回溯算法，是一种系统地搜索问题的解的方法。但是，又怎么利用它实现地图的着色呢？我利用的是将图着色的问题具体化，把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图，这样就可以用到遍历了。虽然在编写代码的时候遇到了很多问题，但是更让人烦躁的是，调试时，程序老是出现错误，这让我们相当沮丧，后来，通过小组成员不断地努力，终于排除所有的问题，程序成功运行，这还是让我们很有成就感的。参考文献参考文献1梁述明，陆忠武四色图着色问题的混沌神经网络解法 J武汉科技大学学报(自然科学版)，2006，(6)：165-1692毛云舟一个实用的地图着色算法J徐州师范大学学报(自然科学版)，1998，(4):17-183佘玉梅，段鹏.人工智能及其应用M.上海交通大学出版社,2007.4吴胜，王书芹.人工智能基础与应用M.电子工业出版社,2007.1.
