当前位置：搜档网 › 基于回溯法的地图着色

基于回溯法的地图着色

XXXXXXXX

摘要：人工智能是20世纪50年代中期兴起的一门边缘学科[1]。人工智能领域中，地图着色问题是一典型的优化的问题。由它引发的“四色猜想”是全世界的难题，直到1975年由三台超高速电子计算机，经过1200小时的计算才终于正明了“四色定理”。这是世界上最长的正明。本文并不是想证明，而只是想基于回溯法来给地图着色，求出最少用色。本文着重介绍利用MFC设计界面来对地图着色进行演示。计算机视觉是研究为完成在复杂的环境中运动和在复杂的场景中识别物体所需要哪些视觉信息，以及如何从图像中获取这些信息的科学领域[2]。

关键词：地图着色；回溯法；MFC

本组成员：XXXXXXXXX

本人分工：本人承担界面设计，edge文档和node文档的编写。

1 引言

人，现在社会的发展中心都离不开这个人字，人是发展的本体，人类的自然智能伴随到处都是，本次实验研究什么是人工智能，人工智能又能如何的运用在生活和学习中。

人工智能(Artificial Intelligence)，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能（Artificial Intelligence，AI）是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，但没有一个统一的定义。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

本次实验研究的是关于人工智能中搜索的功能，实现用回溯法对地图不同地区的着色问题，地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。地图着色的算法比较多，但是切实可行的算法很少，回溯法在地图区域较大，邻接关系复杂的情况下，回溯次数将会大大增多，严重影响了程序执行效率。不过本次作业则是采用修改后的回溯法，在一定的条件下，执行效率还是很高。

本次实验是要对中国地图中的省级行政区最多使用四种颜色来进行着色，编程实现回溯算法用于地图自动着色。我要实现的是对中国地图着色的界面设计，我利用VS中的MFC来实现界面设计。

2 算法原理与系统设计

2.1 回溯算法原理

要解决地图着色的问题，本文采用的是回溯法。回溯法是一种系统地搜索问题解的搜索算法。回溯法递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

而地图着色的问题可以处理为：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。

2.2 详细设计

地图着色功能流程图如下：

图2-1 确定颜色流程图

在窗口上着色时，用到的是广度算法的思想，搜索遍历一个省区域内的所有像素点。

着色是各省渐变着色，感观上能看见是从省中间向边缘扩散，同时动态的把用到的颜色以饼形图画在地图右边窗口上，并显示当前用色数。

图2-2 重置导出地图流程图

在对一个省进行着色时，用深度优先的算法实现，共用4种颜色，分别是红，绿，蓝，粉。每

次给当前省份4种颜色中的一种，然后判断是否合理，如不合理则换另一种颜色值，根据图的4色定理一定能从4种颜色中找到一个合适的颜色，直到当前省份找到合适颜色后，进行下个省份的判断。在着色时，以这个省份的中心点为基准，由环形向外进行着色，采用深度优先搜索算法，并根据标记的二维数组来进行边界检测，以保证着色的准确性。

图2-3 着色流程图

在本次设计中，用到了关于地图信息的两个文件，一个是node文档，如图2-4所示。它里边存储的是地图的每个省份的中间点的像素坐标，如“新疆149 173”，代表的是新疆在地图中的坐标位置，一共32个省。另一个是edge文档，如图2-5所示。它里边存储的是省与省之间的相邻接关系，比如“0 1 null ”，代表省0与省1相邻。这里的0和1是根据node表中的顺序得来的，0代表新疆，1代表西藏。当两个省相临时，他们不能着相同的颜色。程序不要求用户输入，运行程序后自动从文件中读取地图信息，并加载原始地图，出现可操作的可视化界面。

图2-4 node文件

图2-5 edge文件

3 系统实现

3.1 算法分析

在窗口上着色时，用到的是广度算法的思想，搜索遍历一个省区域内的所有像素点。

着色是各省渐变着色，感观上能看见是从省中间向边缘扩散，同时动态的把用到的颜色以饼形图画在地图右边窗口上，并显示当前用色数。

3.2 代码实现

在界面设计时，用了三个主要功能的按钮，分别为“显示省名”、“着色”、“地图重置”。对界面的设计代码实现如下：

BEGIN

PUSHBUTTON "显示省名",IDC_SHOWPROVC,396,183,50,14

PUSHBUTTON "地图重置",IDC_RELOADMAP,459,183,50,14

DEFPUSHBUTTON "着色",ID_MAKECOLOR,395,226,50,14

PUSHBUTTON "退出",IDCANCEL,459,270,50,14

GROUPBOX "",IDC_STATIC,5,1,379,292

LTEXT "当前还没有对地图着色！",IDC_LABE,394,12,106,11

GROUPBOX "",IDC_STATIC,393,25,125,125

GROUPBOX "操作选择区",IDC_STATIC,392,165,126,93

LTEXT "退出请点这里：",IDC_STATIC,404,273,49,8

LTEXT "",ID_TIME,417,138,80,8

END

对“地图重置”按钮的点击事件如下：

void C地图着色Dlg::OnBnClickedReloadmap()

{

isColred=false;

isRinf=false;

CClientDC dc(this);

CBitmap map;map.LoadBitmap(IDB_BITMAP2);

BITMAP masize;

map.GetBitmap(&masize);///得到位图信息体。

CDC comp;

comp.CreateCompatibleDC(&dc);///创建兼容DC

comp.SelectObject(&map);///位图选入兼容DC

dc.BitBlt(10,10,masize.bmWidth,masize.bmHeight,&comp,0,0,SRCCOPY);///显示位图到窗体。

CBrush *oldbrush;

//CBrush *brush=CBrush::FromHandle((HBRUSH)GetStockObject(NULL_BRUSH));

CBrush brush(RGB(240,240,240));

//创建和窗体色一样的画刷，不能用空画刷，否则二次着色时，饼形仍是有色的。

oldbrush=dc.SelectObject(&brush);

dc.Ellipse(720,80,880,230);///画饼形所在的圆。

m_labe.SetWindowText(CString("当前还没有对地图着色！"));

m_labTime.SetWindowText(NULL);

dc.SelectObject(oldbrush);///还原设备。

map.DeleteObject();///删除创建的资源。

brush.DeleteObject();

}

对“着色”按钮的点击事件：

void C地图着色Dlg::OnBnClickedMakecolor()///对地图进行着色。

{

if(isColred)

{

SetTimer(1,500,NULL);

MessageBox("已经对地图着了色！","提示:",MB_ICONASTERISK|MB_OK);

return;

}

if (isRinf) //如已经显示了省名，为去除省名，重新回到原始界面。

OnBnClickedReloadmap();

SetViewMapColor();

isColred=true;

}

对“显示省名”按钮的点击事件：

void C地图着色Dlg::OnBnClickedShowprovc()

{

if(isRinf)

{

SetTimer(1,500,NULL);

MessageBox(CString("信息已经显示了！"),"提示:",MB_ICONW ARNING|MB_OK);

return;

}

CClientDC dc(this);

dc.SetBkMode(0);///设置背景透明。

for (int i=0;i

{

dc.TextOut( m_mapGraph.m_maps[i].center_x,m_mapGraph.m_maps[i].center_y,m_mapGraph.m_m aps[i].str.c_str());

}

isRinf=true;

}

4 实验或测试结果

程序运行后出现如下界面：

右边圆区为动态显示着色饼形图区，上面同时也会根据颜色种数增加而动态显示颜色数。当按下显示省名时，界面如下：

当按下着色按钮时界面着色后如下：

着色过程是可观的，渐变从左到右，逐个省从其中心环形扩散着色。右边圆形区会在每次增加一种新颜色后，用相应颜色画一个饼形。同时上面标签文字会动态显示当前用色数。在着色完全结束后，会在圆形区正下面显示带个着色过程所用的时间。

当我们按下重置地图时，会出现最初启动程序的界面，用户可以继续操作。

当按下‘导出地图信息时’程序会自己打开一个地图信息文件，显示在所有窗口最前端，文件如下：

程序中可能会出现的如下提示对话框，并都会自动在0.5秒内消失。

5 结论

在这个基于回溯法的地图着色问题研究过程中，我负责的是显示界面设计这个部分和edge文档和node文档的编写。虽然不是此问题的核心，但我也是很用心地完成它。在程序设计中，根据信息确定地图各省边界，从省中心回溯对各省扩散着色。

通过对地图着色程序的设计，理解了图在程序中的运用和表示。我以前从来没有接触过MFC，这是我第一次用C++实现可视化界面的设计，我觉得很有成就感。

参考文献

[1] 佘玉梅，段鹏.人工智能及其应用[M].上海交通大学出版社,2007.

[2] 吴胜，王书芹.人工智能基础与应用[M].电子工业出版社,2007.1.

回溯法论文-回溯法的分析与应用

沈阳理工大学算法实践与创新论文

摘要对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的 K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。关键词: 回溯法图的着色问题符号三角形问题图排列问题

目录第1章引言 (1) 第2章回溯法的背景 (2) 第3章图的着色问题 (4) 3.1 问题描述 (4) 3.2 四色猜想 (4) 3.3 算法设计 (5) 3.4 源代码 (6) 3.5 运行结果图 (10) 第4章符号三角形问题 (11) 4.1 问题描述 (11) 4.2 算法设计 (11) 4.3 源代码 (12) 4.4 运行结果图 (16) 第5章圆的排列问题 (17) 5.1 问题描述 (17) 5.2 问题分析 (17) 5.3 源代码 (18) 5.4 运行结果图 (22) 结论 (23) 参考文献 (24)

图着色

算法设计课程设计题目图着色问题姓名学号专业年级指导教师职称 2014年 12月 4日

图的m着色问题 1 摘要 (3) 2 图的着色问题 (4) 2.1 图的着色问题的来源 (4) 2.2 图的着色问题的描述 (4) 3算法的基本思想 (4) 3.1 求极小覆盖法----布尔代数法 (4) 3.2 穷举法－Welch Powell着色法 (4) 3.3 回溯法 (4) 3.4 贪心法 (4) 3.5 蚁群算法 (5) 4算法步骤 (5) 4.1 求极小覆盖法----布尔代数法 (4) 4.2 穷举法－Welch Powell着色法 (4) 4.3 回溯法 (4) 4.4 贪心法 (4) 4.5 蚁群法 (4) 5 理论分析（复杂度比较）、实验性能比较 (7) 5.1 复杂度分析 (4) 5.2 实验性能比较 (4) 6 心得体会 (8) 7参考文献 (8) 8 附录 (8)

摘要图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态搜索方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。关键词：图着色 c++代码 2、图的着色问题 2.1图的着色问题的来源 1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。” 用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这就是源于地图着色的四色猜想问题。这里所指的相邻区域，是指有一整段边界是公共边界。如果两个区域只相遇于一点或有限多点，就不叫相邻。因为用相同的颜色给它们着色不会引起混淆。用四种颜色着色的世界地图：采用四种颜色着色的美国地图： 2.2图的着色问题的描述（一）图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。（二）通常所说的着色问题是指下述两类问题：

地图学课程设计说明书

佛山科学技术学院《地图学课程设计》说明书专业自然地理与资源环境姓名薛春惠成绩班级 13自然地理与资源环境学号2013804142 日期 2015/6/27

目录一、地图内容二、设计步骤收集资料绘制地图三、城市状况四、南海旅游景点六、存在的不足七、专题图一、地图内容

二、设计步骤 1 收集资料收集各种地图、影像、数据和文字资料，分析汇总资料，选取有效部分加工使用，分别用到《中国自然地理地图集》、《广东省交通地图》、《佛山市旅游地图》、《佛山市南海区地图》、1：10万佛山市地形图、佛山市卫星影像等。 2、绘制地图 (1)投影网格与比例尺：依据地图内容、用途选用等比例尺底图，注意图廓的配准、注记与经纬网密度删减。 (2)水系：选用河流、湖泊、水库、海岸线等，适当概括。 (3)居民点：居民点分级、概括，地名分级注记。 (4)边界线：视专题地图需要选取（国、省、市、县、镇边界），线性符号选用与设计。 (5)交通线：铁路（车站）、国道、高速公路和水运航线（码头）三、城市状况 3.1 地理位置

3.2 地形地貌 3.3 行政规划 3.4 人口概况 3.5 矿产资源 3.6 水资源和水文情况 3.7 商业广场情况四、南海旅游景点西樵山西樵山风景名胜区位于广东省南海市西南部，面积约十四平方公里，西樵山有七十二峰，以山青，水奇著称，享有“岭南佳境”之盛名。１９８８年被定为国家重点风景名胜区。西樵山是七八千万年前由海底火山喷发岩浆，岩状，火山灰后形成的死火山，山体外陡内平，状若莲衣复合，大秤峰居群峰之首，九龙岩，冬菇石，石燕石等峰岩形态万千。西樵山岩石节理发育，裂隙纵横，富有潜水，形成多处水景，有２３２口泉眼，２８处瀑布。“欲览西樵胜，应先访白云”。位于西樵山西北部的白云洞为——马蹄形山谷，它兼收岩泉飞瀑之美，有“胜甲西樵”之称。三峰之间有两飞泉左右迂回而下，称“大云泉”、“小云泉”。泉水折叠汇成了三个湖，即所谓“白云飞下过三湖”：上为“应潮湖”，中为“鉴湖”，下为“会龙湖”。现在其下又增辟“白云”、“人工”两湖，形成五湖飞瀑交辉，亭台山水相映的奇泉。洞山腰的云泉仙馆原是明代的玉楼书院，云泉仙馆西的“三湖书院”门额为林则徐所题，康有为青年时代曾在此面壁苦读三年，山西南部有西天湖和左垂虹瀑，右垂虹瀑等景；山东南部有清暑岩，云岩飞瀑等景，山东北部有全山最大的瀑布玉岩飞瀑，以及玉岩，仙人石，东天湖等景。早在新、旧石器时代，西樵山就有人类活动，留下许多历史遗迹，史学界称为“西樵山文化”。明代中叶成为南国理学名山，至今还保存着白云古寺，以及大量摩崖石刻等文物古迹。西樵山碧玉洞碧玉洞为峰间峡谷，两边怪石嶙峋、谷底狭径崎岖、洞中有玉岩珠瀑，听玉石室、遇仙桥，垂云石、东天湖等景点。其中，玉岩珠瀑为西樵山最大瀑布。其中“西樵云瀑”在清朝已列为“羊城八景”之一，君行西樵，宛若画中游历，秀甲西樵的白云洞景区，融二十四景于一体，而其间古代建筑掩映，错落有致，碧玉洞，

C语言地图着色

课程设计地图着色课程设计名称：课程设计专业班级：学生姓名：学号：指导教师：课程设计时间：

计算机专业课程设计任务书学生姓名专业班级学号题目地图着色课题性质课题来源指导教师同组姓名主要内容学习掌握并熟练运用C语言进行程序设计；针对具体应用问题，选择、设计和实现合适的抽象数据类型；进行简单的需求分析，给出设计方案。任务要求综合运用和融化所学理论知识，提高分析和解决实际问题的能力，达到培养良好程序设计能力和习惯的目的，为开发满足问题要求的小型应用软件奠定基础，达到软件工程的综合性基础训练的目的。完成需求分析报告，报告中对关键部分给出图表说明。要求格式规范，工作量饱满。参考文献《数据结构（C语言版）》严蔚敏清华大学出版社《C语言程序设计》（第三版）谭浩强清华大学出版社

指导教师签字：审查意见教研室主任签字： 2014年6月15 日

目录 1 需求分析 (4) 2 概要设计 (4) 3详细设计 (5) 4 运行环境 (6) 5开发环境 (6) 6 程序设计.............................................................................................6~9 7 调试分析........................................................................................9~10 8 测试结果 (10) 9参考文献 (11) 10心得体会 (11) 11成绩评价表 (12)

算法设计与分析复习题目及答案(1)

分治法1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。不可以使用分治法求解的是（0/1背包问题）。动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。矩阵连乘问题的算法可由（动态规划算法B）设计实现。实现最大子段和利用的算法是（动态规划法）。贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).

地图学课程设计报告

地图学课程设计报告学生姓名序号班级地信指导老师日期 2013 .6 .25

目录一、前言 (1) 二、基于ArcMap的全国人口分布、构成及演变分析 (1) （一）ArcMap中专题现象的表示方法 (1) （二）反映全国人口分布、构成及演变的专题图表示方法的选择 (1) （三）1990年全国的人口分布与构成分析 (1) （四）从1982年到1990年全国人口的演变趋势分析 (5) 三、武汉市电子地图设计与编绘 (8) （一）总体方案 (8) （二）地图分层 (8) （三）地图数字化与图形编辑 (9) （四）表属性辑 (10) （五）图面配置 (10) （六）图幅关联及媒体链接........................................................................................ (10) （七）制作完成后截图 (11) 四、收获与建议 (13) 附件

一、前言本次课程设计是在学完《地图学》课程后开展的实践教学。目的是通过课程设计，巩固课堂所学书本知识，进一步理解和掌握各类电子地图的编绘方法，学会运用常用GIS软件开展机助制图的方法与步骤，并能根据具体的任务独立开展地图的设计与编绘，对专题地图进行专题分析，为GIS软件开发中的地理信息可视化打下基础。通过对1982和1990年全国人口状况专题地图的制作，熟悉专题地图的制作与表示方法；通过武汉市电子地图的制作，进一步熟悉纸质地图的矢量化与地图的多媒体化即制作电子地图。二、基于ArcGIS的全国人口分布、构成及演变分析（一）MapInfo中专题现象的表示方法 1、点值法——用点状符号表示数量的分布。 2、等值线法——用线状符号表示定量的分布，用于表示连续分布的事物的数量变化特征。 3、范围法——用于用面状符号表示不连续分布的面状事物。 4、质底法——用于用面状符号表示连续分布的事物的定性特征。 5、量底法（分级统计图法）——用于用面状符号表示连续分布的事物的数量特征。 6、定域统计图法（分区统计图法）——用点状符号表示面状分布事物的数量特征。着重表示不同区域单元同一事物的数量对比，也可以兼顾同一区域内组成某一事物的各组分间的数量对比。 7、定位统计图法——用点状符号表示面状分布事物的数量特征。着重表示同一区域单元内某一事物的各组分间的数量对比，也可以兼顾不同区域单元同一事物的数量对比。（二）反映全国人口分布、构成及演变的专题图表示方法的选择在反映全国人口分布时，用了点值法表示，反映出了各省的人口密度分布，用柱状图表示了全国各年龄段的人口比例，用饼状图表示了男女比例，从82年到90年人口的增长趋势用了柱状图表示。（三）1990年全国的人口分布与构成分析

地图着色问题

一、需求分析 1、问题描述现在有一张地图，为了便于区别各个地图上的板块，地图上相邻的颜色块应该是不同的颜色。现在的任务是给定一张地图，要对其进行着色，相邻的板块之间的颜色不能相同，输出最后的着色的方案。 2、基本分析功能一：为了程序的灵活性，可以让程序自由建立图功能二：为建好的图进行着色。 3、输入输出输入一张图的信息，正确输入边数和顶点数，输入边的关系（两个顶点之间的），颜色只要四种，分别用数字1到4表示。输出时根据每个顶点不同的标号输出着色的结果。二、概要设计 1、设计思路给定四种颜色，从选定的第一个顶点开始着色，先是第一种颜色，如果这个颜色与这个顶点的其他邻接顶点颜色不重复，则这个顶点可以使用此颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上述过程。着色过程就是一个递归的过程，直到所有的顶点都有着色后结束着色过程

结束

2、数据结构设计：因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构是邻接矩阵，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点邻接，如果用邻接矩阵就能符合实际的需求，虽然占用稍大的空间，但是增强了程序的实际使用性。抽象数据类型定义如下：数据对象是点和边（vex&adj）数据关系是颜色分布以及边的相邻的两个顶点基本操作： CreatGrouph(&G); 创建一张需要操作的无向图G Destroy(Graph &G); 初始条件：无向图G存在操作结果：销毁图G LocateVex(&G,i) 初始条件：无向图G存在操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息 Trycolor(current &G,store[]) 初始条件：无向图G存在，在图中有第current个顶点

算法分析与程序设计动态规划及回溯法解背包问题

动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

回溯法实验(最大团问题)

算法分析与设计实验报告第七次附加实验

} } 测试结果当输入图如下时：当输入图如下时： 1 2 3 4 5 1 2 3 4 5

当输入图如下时： 1 2 3 4 5

附录：完整代码（回溯法） //最大团问题回溯法求解 #include using namespace std; class Clique { friend void MaxClique(int **,int *,int ); private: void Backtrack(int i); int **a; //图的邻接矩阵 int n; //图的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前顶点数 int bestn; //当前最大顶点数 }; void Clique::Backtrack(int i) { //计算最大团 if(i>n) //到达叶子节点 { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn;

cout<<"最大团：（"; for(int i=1;i=bestn) { //修改一下上界函数的条件，可以得到 x[i]=0; //相同点数时的解 Backtrack(i+1); } } void MaxClique(int **a,int *v,int n) { //初始化Y Clique Y; Y.x=new int[n+1]; Y.a=a; Y.n=n; https://www.sodocs.net/doc/ec11291322.html,=0; Y.bestn=0; Y.bestx=v; Y.Backtrack(1); delete [] Y.x; cout<<"最大团的顶点数："<

算法设计与分析：回溯法-实验报告

应用数学学院信息安全专业班学号姓名实验题目回溯算法实验评分表

实验报告一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。二、实验内容【实验内容】最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。三、算法思想和实现【实现代码】

【实验数据】假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。部件重量表：部件价格表：【运行结果】

实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。四、问题与讨论影响回溯法效率的因素有哪些？答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。五、总结这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井

用回溯法求解图的m着色问题

实验二用回溯法求解图的m着色问题一、实验目的 1 2、使用回溯法编程求解图的m着色问题。二、实验原理回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。回溯法从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。三、问题描述给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。设计一个算法，找出用m种颜色对一个图进行着色的不同方案。四、算法设计与分析用邻接矩阵a来表示一个无向连通图G=(V,E)。用整数1,2,…,m来表示m种不同的颜色。x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。在回溯算法Backtrack中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色方案，因此当前已找到的可m着色方案数sum增1。当i≤n时，当前扩展结点Z是解空间树中的一个内部结点。该结点有x[i]=1,2,…,m。对当前扩展结点Z的每一个儿子结点,由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。五、实验结果源程序： #include using namespace std;

地理信息系统课程设计详细过程

课程设计说明书（地图编绘与课程设计）

年月日

地图学课程设计教学大纲一、课程设计题目基于的专题地图设计与编制。二、课程设计目的本设计是在完成地图学的课堂教学后进行的，旨在加深学生对专题地图的认识和理解，包括专题地图的概念、特征、类型、编辑设计、表现方法以及图例的设计和图面配置，巩固课堂教学的内容。是中地数码集团推出的专业矢量绘图软件，是中国具有完全自主知识版权的地理信息系统软件，是全球唯一的搭建式数据中心集成开发平台，实现遥感处理与完全融合，支持空中、地上、地表、地下全空间真三维一体化的开发平台。在绘图、设计制作、编辑合成、输入输出和网页制作等方面功能强大，包括海量无缝图库管理、空间数据库管理、空间分析工具、网络分析功能、多源图像分析与处理等。学生应了解绘图环境，熟练掌握矢量成图步骤方法，会用进行符号设计。是开发，本次设计主要应用信息编辑与分析功能，利用的桌面功能来完成设计，完成矢量数据的属性字段添加，并对其进行分析与编辑。是一个集成了众多高级应用的软件套件，它包含了一套带有用户界面组件的桌面应用（例如，，，以及）。具有三种功能级别――,，和）。三、课程设计要求通过上机操作，要求学生在和软件的基础上根据底图进行矢量化、地理数据的输入、编辑、存储和输出方法。具体要求学生做到： 1 专题地图的编制按照专题地图的表现方法进行，利用相应的符号表示各种自然或人文现象；专题地图的相关基础资料见附件； 2 编辑的图件将就美观、大方，可以适度张扬个性； 3 学会编写课程设计报告。课程设计报告要求格式规范，图文并茂，5000字左右；课程设计报告内容包括：（1）课程设计的目的和意义；（2）专题地图的背景资料（包括自然地理、地质、社会经济等）；（3）专题地图的编制过程；（4）专题地图的设计与优化过程；

地图着色课程设计

算法分析与设计课程设计说明书地图着色学院：计算机与控制工程学院专业：计算机科学与技术学生姓名：xxxxx学号：成绩学生姓名：xxxxx 学号：成绩指导教师：

内容提要此题为地图着色问题，由地图着色问题很容易想到图的着色问题，因此可以把地图抽象为无向图来解决地图的着色问题。对地图的抽象相当于对图的抽象，即以邻接矩阵来实现地图的区域相邻的描绘，而对地图的区域数即以图的顶点数来描绘。设计说明书的内容包括需求分析，概要设计，详细设计，代码实现，后期测试等内容，需求分析是对此问题所需要实现的功能的介绍，概要设计是对所需要实现功能的模块划分，以及初步的实现思想，详细设计通过编写大致的代码来实现功能，代码实现则是具体的解决问题，解决此问题设计了两个算法，贪心，回溯，在程序的测试阶段，回溯算法对同一个问题的解决速率高于贪心算法，但是结果都是以最少的颜色数来染色。课题实现的环境是在window环境下的eclipse中，通过在其中输入地图的区域数，图的连接情况，来选择相应的算法来实现染色，本次课题所采用的数据结构主要是二维数组来抽象图的邻接矩阵。

目录 1引言（或绪论） (1) 2需求分析 (2) 2.1 问题分析 (2) 2.3问题解决 (2) 2.3 运行环境及开发工具 (3) 2.4功能需求 (3) 2.4.1 地图的抽象及输入 (3) 2.4.2 地图着色的算法设计 (3) 2.4.3 界面设计 (3) 2.4.4 输出设计 (3) 2.5任务分配 (4) 3概要设计 (4) 3.1 数据定义 (4) 3.2 功能模块定义 (4) 3.2.1 地图的抽象输入模块 (4) 3.2.2 输出模块 (4) 3.2.3 地图染色模块 (4) 3.2.4 界面设计模块 (5) 3.2.5 主模块 (5) 3.3 程序流程图 (6) 4 详细设计 (7) 4.1 地图输入模块 (7) 4.1.1 数据类型 (7) 4.1.2 具体实现 (7) 4.2 界面设计模块 (7) 4.2.1 数据类型 (7) 4.2.2 具体实现 (7) 4.3 算法设计模块 (9) 4.3.1 回溯法过程 (9)

算法设计与分析复习题目及答案doc

分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。不可以使用分治法求解的是（0/1背包问题）。动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。矩阵连乘问题的算法可由（动态规划算法B）设计实现。实现最大子段和利用的算法是（动态规划法）。贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）

分支限界法最大效益优先是（分支界限法）的一搜索方式。分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。（最优子结构性质）是贪心算法与动态规划算法的共同点。贪心算法与动态规划算法的主要区别是（贪心选择性质）。回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）

地图学课程设计心得体会

地图学课程设计心得体会通过此次课程设计，使我更加扎实的掌握了有关地图制作的基本知识，而且掌握普通地图和专题地图的编制方法与过程、制图综合的理论与技术熟使用悉用MapGIS、ArcGIS等制图软件以及结合运用 Photoshop进行地图编制的全过程及基本方法，了解MapGIS、ArcGIS在制图领域中的应用。巩固课堂上所学的地图编绘的基本原理、综合理论和方法，从而提高我们的专业水平和动手能力。本次课程设计在制图过程中然遇到了不少的问题，但经过一次又一次的思考，一次又一次的实践，并通过同学间互相帮助以及向各师兄的询问，最终完成了省市普通地图和专题地图的制作。在制图过程中也暴露出了自己在这方面的知识欠缺和对软件不不熟悉。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误和不足，不断改正，不断领悟，不断获取。在制图过程中，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中学习到了曾经不知道不懂的东西。所以在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的去探究，然后一一进行解决，只有这样，才能很好的完成想做的事，才能在今后的道路上劈荆斩棘，收获喜悦，收获成功！课程设计诚然是一门专业课，使我很多专业知识以及专业技能上的提升，同时又是一门辩思课，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。使我对抽象的理论有了具体的认识。通过这次课程设计，我掌握了专业软件件的运用；掌握了地图矢量化的不同方法，地图匹配，属性编辑，以及如何提高地图质量，地图美观，也掌握了制图方法和技术，通过查询和收集资料，也懂得了很多的专业术语和知识。我认为，在这学期的实验中，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这也是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。回顾起此课程设计，感慨颇多，从理论到实践，在这几天的时间里，可以说得是苦多于甜，累，但是可以学到很多很多的东西，不仅巩固了以前所学过的知识，也学到了很多在书本上所没有学到过的知识。在设计的过程中遇到问题也颇多，但可喜的是最终都得到了解决。此次课程设计给自己最大的感触是，不管什么样的软件，懂的也好不懂的也好，都要动手去用，只有自己操作了，才会真正明白其中的用处，其次是，在遇到困难的时候，不要总是一个人在那捣鼓，同学间应该互相的帮助，有时候向别人学习，会比自己一个人在哪儿毫无头绪的摸索更好。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。

数据结构课程设计报告地图着色问题

课程设计报告课程设计题目：地图着色问题专业：xxxxxxxxx 班级：xxxxxxxxx 姓名：xxxxxxxxx

一：需求分析： 1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少； 2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系； 3)演示程序以用户和计算机的对话方式进行； 4)最后对结果做出简单分析。二：概要设计一：设计思路把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。二：数据结构设计因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。其中： typedef struct ArcNode { int x; （表示与当前顶点所表示省份相邻的省份的位置信息） struct ArcNode *next; （指向下一个弧结点） }ArcNode; （表示省份之间相邻关系的弧结点） typedef struct { char *name; （顶点所表示的省份的名称） int color; （省份的颜色，用数字表示不同的颜色） ArcNode *firstnext; （指向第一个弧） }shengfen[35];

《地图学课程设计》大纲

《地图学课程设计》大纲一、目的、内容和要求 1、目的通过本项课程设计，掌握地理底图和专题地图编制的基本原理与方法，能够熟练运用制图软件编绘地图，提高数据资料收集、图形化设计和信息综合表达的能力。 2、内容具体内容包括： 2.1地理底图的编制： (1)投影网格与比例尺：依据地图内容、用途选用等比例尺底图，注意图廓的配准、注记与经纬网密度删减。 (2)水系：选用河流、湖泊、水库、海岸线等，适当概括。 (3)居民点：居民点分级、概括，地名分级注记。 (4)边界线：视专题地图需要选取（国、省、市、县、镇边界），线性符号选用与设计。 (5)交通线：铁路（车站）、国道、高速公路和水运航线（码头） (6)地貌信息：根据专题需要，选取少量等高线。 2.2专题地图设计 (7)收集专题信息相关的图件、文本、数据和参考资料。 (8)资料加工处理，数据统计分析，图象资料运用。 (9)专题内容表示：符号设计与表现形式，图例系统设计。 (10)地图概括：地图内容的选择，点、线、面要素的分类、简化、夸张与合并。 (11)图面内容设计：地图幅面上图名、图例、主图、附图、图表、比例尺、文字等位置安排；图廓、色彩、网纹配置、版权说明等。 2.3 编写专题地图说明书 (12)资料与数据来源，分析方法与成图过程。 (13)专题信息导读：专业信息时空分布规律、成因与对策分析。 (14)存在问题分析。 2.4 地图专题内容赣州市地理地图（行政分区地图）基础上（网上搜索），编绘旅游专题、经济专题、人口专题、交通专题、城市专题、环境专题等。 3、要求学生地图课程设计时按地图出版设计要求进行，每人按时上交一份装订成册的专题地图（二分之一开本787*960，彩色打印）及其说明书，并备份存档电子文本和图象、图形格式文件一套。

数据结构课程设计地图着色问题