算法设计与分析课程设计报告

《算法设计与分析课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江苏大学计算机学院课程设计报告江苏大学计算机学院课程设计报告课程名称算法设计与分析课程设计实验学期2015至2016学年，第一学期学生姓名卢亮键专业班级软件1301学号3130608012指导教师黄如兵开课系软件工程算法设计与分析课程组制江苏大学计算机学院课程设计报告《算法设计与分析》课程设计报告课程设计题目：江苏省地图染色问题设计时间：一周(1.11-1.17)一、课程设计目的与要求1.课程设计目的：认识回溯法和分支限界法，并用回溯法和分支限界法解决实际问题。2.基本要求：（1）实现回溯法和分支限界法的江苏省地图染色

2、问题，并统计开销。（2）完成染色的最少颜色数目是多少。（3）将几种染色算法集成到一个系统里面，且尽可能有图形界面。二、课程设计内容问题定义：给定江苏省地图，对不同的地级市进行染色，要求任何两个相邻的市之间不可以同色，请计算出最少的颜色数目，同时要求至少用回溯法和分支限界法的算法实现（鼓励实现其他的方法）。三、课程设计设备与环境设备：笔记本电脑或台式电脑环境：（1）C/C++:Visualc++等（2）Java：eclipse等江苏大学计算机学院课程设计报告一、设计正文System.out.println("徐州、宿迁、

3、连云港、淮安、盐城、扬州、泰州、南通、南京、镇江、常州、无锡、苏州13个城市相邻矩阵为：");int[][]map={{0,1,1,0,0,0,0,0,0,0,0,0,0},{1,0,1,1,0,0,0,0,0,0,0,0,0},{1,1,0,1,1,0,0,0,0,0,0,0,0},{0,1,1,0,1,1,0,0,0,0,0,0,0},{0,0,1,1,0,1,1,1,0,0,0,0,0},{0,0,0,1,1,0,1,0,1,1,0,0,0},{0,0,0,0,1,1,0,1,0,1,1,1,1},{0,0,0,

4、0,1,0,1,0,0,0,0,0,1},{0,0,0,0,0,1,0,0,0,1,1,0,0},{0,0,0,0,0,1,1,0,1,0,1,0,0},{0,0,0,0,0,0,1,0,1,1,0,1,0},{0,0,0,0,0,0,1,0,0,0,1,0,1},{0,0,0,0,0,0,1,1,0,0,0,1,0}};map[x][y]表示第x个城市和第y个城市的相邻情况，特殊情况为map[x][x]无意义，其值为0。而约束函数则为两个相邻的城市的染色的颜色互不相同；其中，0表示不相邻；1表示相邻。privatei

5、ntcolors;//最少颜色数目privateint[][]map;//相邻矩阵privatestaticint[]x;//当前的解privatestaticlongsum;//解法种数staticintk=13;//城市个数staticintw=1;//颜色1,2,3,4江苏大学计算机学院课程设计报告回溯法：回溯法就是从当前节点遍历，当前城市染色满足它的约束函数，则继续遍历到下一个城市节点，给以初始颜色；否则，若颜色够用，当前城市染下一种颜色，不然就返回上一个节点，即上一个城市染下一种颜色。如此循环往复，到所有的解

6、空间树都遍历完毕，即为结束。江苏大学计算机学院课程设计报告publiclongmColoring(){backtrack(1);//从第一个根节点开始遍历returnsum;}privatevoidbacktrack(intt){intn=map[0].length;if(t>n){sum++;//print(sum);//如果遍历到第n+1层节点，就说明已成功了一种方法，输出方法并方法数加1}else{for(inti=1;i<=colors;i++){x[t-1]=i;if(ok(t))backtrack(t+1)

7、;//满足约束函数，遍历下一个根节点}}}privatebooleanok(intk)//回溯法约束函数{for(intj=0;j

8、剪去不满足条件的所有子节点intlooper=0;loop:for(intn=0;n