整理為word格式整理為word格式整理為word格式人工智能課程大作業——基于回溯搜索的地圖著色班級：20110616學號：2011061624姓名：曾江東2014年11月26號整理為word格式整理為word格式整理為word格式摘要：人工智能是20世紀50年代中期興起的一門邊緣學科。人工智能領域中，地圖著色問題是一典型的優化的問題。由它引發的“四色猜想”是全世界的難題，直到1975年由三臺超高速電子計算機，經過1200小時的計算才終于正明了“四色定理”。這是世界上最長的證明。本文并不是想證明，而只是想基于回溯法來給地圖著色，求出最少用色。本文著重介紹利用MFC設計界面來對中國省級地圖著色進行演示。計算機視覺是研究為完成在復雜的環境中運動和在復雜的場景中識別物體所需要哪些視覺信息，以及如何從圖像中獲取這些信息的科學領域。關鍵詞：地圖著色；回溯搜索；MFC本組成員：曾江東，楊星，俞洋本人分工：本人主要基于回溯搜索算法的代碼的編寫。1引言人，現在社會的發展中心都離不開這個人字，人是發展的本體，人類的自然智能伴隨到處都是，本次實驗研究什么是人工智能，人工智能又能如何的運用在生活和學習中。

人工智能(Artificial

Intelligence)

，英文縮寫為AI。它是研究、開發用于模擬、延伸和擴展人的智能的理論、方法、技術及應用系統的一門新的技術科學。

人工智能（Artificial

Intelligence，AI）是研究、開發用于模擬、延伸和擴展人的智能的理論、方法、技術及應用系統的一門新的技術科學。人工智能從誕生以來，理論和技術日益成熟，應用領域也不斷擴大，但沒有一個統一的定義。人工智能是計算機科學的一個分支，它企圖了解智能的實質，并生產出一種新的能以人類智能相似的方式做出反應的智能機器，該領域的研究包括機器人、語言識別、圖像識別、自然語言處理和專家系統等。

本次實驗研究的是關于人工智能中搜索的功能，實現用回溯法對地圖不同地區的著色問題，地圖上有不同國家（不同區域），每個國家都與其他一些國家鄰接。現要求對地圖著色，使所有的國家與它的鄰接的國家有不同的顏色。通常由四種顏色就已足夠。地圖著色的算法比較多，但是切實可行的算法很少，回溯法在地圖區域較大，鄰接關系復雜的情況下，回溯次數將會大大增多，嚴重影響了程序執行效率。不過本次作業則是采用修改后的回溯法，在一定的條件下，執行效率還是很高。

本次實驗是要對中國地圖中的省級行政區最多使用四種顏色來進行著色，編程實現回溯算法用于地圖自動著色。我負責得是改進的回溯算法的代碼的編寫。2算法原理與系統設計2.1

回溯算法原理要解決地圖著色的問題，本文采用的是回溯法。回溯法是一種系統地搜索問題解的搜索算法。回溯法遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。

其基本步驟：1.定義一個解空間，它包含問題的解。

2.利用適于\o"搜索"搜索的方法組織解空間。3.利用\o"深度優先法"深度優先法搜索解空間。4.利用\o"限界函數"限界函數避免移動到不可能產生解的子空間。而地圖著色的問題可以處理為：如果把每一個區域收縮為一個頂點，把相鄰兩個區域用一條邊相連接，就可以把一個區域圖抽象為一個平面圖。則著色問題變成了對解問題的最優搜索算法的實現。我利用分枝定界法對候選解進行系統檢查，能以較高效率的找到最優解。2.2

詳細設計地圖著色功能流程圖如圖2-1所示：整理為word格式整理為word格式整理為word格式圖2-1地圖顏色確定流程圖在窗口上著色時，用到的是廣度算法的思想，搜索遍歷一個省區域內的所有像素點。整理為word格式整理為word格式整理為word格式著色是各省漸變著色，感觀上能看見是從省中間向邊緣擴散。在對一個省進行著色時，用深度優先的算法實現，共用4種顏色，分別是紅，綠，藍，黃。每次給當前省份4種顏色中的一種，然后判斷是否合理，如不合理則換另一種顏色值，根據圖的4色定理一定能從4種顏色中找到一個合適的顏色，直到當前省份找到合適顏色后，進行下個省份的判斷。在著色時，以這個省份的中心點為基準，由環形向外進行著色，采用深度優先搜索算法，并根據標記的二維數組來進行邊界檢測，以保證著色的準確性。在本次設計中，用到了關于地圖信息的兩個文件，一個是地圖標記點文檔，如圖2-2所示。它里邊存儲的是地圖的每個省份的中間點的像素坐標，如“新疆

125

123”，代表的是新疆在地圖中的坐標位置，一共32個省。另一個是相鄰之間的關系的文檔，如圖2-3所示。它里邊存儲的是省與省之間的相鄰接關系，比如“13”，代表省1，省3相鄰。這里的0和1是根據node表中的順序得來的，0代表新疆，1代表西藏。當兩個省相臨時，他們不能著相同的顏色。程序不要求用戶輸入，運行程序后自動從文件中讀取地圖信息，并加載原始地圖，出現可操作的可視化界面。圖2-2地圖標記點文件圖2-3相鄰之間的關系文件3系統實現3-1回溯算法我采用的是深度優先搜索算法，它就是把最近剛產生的結點優先擴展，直到達到一定的深度限制。若未找到目標或無法再擴展時，再回溯到另一個結點繼續擴展。它類似于樹的先根搜索，是樹的先根搜索的推廣。3-2代碼實現地圖涂色用到深度優先搜索算法voidCMyDlg::On_Color(){ //TODO:Addyourcontrolnotificationhandlercodehere ALgraphG; inti,s,d;listnode*p,*q; ifstreamifile("C:\\地圖(鄰接表)\\text2.txt",ios::in);整理為word格式整理為word格式整理為word格式 G.vexnum=32; G.arcnum=68; for(i=1;i<=32;i++) { G.vexs[i].first=NULL; } for(i=1;i<=68;i++){ ifile>>s>>d; p=newlistnode; p->adjvex=d; p->next=G.vexs[s].first; G.vexs[s].first=p; q=newlistnode; q->adjvex=s; q->next=G.vexs[d].first; G.vexs[d].first=q;} ifstreamifile1("C:\\地圖(鄰接表)\\坐標1.txt",ios::in); for(i=0;i<32;i++) { ifile1>>P[i].x>>P[i].y; } intj,a[MAXVER]; intcolor[MAXVER]; color[0]=1; for(i=0;i<MAXVER;i++) a[i]=0; for(i=1;i<MAXVER;i++) color[i]=1; for(i=1;i<=32;i++) { intcount=1; listnode*p; p=G.vexs[i].first; while(p!=NULL) { if(i<p->adjvex) p=p->next; else { a[count]=p->adjvex;整理為word格式整理為word格式整理為word格式 count++; p=p->next; } } if(count>1) { intt=1; for(j=1;j<=n;j++) { intflag=1; for(t=1;t<count;t++) { if(j==color[a[t]]) { flag=0; break; } } if(flag==1) { color[i]=j; break; } } } } for(i=1;i<=32;i++) { CDC*pdc=GetDC(); Color(P[i-1].x,P[i-1].y,c[color[i]-1],pdc); }}4實驗或測試結果程序運行后出現如下界面：整理為word格式整理為word格式整理為word格式圖4-1地圖初始化點擊著色后，開始著色：圖4-2地圖著色中整理為word格式整理為word格式整理為word格式圖4-3地圖著色完成 在調試過程中，我們發現地圖著色非常緩慢，我們分析是由于我們是對點像素的遍歷，而圖的范圍又非常廣，導致遍歷速度很慢，程序效率不快。5結論 在這次利用回溯搜索算法實現中國地圖著色的實驗中，我負責的是回溯搜索算法的編寫，其實基本的回溯算法，是一種系統地搜索問題的解的方法。但是，又怎么利用它實現地圖的著色呢？我利用的是將圖著色的問題具體化，把每一個區域收縮為一個頂點，把相鄰兩個區域用一條邊相連接，就可以把一個區域圖抽象為一個平面圖，這樣就可以用到遍歷了。 雖然在編寫代碼的時候遇到了很多問題，但是更讓人煩躁的是，調試時，程序老是出現錯誤，這讓我們相當沮喪，后來，通過小組成員不斷地努力，終于排除所有的問題，程序成功運行，這還是讓我們很有成就感的。參考文獻[1]

梁述明，陸忠武．四