TSP问题的遗传算法求解方案--源程序清单旅行商问题包含算法介绍源程序测试结果讲课讲稿

1、Good is good, but better carries it.精益求精，善益求善。TSP问题的遗传算法求解方案-源程序清单旅行商问题，包含算法介绍，源程序，测试结果-TSP问题的遗传算法求解方案算法的软件实现4.1开发环境介绍本文中的所有算法是在VisualC+6.0的操作平台上进行开发的，并结合STL进行编程。1、VisualC+6.0简介VisualC+6.0是微软公司最新出品的功能最为强大的可视化开放工具，是计算机界公认的最优秀的应用开发工具之一。Microsoft的基本类库使得开发Windows应用程序比以往任何时候都要容易。VisualC+作为一种程序设计语言，它同时也是一

2、个集成开发工具，提供了软件代码自动生成和可视化的资源编辑功能。2、VisualC+6.0的优势(1).拥有强大的编辑环境。(2).拥有强大的类库的支持。(3).拥有强大的调试环境。(4).拥有较强的低层控制能力。(5).拥有强大的帮助系统MSDN的支持。(6).拥有一个高效的编译器，产生的可执行文件体积小巧、运行速度快。3、STL简介STL（StandardTemplateLibrary），即标准模板库，是一个具有工业强度的，高效的C+程序库。它被容纳于C+标准程序库（C+StandardLibrary）中，是ANSI/ISOC+标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领

3、域里所常用的基本数据结构和基本算法。为广大C+程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。这种现象有些类似于MicrosoftVisualC+中的MFC（MicrosoftFoundationClassLibrary），或者是BorlandC+Builder中的VCL(VisualComponentLibrary)，但是它比二者具有更强的优势。更加值得一提的是，它具备以下几个区别于其它软件库的优点：(1).经过类属编程方法精心组织的，可互换的编程模块能够提供比传统组件设开始初始化遗传算法的相关参数计算每个个体的适应值产生城市对城市进行编码是否符合终止条件？输出正确的TSP结果

4、是GEN=GEN+1选择交叉变异否世代进化轮盘赌选择普通选择GXCXOXPMX基于次序的变异基于位置的变异倒位变异图4.1遗传算法解TSP的具体流程图计方法丰富得多的组合方式。(2).类属编程方法设计也是将来为数据库，用户界面等专业领域开发组件的基础。(3).通过使用某些编译机制并根据不同的算法进行具体的设计，可以在不损失效率的情况下实现对组件的概括。与此形成鲜明对照的是，其它一些具有复杂继承层次和大量使用虚函数的C+库结构则通常会降低效率。4.2算法实现的流程图本设计的具体流程图如图4.1所示：4.3算法的各个模块及其详细设计思路1城市生成模块用户可以点击鼠标左键产生城市，也可以选择菜单栏的

5、设置城市选项，通过输入城市数目来随机生成城市。当然，如果用户选择错了城市，可以在该城市上点击鼠标右键来清除城市。如果用户要清除所有的城市，可以双击鼠标右键或选择菜单栏的结束选项，都可以清除所有的城市。其设计设计思路如图4.2所示：调用画图函数画点(即设置城市)程序将点的信息存入一个点向量中程序检测鼠标移动的具体信息按下鼠标左键用一个变量记入要产生的城市数按下鼠标右键选择菜单栏的设置城市选项将点向量中要除去的点找出来循环调用鼠标左键点击消息直到达到要求的城市数选择菜单栏的结束选项重新画点向量中的所有点(此时该删除的点已从点向量中删除)重新画地图(即清除了所有的点)图4.2城市生成模块的设计思路最

6、后的效果如图4.3所示：图4.3TSP问题城市设置实现效果2.地图选择模块根据具体的需要，用户可以选择不同的地图，本设计提供的地图有：基于直角坐标系的地图和圆形地图，这两个地图由不同的类来产生。其中类DefaultMap产生直角坐标地图，类RoundMap产生圆形地图。图4.4所示的是直角坐标地图，图4.5所示的是圆形地图。图4.4直角坐标地图图4.5圆形地图3.遗传算法解TSP的参数设置模块在具体的应用中，用户可以根据具体情况来设置遗传算法的相关参数，这些参数包括：交叉率：控制程序进行交叉的次数，在本设计中，先随机生成一个数，如果这个数大于交叉率，则不交叉，如果这个数小于交叉率，则进行交叉。

7、具体实现如下：pick=float(randomInt(0,1000)/1000;if(pickpcross)/进行交叉操作else/不进行交叉操作变异率：控制程序进行变异的次数，在本设计中，先随机生成一个数，如果这个数大于变异率，则不变异，如果这个数小于变异率，则进行变异操作。具体实现如下：pick=float(randomInt(0,1000)/1000;if(pickpmutation)/进行变异操作else/不进行变异操作种群大小：即种群中所含有的个体数量，选择一个合理的种群值，不但会使得群体的多样性增强，防止遗传算法的“早熟现象”，还会使得遗传操作收敛得更快。世代数：控制遗传操作世代

8、进化的次数，合理的世代数能够使得计算结果的优劣程度不同。图4.6遗传算法解TSP的参数设置进化设置：根据子染色体与父染色体的关系，进化设置又分为两种：普通进化：完全模仿自然进化，子染色体可能比父染色体优秀，也可能比父染色体差。强制进化：选取子染色体中比父染色体优秀的染色体，杀死子染色体中比父染色体差的染色体。使得进化一直朝着优秀染色体的方向进化。具体的实现效果如图4.6所示：4.交叉算子选择模块交叉操作是遗传算法中最重要的一环，交叉算法的优劣将最大限度地影响遗传算法的结果。本设计先根据国外专家提出的解TSP的几种经典算法，然后编程将其实现，并在此基础上，提出一种改进的交叉算法。在具体的应用中，

9、用户可以根据自己的需要，选择最符合实际情况的交叉算法。程序的具体选择模块如下：/交叉算子的选择模块inlinevoidCGA:crossover(Chrom&parent1,Chrom&parent2,Chrom&child1,Chrom&child2)switch(TempCrossoverStyle)caseID_PARTIALLY_MATCHED_CROSSOVER:/部分匹配交叉partially_matched_crossover(parent1,parent2,child1,child2);break;caseID_ORDER_CROSSOVER:/顺序交叉order_crosso

10、ver(parent1,parent2,child1,child2);break;caseID_CYCLE_CROSSOVER:/循环交叉cycle_crossover(parent1,parent2,child1,child2);break;caseID_GREED_CROSSOVER:/循环贪心交叉greed_crossover(parent1,parent2,child1,child2);break;default:break;5.变异算子选择模块求解TSP时，变异算子的设计比交叉算子的设计灵活，任何具有局部搜索能力的算子都可以作为它的变异算子。本设计实现了三种变异：基于次序的变异，基于

11、位置的变异，倒位变异。程序的具体选择模块如下：/变异算子选择模块inlinevoidCGA:mutation(Chrom&chr)switch(TempMutationStyle)caseID_ORDER_MUTATION:/基于次序的变异order_oriented_mutation(chr);break;caseID_POSITION_MUTATION:/基于位置的变异position_oriented_mutation(chr);break;caseID_REVERSE_MUTATION:/倒位变异reverse_mutation(chr);break;default:break;6.具

12、体输出信息显示模块为了使程序运行时具体的算法和各种数据信息更加明确化，增加了信息显示模块，这样，在程序运行时用户可以掌握具体的数据信息，以便对各种算法进行比较。信息显示模块包括：计算结果模块，算法运行时间模块，所选遗传算子模块。下面分别对各个显示模块进行讨论：计算结果模块：输出的信息包括当前鼠标的横坐标，当前鼠标的纵坐标，这两个信息是为了用户设置城市时参考的。城市总数信息是用户设置的城市数目。总距离信息是经过计算的TSP问题的最优路径长度，它是屏幕上象素点间的距离。算法运行时间模块：包括算法启动前时间，它是用户设置完城市，进行求解时刻的时间；算法结束时间，它是程序运行完成，正确输出TSP结果时

13、刻的时间；算法耗费时间，它是进行遗传算法求解TSP时算法所消耗的时间。所选遗传算子模块：它显示的是用户选择了那种交叉算子，那种遗传算子，以便于对各种算法比较时使用。具体的显示如图4.7所示：图4.7各种信息显示图4.4设计中主要的类和函数的功能1.Map类，DefaultMap类，RoundMap类DefaultMap类这三个类均为画图相关的类，其继承关系为：继承Map类基类RoundMap类继承图4.8画图类继承关系其中，DefaultMap类主要是与直角坐标地图有关，RoundMap类主要是与圆形地图有关。这些类提供了画地图函数：DrawMap，保存地图中的位置函数：SaveClickPo

14、int，清除点向量中所有城市点的函数：DelAllPoint，在地图上画点的函数：DrawPonit，将地图上已存在的点删除函数：SmearPonit等等。2.CGA类这个类主要是为遗传算法设置的，在这个类中定义了基因结构体代表一个城市，染色体结构体代表到各城市去的一种组合，还定义了种群结构体表示各种不同基因的组合。这个类主要是进行遗传算法操作的，包括各种进化运算，即选择，交叉，变异等等。这个类中的主要函数有：遗传算法参数设置函数：preSet，遗传算法启动函数：start，交叉类型选择函数：SetCrossoverStyle，变异类型选择函数：Set-MutationStyle，世代进化函数

15、：generation，染色体适应度计算函数：chromCost，种群个体适应度计算函数：popCost，初始化染色体函数：initChrom，初始化种群函数：initpop，轮盘赌选择函数：selectChrom等等。3.Control类Control类主要是对程序进行控制的，它为各个模块的组合提供了接口，并且将必要的数据信息在屏幕上输出。它提供的函数主要有：欢迎窗口显示函数：welcome，遗传算法接口函数：SetGaInformation，信息显示函数：DisPlay等等。4.Line类Line类主要是计算TSP问题的具体操作，包括对城市点构成矩阵的设置，计算城市点之间的距离，画线，保存

16、城市点的矩阵信息，计算最终结果等。5.main.cpp这是一个主程序文件，是整个程序启动，操作的主控文件。是整个程序的框架部分。此外，程序还有头文件类，资源类等等。这里就不详细介绍，具体的源程序见程序文档。5软件测试及实验结果分析5.1软件测试以下是软件测试的步骤：1.运行程序后，弹出欢迎消息，如图5.1所示：图5.1遗传算法解TSP问题欢迎窗口2.点击确定，进入主程序模块，点击选择地图，可以选择直角坐标地图和圆形地图，默认地图为直角坐标地图，下面的演示以直角坐标地图为主，如图5.2所示：图5.2遗传算法解TSP问题直角坐标演示地图3.在屏幕上点击鼠标左键可设置城市，也可以点击菜单栏设置城市，

17、弹出设置城市数目对话框，在对话框中输入城市数目，可以在屏幕上随机生成城市，具体情况如图5.3，5.4所示：图5.3设置城市数目图5.4设置城市4.点击菜单栏遗传算法设置按钮，弹出遗传算法参数设置对话框，如图5.5所示：图5.5遗传算法参数设置对话框在遗传算法参数设置对话框中，可以设置交叉率，变异率，种群大小，世代数以及选择进化设置等。5.点击菜单栏交叉类型按钮，可以选择交叉算法，如图5.6所示：图5.6交叉类型选择可供选择的交叉类型有：部分匹配交叉，顺序交叉，循环交叉，循环贪心交叉。6.点击菜单栏变异类型按钮，可以选择变异算法，如图5.7所示，可供选择的变异类型有：基于次序的变异，基于位置的变

18、异，倒位变异。图5.7变异类型选择7然后点击菜单栏开始，则进行计算，最终结果如图5.8所示：图5.8遗传算法解TSP问题计算结果8.点击菜单栏结束可以清除所有点，点击帮助，可以弹出帮助文件。至于圆形地图的测试过程与直角坐标地图相似。5.2算法的正确性验证为了测试算法的正确性，我使用了固定城市测试模块，该模块中的城市坐标，城市大小可以预先设置。其中，城市的数目，坐标和最优解均可以参照国内外专家的文献，然后对比本程序计算的结果。如图5.9所示：图5.9固定城市测试本设计中的参考文献可见参考文献1，城市坐标见参考文献1，36，交叉率为0.6，变异率为0.2，种群大小为100，世代数为100，采用强制

19、进化方式，交叉类型为部分匹配交叉，变异类型为基于次序的变异。测试的十组数据如下：时间(s)12.67211.82812.7811.76512.68812.84411.25010.84410.68711.954最优解517492505515492509519526549491计算平均值有平均最优解为：511.5，平均时间为：11.9364s。与参考文献1，37的部分匹配交叉数据，平均最优解为：517.0，平均时间为：31.2s对比可知，本设计的算法符合要求。由于本设计使用的是强制进化方式，所以平均最优解和平均时间均有一定的改进。5.3模拟实验结果与分析5.3.1不同遗传操作组合的算法为了考察遗传

20、算法组合优化在求解TSP问题中的重要性,本文进行了多种遗传操作组合的模拟实验，各种遗传操作组合成的算法如下:GA0：部分匹配交叉+基于次序的变异GA1：部分匹配交叉+基于位置的变异GA2：部分匹配交叉+倒位变异GA3：顺序交叉+基于次序的变异GA4：顺序交叉+基于位置的变异GA5：顺序交叉+倒位变异GA6：循环交叉+基于次序的变异GA7：循环交叉+基于位置的变异GA8：循环交叉+倒位变异GA9：循环贪心交叉+基于次序的变异GA10：循环贪心交叉+基于位置的变异GA11：循环贪心交叉+倒位变异表5.130个城市位置坐标城市编号坐标城市编号坐标城市编号坐标1(40,406)11(190,323)2

21、1(2,290)2(33,39)12(401,152)22(521,92)3(268,183)13(291,201)23(172,43)4(277,377)14(620,235)24(440,150)5(361,103)15(117,154)25(252,147)6(104,4)16(546,305)26(346,343)7(180,26)17(70,197)27(461,416)8(160,70)18(468,171)28(436,258)9(194,181)19(466,258)29(322,80)10(626,395)10(234,233)30(228,357)5.3.2模拟实验结果对于

22、上述各算法，分别进行了计算机模拟实验，计算中采用的有关数据如下：城市数为30，群体规模为100，交叉概率为0.8，变异概率为0.1，群体更新100代结束，采用强制进化方式进化，每个算法采集了10组数据。其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间。30个城市的坐标如表5.1所示：对每个算法采集的数据，计算其平均结果，表5.2中的所有数据都是经过10次测试得出的统计平均结果。表5.2各种遗传操作组合求解TSP问题模拟实验结果比较算法最佳解时间(s)算法最佳解时间(s)GA02698.419.266GA62947.223.234GA12682.118.110GA729

23、18.619.250GA22675.918.234GA82903.919.360GA32524.816.125GA92521.624.695GA42524.316.187GA102523.924.685GA52523.516.309GA112522.723.8565.3.3实验结果分析由表5.2可见：1.GA0与GA1与GA2以及GA3与GA4与GA5，GA6与GA7与GA8，GA9与GA10与GA11的优化结果无大的差异，这说明变异算子在优化过程中所起的作用相对小一些。事实上，几种算法结果的相对一致性,很大程度上是变异概率取的较小,使变异在整个搜索过程中发生次数甚微造成的。这也符合自然进化的

24、规律，毕竟，变异的发生概率是极其微小的。2.排除变异算子所带来的差异，只比较交叉算子可知，循环交叉算子的效果最差，这主要是因为经过循环之后，有可能到最后才完成循环。也就是说，循环了一周，子代和父代却没有大的改变。但由于进行了一系列循环，耗费了不少时间，因此，循环交叉所花费的时间也比较多。3.通过改进的交叉算子(循环贪心交叉)和其它算子作比较可知，虽然改进的交叉算子所求的旅程长度有一定的改观，但耗费了不少时间。这主要是因为改进的交叉算子不但要循环，还要比较相邻城市之间的距离，并且所比较的城市都被扩展时，还要随机选择一个城市直到它不在所扩展的城市中或者所有的城市都被扩展，因此花费了大量的时间。因此

25、对于改进的交叉算子不宜处理太多城市的TSP问题。4.总体来说，顺序交叉比较稳定，没有太多随机选择的情况，因此，对于多城市问题，不失为一种较理想的选择。5.4改进算法与原算法的比较对于下面各比较算法，分别进行了计算机模拟实验，计算中采用的有关数据如下：城市数为30，群体规模为100，交叉概率为0.6，变异概率为0.2，群体更新100代结束，采用强制进化方式进化，每个算法采集了10组数据。其中，TSP旅程长度为屏幕上象素点之间的距离，时间为算法所消耗的CPU时间。30个城市的坐标如表5.3所示：表5.330个城市坐标城市编号坐标城市编号坐标城市编号坐标1(87,7)11(58,69)21(4,50

26、)2(91,83)12(54,62)22(13,40)3(83,46)13(51,67)23(18,40)4(71,44)14(37,84)24(24,42)5(64,60)15(41,94)25(25,38)6(68,58)16(2,99)26(41,26)7(83,69)17(7,64)27(45,21)8(87,76)18(22,60)28(44,35)9(74,78)19(25,62)29(58,35)10(71,71)10(18,54)30(62,32)5.4.1改进循环交叉算法与循环交叉算法的数值比较对于循环交叉测试的十组数据如下：时间(s)15.67214.82814.7814.

27、76515.68816.84414.65015.84414.68715.954最优解684717705715692709669676689691对于改进的循环交叉测试的十组数据如下：时间(s)11.96911.70312.32811.76512.18812.84411.25011.84410.48710.954最优解615621640632609651603621630612对于循环交叉平均最优解为：694.7，平均时间为：15.3712s。对于改进循环交叉平均最优解为：623.4，平均时间为：11.7332s。通过对比可知，改进后的算法明显优于改进前的算法。5.4.2改进循环贪心交叉算法与循

28、环贪心交叉算法的数值比较对于改进的循环贪心交叉测试的十组数据如下：时间(s)12.68713.35912.9312.42212.50012.28112.93811.50012.85912.953最优解610616643644655643590699613617对于循环贪心交叉测试的十组数据如下：时间(s)14.25013.62514.75014.17213.75014.50013.40614.31213.98514.734最优解580614626594624651626570694586对于改进的循环贪心交叉平均最优解为：633.0，平均时间为：12.6429s。对于循环贪心交叉平均最优解为：

29、616.5，平均时间为：14.1484s。通过对比可知，改进后的算法时间上明显优于改进前的算法。主要是减少了随机查找数据的时间，但由于改进后的算法是循环查找未扩展的城市，因此使得种群的多样性减少了，即使得平均最优解要比改进前差一些，但对于大量城市的TSP问题来说，节省时间是很值得考虑的。6结论TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题，它已经被证明属NP难题。TSP搜索空间随着城市数的增加而增大，在庞大的空间中寻找最优解，对于现有的常规方法和现有的计算工具而言，存在着诸多的困难。借助遗传算法的搜索能力解决TSP问题是很自然的想法。本设计在深入分析和研究遗传算法基本理论与方法的基

30、础上，不但编程实现了国内外专家提出的一些优秀的算法，而且结合具体的编程情况，对其中的一些算法作了必要的改进。最后，本设计对各种算法的组合进行了实验，并且对各种算法结果进行了比较和分析。在本文研究基础上，还可以进一步开拓以下几个方向的研究工作:1.将遗传算法运用于大规模的旅行商问题；2.将许多实际应用问题(如印制电路板的钻孔路线方案、连锁店的货物陪送路线等)建模为TSP问题，并应用遗传算法来解决；3.如何获得更好的性能是遗传算法研究中的重要课题。如何在保证求解质量的同时降低时间的开销，如何针对具体问题寻找优化的并行计算策略和群体划分策略，也是遗传算法中需要进一步深入研究的重要课题。遗传算法是新发

31、展起来的一门学科，各种理论、方法尚未成熟，需要进一步地发展和完善，但它已为解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的专业领域中。随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键的作用。程序核心代码一资源类1.头文件/NO_DEPENDENCIES/MicrosoftDeveloperStudiogeneratedincludefile./Usedbyresource

32、.rc#defineIDDefault3#defineIDR_MENU1101#defineIDI_ICON1104#defineIDD_GA_BOX105#defineIDD_HELP_BOX106#defineIDD_SETCITY107#defineIDC_EDIT21002#defineIDC_EDIT31003#defineIDC_EDIT41004#defineIDC_EDIT61008#defineIDC_RADIO11019#defineIDC_RADIO21020#defineIDI_TSP1022#defineIDC_ICON11023#defineIDC_ICON2102

33、3#defineIDC_CITYNUMBER1025#defineID_GA_SET40012#defineID_DefaultMap40020#defineID_RoundMap40021#defineID_CUSTOMMAP40023#defineID_HELP_BOX40024#defineID_GASET40026#defineID_END40027#defineID_EXIT40028#defineID_ORDER_MUTATION40030#defineID_POSITION_MUTATION40031#defineID_REVERSE_MUTATION40032#defineID

34、_PARTIALLY_MATCHED_CROSSOVER40033#defineID_ORDER_CROSSOVER40034#defineID_CYCLE_CROSSOVER40035#defineID_SET_CITY40036#defineID_GREED_CROSSOVER40037#defineID_FIXED_CITY40038/Nextdefaultvaluesfornewobjects/#ifdefAPSTUDIO_INVOKED#ifndefAPSTUDIO_READONLY_SYMBOLS#define_APS_NEXT_RESOURCE_VALUE108#define_A

35、PS_NEXT_COMMAND_VALUE40039#define_APS_NEXT_CONTROL_VALUE1027#define_APS_NEXT_SYMED_VALUE101#endif#endif二头文件类1.头文件/head.h/#pragmaonce#include#include#include#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;/命名空间/三地图类1.头文件/map.h/#pragmaonce#includehead.

36、h/MapControl控制地图以及左右键点击后对的处理/classMappublic:virtualvoidDrawMap(HWNDhwnd,HDChdc)=0;/画地图/virtualvoidSaveClickPoint()=0;/保存格式为地图中的位置virtualvoidDelAllPoint()=0;/清除vecpoin所有点/在地图上画点（参数为实际位置）virtualvoidDrawPonit(HWNDhwnd,constPOINT&)=0;/将地图上已存在的点（参数为实际位置）删除virtualvoidSmearPonit(HWNDhwnd,constPOINT&)=0;/保存

37、POINT(参数为实际位置)到向量virtualvoidAddPoint(constPOINT&)=0;/删除POINT(参数为实际位置)到向量virtualvoidSubPoint(constPOINT&)=0;/获得所有已点击的点的位置(实际值)virtualvectorGetAllClickPoint()=0;protected:POINTbeginpoint;/实际位置vectorvecpoint;/地图中的位置;/函数对象/classequal_pointpublic:equal_point()equal_point(constPOINT&_val):val(_val)boolope

38、rator()(constPOINT&point)return(point.x=val.x)&(point.y=val.y);booloperator()(constPOINT&point1,constPOINT&point2)return(point1.x=point2.x)&(point1.y=point2.y);private:POINTval;/四直角坐标地图类1.头文件/defaultmap.h/#pragmaonce#includemap.h#defineDIVISIONS110#defineDIVISIONS26classDefaultMap:publicMappublic:vo

39、idDrawMap(HWNDhwnd,HDChdc);/画地图/voidSaveClickPoint();/保存格式为地图中的位置voidDelAllPoint();/清除vecpoin所有点/在地图上画点(参数为实际位置)voidDrawPonit(HWNDhwnd,constPOINT&);/将地图上已存在的点(参数为实际位置)删除voidSmearPonit(HWNDhwnd,constPOINT&);voidAddPoint(constPOINT&);/保存POINT(参数为实际位置)到向量voidSubPoint(constPOINT&);/删除POINT(参数为实际位置)到向量/获

40、得所有已点击的点的位置(实际值)vectorGetAllClickPoint();POINTGetMapPoint(constPOINT&point);/实际POINT在地图位置POINTGetRealPoint(constPOINT&point);/地图POINT实际位置protected:/找到该点附近的像素点iarea为该点的半径vectorFindAroundPoint(constPOINT&point,intiarea);/2.源文件/defaultmap.cpp/#includedefaultmap.h/画地图/voidDefaultMap:DrawMap(HWNDhwnd,HDC

41、hdc)HPENhpen;hpen=CreatePen(PS_SOLID,1,RGB(0,128,128);/创建画笔SelectObject(hdc,hpen);for(intx=0;xDIVISIONS1;x+)/10for(inty=0;yDIVISIONS2;y+)/6Rectangle(hdc,5+x*70,50+y*70,5+(x+1)*70,50+(y+1)*70);DeleteObject(hpen);/删除画笔return;/保存删除POINT(在地图位置)到向量/*voidDefaultMap:SaveClickPoint()fstreamoutFile(copy.text

42、,ios_base:out);/以写方式打开文件if(!outFile)cerrunabletoopeninputfile:-bailingout!n;return;if(vecpoint.size()=0)return;outFile#DEFAULT_MAP_NAMEn;/以后有用outFile#vecpoint.size()n;for(intn=0;nvecpoint.size();n+)outFilevecpointn.x;outFile;outFilevecpointn.y;outFilen;return;*/删除所有点/voidDefaultMap:DelAllPoint()if(v

43、ecpoint.size()=0)return;vecpoint.clear();return;/找到该点附近的点/vectorDefaultMap:FindAroundPoint(constPOINT&point,intiarea)/iarea为该点的半径POINTtemppoint;vectorvecroundpoint;temppoint.x=point.x-6;/判断点是否在有效区域/-51temppoint.y=point.y-51;/-51if(temppoint.x0|temppoint.y700|temppoint.y420)returnvecroundpoint;iarea=

44、abs(iarea);/防止iarea小于零for(intn=-iarea;n-1-iarea;m-)temppoint.x=point.x+m;temppoint.y=point.y+n;vecroundpoint.push_back(temppoint);temppoint.x=point.x+n;temppoint.y=point.y+m;vecroundpoint.push_back(temppoint);returnvecroundpoint;/在地图上画点/在地图上画点(参数为实际位置)/voidDefaultMap:DrawPonit(HWNDhwnd,constPOINT&po

45、int)intcx=point.x-6;/判断点是否在有效区域intcy=point.y-51;if(cx0|cy700|cy420)return;AddPoint(point);HDChdc;hdc=GetDC(hwnd);HPENhpen;hpen=CreatePen(PS_DOT,5,RGB(255,0,0);SelectObject(hdc,hpen);/选择对象进DCEllipse(hdc,point.x+2,point.y+2,point.x-2,point.y-2);/画圆点DeleteObject(hpen);ReleaseDC(hwnd,hdc);return;/添加和减少点

46、(在地图位置)到向量/保存POINT(参数为实际位置)到向量/voidDefaultMap:AddPoint(constPOINT&point)POINTtempoint=point;if(vecpoint.size()!=0&find_if(vecpoint.begin(),vecpoint.end(),equal_point(tempoint)!=vecpoint.end()return;/保证点不重复vecpoint.push_back(tempoint);/清除一个指定的点/voidDefaultMap:SubPoint(constPOINT&point)if(vecpoint.siz

47、e()=0)return;vectorvecroundpoint;vector:iteratorIter1;vecroundpoint=FindAroundPoint(point,2);/获得该点附近的像素点if(vecroundpoint.size()=0)return;Iter1=find_first_of(vecpoint.begin(),vecpoint.end(),vecroundpoint.begin(),vecroundpoint.end(),equal_point();if(Iter1=vecpoint.end()return;vecpoint.erase(Iter1);/将地

48、图上已存在的点(参数为实际位置)删除/擦掉该点(重画所有的点和地图)/voidDefaultMap:SmearPonit(HWNDhwnd,constPOINT&point)HDChdc;hdc=GetDC(hwnd);intn=vecpoint.size();SubPoint(point);if(n=vecpoint.size()/没找到则向量大小不变return;DrawMap(hwnd,hdc);ReleaseDC(hwnd,hdc);for(n=0;nvecpoint.size();n+)/重画所有的点和地图DrawPonit(hwnd,vecpointn);return;/获得所有已

49、点击的点的位置/vectorDefaultMap:GetAllClickPoint()returnvecpoint;/将地图与实际位置之间转换/POINTDefaultMap:GetRealPoint(constPOINT&point)/实际位置转换为地图位置POINTtemppoint;temppoint.x=point.x-6;temppoint.y=point.y-51;/判断点是否在有效区域if(temppoint.x0|temppoint.y700|temppoint.y420)temppoint.x=-1;temppoint.y=-1;returntemppoint;temppoi

50、nt.x+=6;temppoint.y+=51;returntemppoint;/地图位置转换为实际位置/POINTDefaultMap:GetMapPoint(constPOINT&point)POINTtemppoint=point;temppoint.x-=6;temppoint.y-=51;if(temppoint.x0|temppoint.y0|700temppoint.x|420temppoint.y)temppoint.x=-1;/点在无效区域temppoint.y=-1;returntemppoint;returntemppoint;/点在有效区域/五圆形坐标地图类1.头文件/

51、roundmap.h/#pragmaonce#includemap.hclassRoundMap:publicMappublic:RoundMap();voidDrawMap(HWNDhwnd,HDChdc);/画地图POINTFindAroundPoint(constPOINT&);/voidSaveClickPoint();/保存格式为地图中的位置voidDelAllPoint();/清除vecpoin所有点/在地图上画点(参数为实际位置)voidDrawPonit(HWNDhwnd,constPOINT&);/将地图上已存在的点(参数为实际位置)删除voidSmearPonit(HWND

52、hwnd,constPOINT&);voidAddPoint(constPOINT&);/保存POINT(参数为实际位置)到向量voidSubPoint(constPOINT&);/删除POINT(参数为实际位置)到向量vectorGetAllClickPoint();/获得所有已点击的点的位置(实际值)protected:vectormappoint;/2.源文件/roundmap.cpp/#includeroundmap.h/圆形地图/RoundMap:RoundMap()/doinitializationstuffherevectorpoint60(60);intiallpoint120

53、=305,-21,324,-23,344,-23,365,-19,384,-13,402,-6,421,4,437,16,454,28,468,41,482,57,493,74,503,93,509,113,515,132,518,152,520,173,518,193,514,214,510,233,501,254,493,271,481,287,468,304,456,318,439,329,422,342,284,-16,263,-12,246,-4,225,3,210,17,194,28,178,42,166,56,156,74,145,93,137,112,133,131,129,1

54、53,127,173,128,195,132,213,137,233,146,255,155,272,165,290,180,307,194,318,208,331,227,343,244,352,265,360,282,365,303,366,326,369,343,368,368,365,385,360,404,353;for(intn=0;n60;n+)point60n.x=iallpoint2*n;point60n.y=iallpoint2*n+1;for(n=0;n60;n+)point60n.x=point60n.x+21;point60n.y=point60n.y+81;mapp

55、oint=point60;/画地图/voidRoundMap:DrawMap(HWNDhwnd,HDChdc)/n表示线的条数RECTrect;rect.bottom=450;/无效区域（背景区域）rect.left=100;rect.right=740;rect.top=0;HBRUSHhbrush;/擦除背景区域hbrush=CreateSolidBrush(RGB(255,255,255);FillRect(hdc,&rect,hbrush);SelectObject(hdc,GetStockObject(BLACK_PEN);for(intn=0;n60;n+)Ellipse(hdc,

56、mappointn.x-5,mappointn.y-5,mappointn.x+5,mappointn.y+5);/保存删除POINT（在地图位置)到向量/*voidRoundMap:SaveClickPoint()fstreamoutFile(copy.text,ios_base:out);if(!outFile)cerrunabletoopeninputfile:-bailingout!n;return;if(vecpoint.size()=0)return;outFile#Round_Map_NAMEn;/以后有用outFile#vecpoint.size()n;for(intn=0;n

57、vecpoint.size();n+)outFilevecpointn.x;outFile;outFilevecpointn.y;outFilen;return;*/删除所有的点/voidRoundMap:DelAllPoint()if(vecpoint.size()=0)return;vecpoint.clear();return;/找到该点是否有所在区域的值/POINTRoundMap:FindAroundPoint(constPOINT&point)vectorvecroundpoint;POINTtemppoint;vector:iteratorIter;for(intn=-3;n-4

58、;m-)temppoint.x=point.x+m;temppoint.y=point.y+n;vecroundpoint.push_back(temppoint);/获得该点附近的点temppoint.x=point.x+n;temppoint.y=point.y+m;vecroundpoint.push_back(temppoint);/获得该点附近的点Iter=find_first_of(mappoint.begin(),mappoint.end(),vecroundpoint.begin(),vecroundpoint.end(),equal_point();if(Iter=mappo

59、int.end()temppoint.x=-1;temppoint.y=-1;returntemppoint;return(*Iter);/在地图上画点或将地点上以存在的点从地图上删除/voidRoundMap:DrawPonit(HWNDhwnd,constPOINT&point)/在地图上画点(参数为实际位置)/HDChdc;POINTtemppoint,Drawpoint;temppoint.x=-1;temppoint.y=-1;Drawpoint=FindAroundPoint(point);if(Drawpoint.x=temppoint.x&Drawpoint.y=temppoi

60、nt.y)return;AddPoint(point);hdc=GetDC(hwnd);HBRUSHhbrush=CreateSolidBrush(RGB(255,0,0);SelectObject(hdc,hbrush);Ellipse(hdc,(Drawpoint).x-5,(Drawpoint).y-5,(Drawpoint).x+5,(Drawpoint).y+5);DeleteObject(hbrush);ReleaseDC(hwnd,hdc);/将地图上已存在的点（参数为实际位置）重画/voidRoundMap:SmearPonit(HWNDhwnd,constPOINT&poin