人工智能大作業(yè)報(bào)告

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

人工智能(Artificial

Intelligence)

，英文縮寫為AI。它是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。

人工智能（Artificial

Intelligence，AI）是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能從誕生以來，理論和技術(shù)日益成熟，應(yīng)用領(lǐng)域也不斷擴(kuò)大，但沒有一個(gè)統(tǒng)一的定義。人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應(yīng)的智能機(jī)器，該領(lǐng)域的研究包括機(jī)器人、語言識(shí)別、圖像識(shí)別、自然語言處理和專家系統(tǒng)等。

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

本次實(shí)驗(yàn)是要對(duì)中國地圖中的省級(jí)行政區(qū)最多使用四種顏色來進(jìn)行著色，編程實(shí)現(xiàn)回溯算法用于地圖自動(dòng)著色。我負(fù)責(zé)得是改進(jìn)的回溯算法的代碼的編寫。2算法原理與系統(tǒng)設(shè)計(jì)2.1

回溯算法原理要解決地圖著色的問題，本文采用的是回溯法?；厮莘ㄊ且环N系統(tǒng)地搜索問題解的搜索算法?；厮莘ㄟf歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。

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

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

詳細(xì)設(shè)計(jì)地圖著色功能流程圖如圖2-1所示：圖2-1地圖顏色確定流程圖在窗口上著色時(shí)，用到的是廣度算法的思想，搜索遍歷一個(gè)省區(qū)域內(nèi)的所有像素點(diǎn)。著色是各省漸變著色，感觀上能看見是從省中間向邊緣擴(kuò)散。在對(duì)一個(gè)省進(jìn)行著色時(shí)，用深度優(yōu)先的算法實(shí)現(xiàn)，共用4種顏色，分別是紅，綠，藍(lán)，黃。每次給當(dāng)前省份4種顏色中的一種，然后判斷是否合理，如不合理則換另一種顏色值，根據(jù)圖的4色定理一定能從4種顏色中找到一個(gè)合適的顏色，直到當(dāng)前省份找到合適顏色后，進(jìn)行下個(gè)省份的判斷。在著色時(shí)，以這個(gè)省份的中心點(diǎn)為基準(zhǔn)，由環(huán)形向外進(jìn)行著色，采用深度優(yōu)先搜索算法，并根據(jù)標(biāo)記的二維數(shù)組來進(jìn)行邊界檢測(cè)，以保證著色的準(zhǔn)確性。在本次設(shè)計(jì)中，用到了關(guān)于地圖信息的兩個(gè)文件，一個(gè)是地圖標(biāo)記點(diǎn)文檔，如圖2-2所示。它里邊存儲(chǔ)的是地圖的每個(gè)省份的中間點(diǎn)的像素坐標(biāo)，如“新疆

125

123”，代表的是新疆在地圖中的坐標(biāo)位置，一共32個(gè)省。另一個(gè)是相鄰之間的關(guān)系的文檔，如圖2-3所示。它里邊存儲(chǔ)的是省與省之間的相鄰接關(guān)系，比如“13”，代表省1，省3相鄰。這里的0和1是根據(jù)node表中的順序得來的，0代表新疆，1代表西藏。當(dāng)兩個(gè)省相臨時(shí)，他們不能著相同的顏色。程序不要求用戶輸入，運(yùn)行程序后自動(dòng)從文件中讀取地圖信息，并加載原始地圖，出現(xiàn)可操作的可視化界面。圖2-2地圖標(biāo)記點(diǎn)文件圖2-3相鄰之間的關(guān)系文件3系統(tǒng)實(shí)現(xiàn)3-1回溯算法我采用的是深度優(yōu)先搜索算法，它就是把最近剛產(chǎn)生的結(jié)點(diǎn)優(yōu)先擴(kuò)展，直到達(dá)到一定的深度限制。若未找到目標(biāo)或無法再擴(kuò)展時(shí)，再回溯到另一個(gè)結(jié)點(diǎn)繼續(xù)擴(kuò)展。它類似于樹的先根搜索，是樹的先根搜索的推廣。3-2代碼實(shí)現(xiàn)地圖涂色用到深度優(yōu)先搜索算法voidCMyDlg::On_Color(){ //TODO:Addyourcontrolnotificationhandlercodehere ALgraphG; inti,s,d;listnode*p,*q; ifstreamifile("C:\\地圖(鄰接表)\\text2.txt",ios::in); 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:\\地圖(鄰接表)\\坐標(biāo)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; 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實(shí)驗(yàn)或測(cè)試結(jié)果程序運(yùn)行后出現(xiàn)如下界面：圖4-1地圖初始化點(diǎn)擊著色后，開始著色：圖4-2地圖著色中圖4-3地圖著色完成 在調(diào)試過程中，我們發(fā)現(xiàn)地圖著色非常緩慢，我們分析是由于我們是對(duì)點(diǎn)像素的遍歷，而圖的范圍又非常廣，導(dǎo)致遍歷速度很慢，程序效率不快。5結(jié)論 在這次利用回溯搜索算法實(shí)現(xiàn)中國地圖著色的實(shí)驗(yàn)中，我負(fù)責(zé)的是回溯搜索算法的編寫，其實(shí)基本的回溯算法，是一種系統(tǒng)地搜索問題的解的方法。但是，又怎么利用它實(shí)現(xiàn)地圖的著色呢？我利用的是將圖著色的問題具體化，把每一個(gè)區(qū)域收縮為一個(gè)頂點(diǎn)，把相鄰兩個(gè)區(qū)域用一條邊相連接，就可以把一個(gè)區(qū)域圖抽象為一個(gè)平面圖，這樣就可以用到遍歷了。 雖然在編寫代碼的時(shí)候遇到了很多問題，但是更讓人煩躁的是，調(diào)試時(shí)，程序老是出現(xiàn)錯(cuò)誤，這讓我們相當(dāng)沮喪，后來，通過小組成員不斷地努力，終于排除所有的問題，程序成功運(yùn)行，這還是讓我們很有成就感的