地图着色实训报告
目录
1 课题需求描述 ........................................................................................................... 2
2 总体功能与数据结构设计 ....................................................................................... 2
2.1总体功能结构.................................................................................................................... 2
2.2数据结构设计.................................................................................................................... 3
3 算法设计和程序设计 ............................................................................................... 3
3.1算法设计 ........................................................................................................................... 3
3.1.1回溯法.................................................................................................................... 3
3.1.2贪心法.................................................................................................................... 6
3.2程序设计 ........................................................................................................................... 6
3.2.1调用回溯法,并判断着色方案是否可行 ............................................................ 6
3.2.2调用贪心法,对地图进行着色,并测试当前方案是否可行 ............................ 8
3.2.3在着色方案可行的情况下,换一种颜色着色,找出所有可行方案 ................ 9
3.2.4主菜单的设计...................................................................................................... 10
3.2.5二级菜单的设计 .................................................................................................. 11
3.2.6对菜单的使用及对算法用时的计时 .................................................................. 11
4 调试与测试 ............................................................................................................. 14
5 设计总结 ................................................................................................................. 17
5.1收获 ................................................................................................................................. 17
5.2存在问题 ......................................................................................................................... 18
6参考文献 .................................................................................................................. 19
1
1 课题需求描述
1.1地图着色问题
设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少
地图着色问题是一个抽象的图形学问题,用程序实现对各个区域进行着色,并且相邻省所用的颜色不同,同时保证颜色的总数最少,如何将程序所需要的功能模拟着色在计算机中编程实现。
地图可以抽象为一个图,可以用邻接矩阵来进行模拟:对于每一个地图,我们可以把每一个区看作一个点,而区与区之间的邻接关系看作点与点之间的连线。从而将地图抽象为一个图,然后就可以用邻接矩阵抽象。相应的顶点为0,则表示两点邻接,否则,就不邻接,为1。该程序用两种方法进行着色,分别是回溯法和贪心法。
2 总体功能与数据结构设计
由于中国的省份较多,各省连接关系太多,所以程序只给出简单的测试数据,来测试该程序的功能。程序对给定的程序进行着色,做到最多只用四种颜色进行着色,使得相邻省的颜色不同,并且将所有的着色可能都例举出来了。对于地图得到着色,我用了两种算法,分别是回溯法和贪心法。并且对他们的执行进行计时,比较他们的时间复杂度。
主要叙述:本课题设计的总体功能结构、数据结构设计。
2.1总体功能结构
2
2.2数据结构设计
void menu(); //主菜单
void menu2(); //菜单用于选择算法
void aboutjx(); //关于地图的说明
void ljjz() //输出地图的邻接矩阵
void huisu(int n,int m,int c[][12]) //调用回溯算法着色
void tx(int map[N][N],int sum,int current) //调用贪心法着色 int main() //输出主菜单,选择执行过程,对程序的调用
3 算法设计和程序设计
3.1算法设计
3.1.1回溯法
3
本程序采用回溯法进行着色。当t=1时,对当前第t个顶点开始着色:若tn,则已求得一个解,输出着色方案即可。否则,依次对顶点t着色1-m, 若t与所有其它相邻顶点无颜色冲突,则继续为下一顶点着色;否则,回溯,测试上一颜色。回溯法的主要就是选择各种颜色,直到把此点着完色为止。
1.将数组color[n]初始化为0;
2.k=1;
3.while (k=1)
3.1 依次考察每一种颜色,若顶点k的着色与其他顶点的着色不发生冲突,则转步骤3.2;否则,搜索下一个颜色;
3.2 若顶点已全部着色,则输出数组color[n],返回;
3.3 否则,
3.3.1 若顶点k是一个合法着色,则k=k+1,转步骤3处理下一个顶点;
3.3.2 否则,重置顶点k的着色情况,k=k-1,转步骤3
4
3.1.2贪心法
选择一种颜色,以任意顶点作为开始顶点,依次考察图中的未被着色的每个顶点,如果一个顶点可以用颜色1着色,换言之,该顶点的邻接点都还未被着色,则用颜色1为该顶点着色,当没有顶点能以这种颜色着色时,选择颜色2和一个未被着色的顶点作为开始顶点,用第二种颜色为尽可能多的顶点着色,如果还有未着色的顶点,则选取颜色3并为尽可能多的顶点着色,依此类推,直到所有顶点都着上颜色。贪心法就是选择一种颜色,最大化的将图中的各点都用这种颜色着上。
1.color[1]=1; //顶点1着颜色1
2.for (i=2; i i++) //其他所有顶点置未着色状态
color[i]=0;
3.k=0;
4.循环直到所有顶点均着色
4.1 k++; //取下一个颜色
4.2 for (i=2; i i++) //用颜色k为尽量多的顶点着色
4.2.1 若顶点i已着色,则转步骤4.2,考虑下一个顶点;
4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突,
则color[i]=k;
5.输出k;
3.2程序设计
3.2.1调用回溯法,并判断着色方案是否可行
bool ok(int k,int c[][12]) //判断顶点k的着色是否发生冲突
{
int i;
for(i=1;ii++)
{
if(c[k][i]==1color[i]==color[k])
6
return 0;
}
return 1;
}
void huisu(int n,int m,int c[][12]) {
int i,k;
for(i=1;ii++)
color[i]=0;
k=1;
while(k=1)
{
color[k]=color[k]+1; while(color[k]=m) if(ok(k,c)) break; else color[k]=color[k]+1; //搜索下一个颜色 if(color[k]k==n) { for(i=1;ii++) printf(%d ,color[i]); printf(n hsjs++; } else if(color[k]n) k=k+1; //处理下一个顶点 else { color[k]=0;
7
k=k-1;//回溯 }
}
}
3.2.2调用贪心法,对地图进行着色,并测试当前方案是否可行
int yes(int map[N][N], int current)
{
int j;
for(j = 1; j current; j++)
if ( (map[current][j] == 1) (color[j] == color[current]) ) return 0;/*城市相邻且颜色相同*/
return 1;
}
/*从current开始标记,sum为总的地图上的11市,color[N]为标记颜色*/
void tx(int map[N][N],int sum,int current)
{
int i; if (current =sum) { for(i=1;ii++)/*测试每种颜色*/ { color[current]=i;/*尝试着色*/
if( yes(map, current) )/*若尝试成功*/
{
tx(map,sum,current+1);/*检查下一个城市*/ return;
} }
8
} } Print_Color(map,1) ;
3.2.3在着色方案可行的情况下,换一种颜色着色,找出所有可行方案
int Same_Color(int map[N][N],int n)
{
int i ;
for(i=0;ii++) // 分别与前面已经着色的几块比较
if(map[n][i]==1color[i]==color[n])// 相邻并且颜色一样,则不满足
{
}
void Print_Color( int map[N][N],int m)
{
int i=0,j=0; for(i=1;ii++) // 尝试更换颜色 { color[m]=i; if(Same_Color(map,m)==0) // 新的颜色不与前面冲突,颜色满足 { if(m==N-1) // 到最后一个行政区域,递归出口 { for(j=0;j j++) // 遍历数组Color[],显示所有行政 } return 0; // 没有冲突,该颜色满足,返回0 return 1; // 与前面颜色有冲突,返回 1,表示该颜色不满足 区域颜色,新的方案!
{ switch(color[j])
9
} } } } } { case 1:printf(1,break; case 2:printf(2,break; case 3:printf(3,break; case 4:printf(4,break; } printf(n txjs++;// 方案加 1 else Print_Color(map,m+1) ; // 下一个行政区域
3.2.4主菜单的设计
void menu()
{
printf(〓〓〓〓〓〓〓〓〓〓〓欢迎使用地图着色系统软件!〓〓〓
〓〓〓〓〓〓〓n
printf(〓3 3 ----1.关于本软件的说明---- 〓n
printf(〓 3 ----2.地图的邻接矩阵---- 3 3〓n
printf(〓 3 ----3.地图的着色---- 3 〓n
printf(〓 ----4.关于本软件---- 3 〓n
10
printf(〓〓〓〓〓〓〓〓〓〓〓〓5.退出系统||||〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓n
}
3.2.5二级菜单的设计
void menu2()
{
printf(〓〓〓〓〓〓〓〓〓〓〓欢迎使用地图着色系统软件!〓〓〓printf( 3请选择服务:n 〓〓〓〓〓〓〓n
printf(〓3 3 ----1.回溯法着色---- 3 3 〓n
printf(〓 3 ----2.贪心法着色---- 3 〓n
printf(〓 3 ----3.返回上一级---- 3 〓n
printf(〓〓〓〓〓〓〓〓〓〓〓〓4.退出系统||||〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓n
}
3.2.6对菜单的使用及对算法用时的计时
L:menu();
while(cinn) { switch(n) { case 1: system(clsaboutmap();break; case 2:system(clsljjz(); break;//输出地图的邻接矩阵; case 3: system(cls printf( 3请选择服务:n
11
menu2(); while(cinp) { switch(p) { case 1: system(cls start=clock();//获取算法开始时间 huisu(11,4,map); printf(n printf(共有%d种着色方案n,hsjs); printf((1代表红色,2代表蓝色,3代表绿色,4代表黄色)n
finish=clock();//获取算法结束时间
timeStandard=(double)(finish-start)/CLOCKS_PER_SEC;//计算时间差
printf(n 回溯算法的运行时间
为:%fsnn,timeStandard);
menu2(); break; case 2: system(cls start=clock(); tx(map,11,1); printf(n printf(共有%d种着色方案n,txjs); printf((1代表红色,2代表蓝色,3代表绿色,4代表黄色)n
finish=clock();//获取算法结束时间 12
timeStandard=(double)(finish-start)/CLOCKS_PER_SEC;//计算时间差
printf(n 贪心算法的运行时间
为:%fsnn,timeStandard);
menu2(); break; system(clsgoto L;break; case 3: case 4: system(cls cout感谢您的使用,再见~!n exit(1);break;
} } system(pause system(cls menu(); default : coutInput Error! } }break; case 4: system(clsaboutme();break; case 5: cout感谢您的使用,再见~!n exit(1); default : coutInput Error!
13
4 调试与测试
进入主菜单见面
关于该程序的说明
14
输出地图的邻接矩阵
二级菜单,用于选择算法
输入1,选择回溯算法。
15
用回溯法着色得到的着色方案和用时
输入2,选择贪心算法。
用贪心法着色得到的着色方案和用时
16
退出系统
5 设计总结
5.1收获
本次算法设计时间是为期一个星期,然而经过一个星期的算法设计上机实验操作,而我所选择的设计题目是“地图着色问题求解”。最开始我都不了解什么是地图着色,后来通过在网上查找了大量资料才明白地图着色是基于历史上著名的“四色问题”。图着色问题对于现实生活中也有许多的应用,比如交通管理系统、安排考试、贮藏问题等。
在本次算法设计的过程,每天都是对着电脑不停地分析问题、解决问题、写代码实验。这我认识到理论与实际的差别,虽然我构思的很快,但是在编写和运行的过程中花费了很多的时间,调试的时候经常遇到这样或那样的各种错误包括一些低级错误,然而最终我还是比较顺利的完成了自己所选的课程设计题目。
算法设计课程增强了我的动手能力,思考分析和解决问题的能力,同时也对我们巩固和加深了对数据结构的理解,有关算法的认识有所提高和加深,并
17
也提高综合运用本课程所学知识到实践中的能力。
5.2存在问题
在此程序中,按测试代码来说,其运行时间为6.772s,对于其染色代码模块,即回溯的主要算法而言,由于是递归算法,其空间复杂度为最差为O(n^2),最优的是每一次着色的时候都能着色成功,即选择相应的颜色就能成功,一共需要回溯n次,空间复杂度O(n)。
贪心算法的在测试的时候执行时间为6.993ns,时间比回溯的多,其空间复杂度为O(n),即每一重颜色都需要循环n次才能将所有能着此颜色的点着完。
但是回溯法和贪心算法的性能是比较相似的。在查找资料时,我还发现了有蚁群算法,因为实现较为困难,还具有随机性,我没能完成它的编写。
尽管完成了大部分功能,但是在界面方面有些不足,此程序没有实现根据一个特定的地图,来对其进行着色,并且在地图上的各区域显示染上的颜色,也就是在界面方面还需要改进,未能在界面上具体显示一个地图,或者将其邻接矩阵抽象的无向图在界面上显示,着色结果在无向图中直观的显示。 18
6参考文献
[1] Kyle Loudon.算法精解.机械工业出版社.2012
[2]谭浩强.C++面向对象程序设计[M].北京.清华大学出版社,2006
[3]王晓东.计算机算法设计与分析(第3版)[M].北京.电子工业出版社.2007
[4]Cliff A.Shaffer.数据结构与算法分析(C++版).2013年第三版
[5]朱洪.算法设计和分析[M].上海科学技术文献出版社,1989,162-163.
19
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 鲜活水产品的保鲜与运输方法
- 英文自我介绍
- 面试问题经验总结
- 我的职业生涯规划书
- 【推荐信】计算机专业毕业生推荐信
- 软件开发者面试百问
- 职业生涯规划A
- 2015年校长办公室招聘面试题目
- 【求职信】销售类求职信
- 人力资源主管职务简历说明
- 话务员柔和的力量
- 自荐信
- 微商怎么做?教你让别人主动加你的方法
- 关于易变性职业生涯的思考
- 由2011届校园招聘想到的
- 面试技巧
- 袁真职业规划
- CE_Zeeshan_Ahmed[5]
- CE Zeeshan Ahmed
- 鲜活水产品的科学运输
- 2职业生涯规划设计书 马舟浩
- 为未来插上腾飞的翅膀 2
- 习水是一个美酒之乡
- 最受HR欢迎的简历五大特征
- 个人简历
- 职业生涯规划 童彩吟
- 个人简介
- 租房
- 【推荐信】给水排水工程专业毕业生推荐信
- 【求职信】人力资源求职信
网友关注视频
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
- 外研版英语七年级下册module3 unit2第一课时
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市
- 二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
- 沪教版八年级下册数学练习册一次函数复习题B组(P11)
- 七年级英语下册 上海牛津版 Unit9
- 北师大版小学数学四年级下册第15课小数乘小数一
- 第8课 对称剪纸_第一课时(二等奖)(沪书画版二年级上册)_T3784187
- 二年级下册数学第一课
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
- 外研版英语三起6年级下册(14版)Module3 Unit2
- 8.练习八_第一课时(特等奖)(苏教版三年级上册)_T142692
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 冀教版小学英语四年级下册Lesson2授课视频
- 第12章 圆锥曲线_12.7 抛物线的标准方程_第一课时(特等奖)(沪教版高二下册)_T274713
- 冀教版小学数学二年级下册第二单元《有余数除法的简单应用》
- 人教版二年级下册数学
- 七年级下册外研版英语M8U2reading
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175
- 外研版八年级英语下学期 Module3
- 19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436
- 沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
- 冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》
- 北师大版数学四年级下册3.4包装
- 二年级下册数学第二课
- 精品·同步课程 历史 八年级 上册 第15集 近代科学技术与思想文化
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理