TSP問題的遺傳算法求解方案--源程序清單旅行商問題包含算法介紹源程序測試結果講課講稿

1、Good is good, but better carries it.精益求精，善益求善。TSP問題的遺傳算法求解方案-源程序清單旅行商問題，包含算法介紹，源程序，測試結果-TSP問題的遺傳算法求解方案算法的軟件實現4.1開發(fā)環(huán)境介紹本文中的所有算法是在VisualC+6.0的操作平臺上進行開發(fā)的，并結合STL進行編程。1、VisualC+6.0簡介VisualC+6.0是微軟公司最新出品的功能最為強大的可視化開放工具，是計算機界公認的最優(yōu)秀的應用開發(fā)工具之一。Microsoft的基本類庫使得開發(fā)Windows應用程序比以往任何時候都要容易。VisualC+作為一種程序設計語言，它同時也是一

2、個集成開發(fā)工具，提供了軟件代碼自動生成和可視化的資源編輯功能。2、VisualC+6.0的優(yōu)勢(1).擁有強大的編輯環(huán)境。(2).擁有強大的類庫的支持。(3).擁有強大的調試環(huán)境。(4).擁有較強的低層控制能力。(5).擁有強大的幫助系統(tǒng)MSDN的支持。(6).擁有一個高效的編譯器，產生的可執(zhí)行文件體積小巧、運行速度快。3、STL簡介STL（StandardTemplateLibrary），即標準模板庫，是一個具有工業(yè)強度的，高效的C+程序庫。它被容納于C+標準程序庫（C+StandardLibrary）中，是ANSI/ISOC+標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領

3、域里所常用的基本數據結構和基本算法。為廣大C+程序員們提供了一個可擴展的應用框架，高度體現了軟件的可復用性。這種現象有些類似于MicrosoftVisualC+中的MFC（MicrosoftFoundationClassLibrary），或者是BorlandC+Builder中的VCL(VisualComponentLibrary)，但是它比二者具有更強的優(yōu)勢。更加值得一提的是，它具備以下幾個區(qū)別于其它軟件庫的優(yōu)點：(1).經過類屬編程方法精心組織的，可互換的編程模塊能夠提供比傳統(tǒng)組件設開始初始化遺傳算法的相關參數計算每個個體的適應值產生城市對城市進行編碼是否符合終止條件？輸出正確的TSP結果

4、是GEN=GEN+1選擇交叉變異否世代進化輪盤賭選擇普通選擇GXCXOXPMX基于次序的變異基于位置的變異倒位變異圖4.1遺傳算法解TSP的具體流程圖計方法豐富得多的組合方式。(2).類屬編程方法設計也是將來為數據庫，用戶界面等專業(yè)領域開發(fā)組件的基礎。(3).通過使用某些編譯機制并根據不同的算法進行具體的設計，可以在不損失效率的情況下實現對組件的概括。與此形成鮮明對照的是，其它一些具有復雜繼承層次和大量使用虛函數的C+庫結構則通常會降低效率。4.2算法實現的流程圖本設計的具體流程圖如圖4.1所示：4.3算法的各個模塊及其詳細設計思路1城市生成模塊用戶可以點擊鼠標左鍵產生城市，也可以選擇菜單欄的

5、設置城市選項，通過輸入城市數目來隨機生成城市。當然，如果用戶選擇錯了城市，可以在該城市上點擊鼠標右鍵來清除城市。如果用戶要清除所有的城市，可以雙擊鼠標右鍵或選擇菜單欄的結束選項，都可以清除所有的城市。其設計設計思路如圖4.2所示：調用畫圖函數畫點(即設置城市)程序將點的信息存入一個點向量中程序檢測鼠標移動的具體信息按下鼠標左鍵用一個變量記入要產生的城市數按下鼠標右鍵選擇菜單欄的設置城市選項將點向量中要除去的點找出來循環(huán)調用鼠標左鍵點擊消息直到達到要求的城市數選擇菜單欄的結束選項重新畫點向量中的所有點(此時該刪除的點已從點向量中刪除)重新畫地圖(即清除了所有的點)圖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/不進行變異操作種群大?。杭捶N群中所含有的個體數量，選擇一個合理的種群值，不但會使得群體的多樣性增強，防止遺傳算法的“早熟現象”，還會使得遺傳操作收斂得更快。世代數：控制遺傳操作世代

8、進化的次數，合理的世代數能夠使得計算結果的優(yōu)劣程度不同。圖4.6遺傳算法解TSP的參數設置進化設置：根據子染色體與父染色體的關系，進化設置又分為兩種：普通進化：完全模仿自然進化，子染色體可能比父染色體優(yōu)秀，也可能比父染色體差。強制進化：選取子染色體中比父染色體優(yōu)秀的染色體，殺死子染色體中比父染色體差的染色體。使得進化一直朝著優(yōu)秀染色體的方向進化。具體的實現效果如圖4.6所示：4.交叉算子選擇模塊交叉操作是遺傳算法中最重要的一環(huán)，交叉算法的優(yōu)劣將最大限度地影響遺傳算法的結果。本設計先根據國外專家提出的解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:/循環(huán)交叉cycle_crossover(parent1,parent2,child1,child2);break;caseID_GREED_CROSSOVER:/循環(huán)貪心交叉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、體輸出信息顯示模塊為了使程序運行時具體的算法和各種數據信息更加明確化，增加了信息顯示模塊，這樣，在程序運行時用戶可以掌握具體的數據信息，以便對各種算法進行比較。信息顯示模塊包括：計算結果模塊，算法運行時間模塊，所選遺傳算子模塊。下面分別對各個顯示模塊進行討論：計算結果模塊：輸出的信息包括當前鼠標的橫坐標，當前鼠標的縱坐標，這兩個信息是為了用戶設置城市時參考的。城市總數信息是用戶設置的城市數目?？偩嚯x信息是經過計算的TSP問題的最優(yōu)路徑長度，它是屏幕上象素點間的距離。算法運行時間模塊：包括算法啟動前時間，它是用戶設置完城市，進行求解時刻的時間；算法結束時間，它是程序運行完成，正確輸出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交叉類型選擇可供選擇的交叉類型有：部分匹配交叉，順序交叉，循環(huán)交叉，循環(huán)貪心交叉。6.點擊菜單欄變異類型按鈕，可以選擇變異算法，如圖5.7所示，可供選擇的變異類型有：基于次序的變異，基于位置的變

18、異，倒位變異。圖5.7變異類型選擇7然后點擊菜單欄開始，則進行計算，最終結果如圖5.8所示：圖5.8遺傳算法解TSP問題計算結果8.點擊菜單欄結束可以清除所有點，點擊幫助，可以彈出幫助文件。至于圓形地圖的測試過程與直角坐標地圖相似。5.2算法的正確性驗證為了測試算法的正確性，我使用了固定城市測試模塊，該模塊中的城市坐標，城市大小可以預先設置。其中，城市的數目，坐標和最優(yōu)解均可以參照國內外專家的文獻，然后對比本程序計算的結果。如圖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最優(yōu)解517492505515492509519526549491計算平均值有平均最優(yōu)解為：511.5，平均時間為：11.9364s。與參考文獻1，37的部分匹配交叉數據，平均最優(yōu)解為：517.0，平均時間為：31.2s對比可知，本設計的算法符合要求。由于本設計使用的是強制進化方式，所以平均最優(yōu)解和平均時間均有一定的改進。5.3模擬實驗結果與分析5.3.1不同遺傳操作組合的算法為了考察遺傳

20、算法組合優(yōu)化在求解TSP問題中的重要性,本文進行了多種遺傳操作組合的模擬實驗，各種遺傳操作組合成的算法如下:GA0：部分匹配交叉+基于次序的變異GA1：部分匹配交叉+基于位置的變異GA2：部分匹配交叉+倒位變異GA3：順序交叉+基于次序的變異GA4：順序交叉+基于位置的變異GA5：順序交叉+倒位變異GA6：循環(huán)交叉+基于次序的變異GA7：循環(huán)交叉+基于位置的變異GA8：循環(huán)交叉+倒位變異GA9：循環(huán)貪心交叉+基于次序的變異GA10：循環(huán)貪心交叉+基于位置的變異GA11：循環(huán)貪心交叉+倒位變異表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，群體規(guī)模為100，交叉概率為0.8，變異概率為0.1，群體更新100代結束，采用強制進化方式進化，每個算法采集了10組數據。其中，TSP旅程長度為屏幕上象素點之間的距離，時間為算法所消耗的CPU時間。30個城市的坐標如表5.1所示：對每個算法采集的數據，計算其平均結果，表5.2中的所有數據都是經過10次測試得出的統(tǒng)計平均結果。表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的優(yōu)化結果無大的差異，這說明變異算子在優(yōu)化過程中所起的作用相對小一些。事實上，幾種算法結果的相對一致性,很大程度上是變異概率取的較小,使變異在整個搜索過程中發(fā)生次數甚微造成的。這也符合自然進化的

24、規(guī)律，畢竟，變異的發(fā)生概率是極其微小的。2.排除變異算子所帶來的差異，只比較交叉算子可知，循環(huán)交叉算子的效果最差，這主要是因為經過循環(huán)之后，有可能到最后才完成循環(huán)。也就是說，循環(huán)了一周，子代和父代卻沒有大的改變。但由于進行了一系列循環(huán)，耗費了不少時間，因此，循環(huán)交叉所花費的時間也比較多。3.通過改進的交叉算子(循環(huán)貪心交叉)和其它算子作比較可知，雖然改進的交叉算子所求的旅程長度有一定的改觀，但耗費了不少時間。這主要是因為改進的交叉算子不但要循環(huán)，還要比較相鄰城市之間的距離，并且所比較的城市都被擴展時，還要隨機選擇一個城市直到它不在所擴展的城市中或者所有的城市都被擴展，因此花費了大量的時間。因此

25、對于改進的交叉算子不宜處理太多城市的TSP問題。4.總體來說，順序交叉比較穩(wěn)定，沒有太多隨機選擇的情況，因此，對于多城市問題，不失為一種較理想的選擇。5.4改進算法與原算法的比較對于下面各比較算法，分別進行了計算機模擬實驗，計算中采用的有關數據如下：城市數為30，群體規(guī)模為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改進循環(huán)交叉算法與循環(huán)交叉算法的數值比較對于循環(huán)交叉測試的十組數據如下：時間(s)15.67214.82814.7814.

27、76515.68816.84414.65015.84414.68715.954最優(yōu)解684717705715692709669676689691對于改進的循環(huán)交叉測試的十組數據如下：時間(s)11.96911.70312.32811.76512.18812.84411.25011.84410.48710.954最優(yōu)解615621640632609651603621630612對于循環(huán)交叉平均最優(yōu)解為：694.7，平均時間為：15.3712s。對于改進循環(huán)交叉平均最優(yōu)解為：623.4，平均時間為：11.7332s。通過對比可知，改進后的算法明顯優(yōu)于改進前的算法。5.4.2改進循環(huán)貪心交叉算法與循

28、環(huán)貪心交叉算法的數值比較對于改進的循環(huán)貪心交叉測試的十組數據如下：時間(s)12.68713.35912.9312.42212.50012.28112.93811.50012.85912.953最優(yōu)解610616643644655643590699613617對于循環(huán)貪心交叉測試的十組數據如下：時間(s)14.25013.62514.75014.17213.75014.50013.40614.31213.98514.734最優(yōu)解580614626594624651626570694586對于改進的循環(huán)貪心交叉平均最優(yōu)解為：633.0，平均時間為：12.6429s。對于循環(huán)貪心交叉平均最優(yōu)解為：

29、616.5，平均時間為：14.1484s。通過對比可知，改進后的算法時間上明顯優(yōu)于改進前的算法。主要是減少了隨機查找數據的時間，但由于改進后的算法是循環(huán)查找未擴展的城市，因此使得種群的多樣性減少了，即使得平均最優(yōu)解要比改進前差一些，但對于大量城市的TSP問題來說，節(jié)省時間是很值得考慮的。6結論TSP是一個具有廣泛的應用背景和重要理論價值的組合優(yōu)化問題，它已經被證明屬NP難題。TSP搜索空間隨著城市數的增加而增大，在龐大的空間中尋找最優(yōu)解，對于現有的常規(guī)方法和現有的計算工具而言，存在著諸多的困難。借助遺傳算法的搜索能力解決TSP問題是很自然的想法。本設計在深入分析和研究遺傳算法基本理論與方法的基

30、礎上，不但編程實現了國內外專家提出的一些優(yōu)秀的算法，而且結合具體的編程情況，對其中的一些算法作了必要的改進。最后，本設計對各種算法的組合進行了實驗，并且對各種算法結果進行了比較和分析。在本文研究基礎上，還可以進一步開拓以下幾個方向的研究工作:1.將遺傳算法運用于大規(guī)模的旅行商問題；2.將許多實際應用問題(如印制電路板的鉆孔路線方案、連鎖店的貨物陪送路線等)建模為TSP問題，并應用遺傳算法來解決；3.如何獲得更好的性能是遺傳算法研究中的重要課題。如何在保證求解質量的同時降低時間的開銷，如何針對具體問題尋找優(yōu)化的并行計算策略和群體劃分策略，也是遺傳算法中需要進一步深入研究的重要課題。遺傳算法是新發(fā)

31、展起來的一門學科，各種理論、方法尚未成熟，需要進一步地發(fā)展和完善，但它已為解決許多復雜問題提供了希望。盡管在遺傳算法的研究和應用過程中會出現許多難題，同時也會產生許多不同的算法設計觀點，然而，目前遺傳算法的各種應用實踐已經展現出了其優(yōu)異的性能和巨大的發(fā)展?jié)摿?，它的發(fā)展前景激勵著各類專業(yè)技術人員把遺傳算法的理論和方法運用于自己的專業(yè)領域中。隨著研究工作的進一步深入和發(fā)展，遺傳算法必將在智能計算領域中起到關鍵的作用。程序核心代碼一資源類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);/創(chuàng)建畫筆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;/判斷點是否在有效區(qū)域/-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;/判斷點是否在有效區(qū)域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;/判斷點是否在有效區(qū)域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;/點在無效區(qū)域temppoint.y=-1;returntemppoint;returntemppoint;/點在有效區(qū)域/五圓形坐標地圖類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;/無效區(qū)域（背景區(qū)域）rect.left=100;rect.right=740;rect.top=0;HBRUSHhbrush;/擦除背景區(qū)域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;/找到該點是否有所在區(qū)域的值/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