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

人工智能課程項(xiàng)目報(bào)告人工智能課程大作業(yè)-—鑒于回溯搜尋的地圖著色班級(jí)：20110616學(xué)號(hào):2011061624姓名：曾江東2014年11月26號(hào)0人工智能課程項(xiàng)目報(bào)告綱要：人工智能是20世紀(jì)50年月中期盛行的一門邊沿學(xué)科。人工智能領(lǐng)域中，地圖著色問題是一典型的優(yōu)化的問題。由它引起的“四色猜想”是全球的難題，直到1975年由三臺(tái)超高速電子計(jì)算機(jī)，經(jīng)過1200小時(shí)的計(jì)算才終于正了然“四色定理”.這是世界上最長的證明。本文其實(shí)不是想證明,而不過想鑒于回溯法來給地圖著色，求出最少用色.本文側(cè)重介紹利用MFC設(shè)計(jì)界面來對(duì)中國省級(jí)地圖著色進(jìn)行演示。計(jì)算機(jī)視覺是研究為達(dá)成在復(fù)雜的環(huán)境中運(yùn)動(dòng)和在復(fù)雜的場(chǎng)景中辨別物體所需要哪些視覺信息，以及怎樣從圖像中獲得這些信息的科學(xué)領(lǐng)域.重點(diǎn)詞:地圖著色；回溯搜尋；MFC本構(gòu)成員：曾江東，楊星，俞洋自己分工：自己主要鑒于回溯搜尋算法的代碼的編寫。前言人，此刻社會(huì)的發(fā)展中心都離不開這個(gè)人字，人是發(fā)展的本體，人類的自然智能陪伴各處都是，本次實(shí)驗(yàn)研究什么是人工智能，人工智能又能怎樣的運(yùn)用在生活和學(xué)習(xí)中。人工智能（ArtificialIntelligence)，英文縮寫為AI。它是研究、開發(fā)用于模擬、延長和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能（ArtificialIntelligence，AI）是研究、開發(fā)用于模擬、延長和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué).人工智能從出生以來,理論和技術(shù)日趨成熟，應(yīng)用領(lǐng)域也不停擴(kuò)大，但沒有一個(gè)一致的定義。人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它妄圖認(rèn)識(shí)智能的實(shí)質(zhì),并生產(chǎn)出一種新的能以人類智能相像的方式做出反響的智能機(jī)器，該領(lǐng)域的研究包含機(jī)器人、語言辨別、圖像辨別、自然語言辦理和專家系統(tǒng)等.本次實(shí)驗(yàn)研究的是對(duì)于人工智能中搜尋的功能,實(shí)現(xiàn)用回溯法對(duì)地圖不一樣地域的著色問題，地圖上有不一樣國家（不一樣地區(qū)），每個(gè)國家都與其余一些國家毗鄰?，F(xiàn)要求對(duì)地圖著色，使全部的國家與它的毗鄰的國家有不一樣的顏色.往常由四種顏色就已足夠。地圖著色的算法比許多，可是確實(shí)可行的算法極少,回溯法在地圖地區(qū)較大,毗鄰關(guān)系復(fù)雜的狀況下，回溯次數(shù)將會(huì)大大增加，嚴(yán)重影響了程序履行效率?？墒潜敬巫鳂I(yè)則是采納改正后的回溯法，在必定的條件下,履行效率仍是很高。本次實(shí)驗(yàn)是要對(duì)中國地圖中的省級(jí)行政區(qū)最多使用四種顏色來進(jìn)行著色,編程實(shí)現(xiàn)回溯算法用于地圖自動(dòng)著色。我負(fù)責(zé)得是改良的回溯算法的代碼的編寫.算法原理與系統(tǒng)設(shè)計(jì)2.1回溯算法原理要解決地圖著色的問題，本文采納的是回溯法。回溯法是一種系統(tǒng)地搜尋問題解的搜尋算法。回溯法遞歸地在解空間中搜尋,直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。其基本步驟：1。定義一個(gè)解空間，它包含問題的解。2。利用適于搜尋的方法組織解空間。3.利用深度優(yōu)先法搜尋解空間.4。利用限界函數(shù)防止挪動(dòng)到不行能產(chǎn)生解的子空間。而地圖著色的問題能夠辦理為：假如把每一個(gè)地區(qū)縮短為一個(gè)極點(diǎn)，把相鄰兩個(gè)地區(qū)用一條邊相連結(jié),就能夠把一個(gè)地區(qū)圖抽象為一個(gè)平面圖.則著色問題變?yōu)榱藢?duì)解問題的最優(yōu)搜尋算法的實(shí)現(xiàn).我利用分枝定界法對(duì)候選解進(jìn)行系統(tǒng)檢查,能以較高效率的找到最優(yōu)解。2。2詳盡設(shè)計(jì)地圖著色功能流程圖如圖2—1所示:1人工智能課程項(xiàng)目報(bào)告開始Colr[0]=0,i=1,colr=0,pl=nulli<n否返回是Cplr=0Pl=結(jié)點(diǎn)i的鏈表Pl不空是Pl.index對(duì)應(yīng)++i的結(jié)點(diǎn)顏色Pl=pl->next否否==colr是Pl不空是colr++否Colr[i]=colr結(jié)束圖2-1地圖顏色確立流程圖在窗口上著色時(shí)，用到的是廣度算法的思想,搜尋遍歷一個(gè)省地區(qū)內(nèi)的全部像素點(diǎn).2人工智能課程項(xiàng)目報(bào)告著色是各省漸變著色，感觀上能看見是從省中間向邊沿?cái)U(kuò)散。在對(duì)一個(gè)省進(jìn)行著色時(shí),用深度優(yōu)先的算法實(shí)現(xiàn)，共用4種顏色,分別是紅，綠，藍(lán)，黃。每次給目前省份4種顏色中的一種，而后判斷能否合理，如不合理則換另一種顏色值，依據(jù)圖的4色定理必定能從4種顏色中找到一個(gè)適合的顏色，直到目前省份找到適合顏色后，進(jìn)行下個(gè)省份的判斷.在著色時(shí)，以這個(gè)省份的中心點(diǎn)為基準(zhǔn)，由環(huán)形向外進(jìn)行著色,采納深度優(yōu)先搜尋算法，并依據(jù)標(biāo)志的二維數(shù)組來進(jìn)行界限檢測(cè)，以保證著色的正確性。在本次設(shè)計(jì)中，用到了對(duì)于地圖信息的兩個(gè)文件,一個(gè)是地圖標(biāo)志點(diǎn)文檔，如圖2—2所示。它里邊儲(chǔ)存的是地圖的每個(gè)省份的中間點(diǎn)的像素坐標(biāo)，如“新疆125123”，代表的是新疆在地圖中的坐標(biāo)地點(diǎn)，一共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)轉(zhuǎ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:AddyourcontrolnotificationhandlercodehereALgraphG;inti，s,d;listnode＊p，＊q；ifstreamifile("C：地圖（毗鄰表)\\text2.txt”，ios：：in)；3人工智能課程項(xiàng)目報(bào)告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；4人工智能課程項(xiàng)目報(bào)告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);｝}實(shí)驗(yàn)或測(cè)試結(jié)果程序運(yùn)轉(zhuǎn)后出現(xiàn)以下界面：5人工智能課程項(xiàng)目報(bào)告圖4-1地圖初始化點(diǎn)擊著色后，開始著色:圖4-2地圖著色中6人工智能課程項(xiàng)目報(bào)告圖4—3地圖著色達(dá)成在調(diào)試過程中，我們發(fā)現(xiàn)地圖著色特別遲緩,我們剖析是因?yàn)槲覀兪菍?duì)點(diǎn)像素的遍歷，而圖的范圍又特別廣，致使遍歷速度很慢，程序效率不快。結(jié)論在此次利用回溯搜尋算法實(shí)現(xiàn)中國地圖著色的實(shí)驗(yàn)中，我負(fù)責(zé)的是回溯搜尋算法的編寫，其實(shí)基本的回溯算法，是一種系統(tǒng)地搜尋問題的解的方法.可是，又怎么利用它實(shí)現(xiàn)地圖的著色呢?我利用的是將圖著色的問題詳細(xì)化，把每一個(gè)地區(qū)縮短為一個(gè)極點(diǎn)，把相鄰兩個(gè)地區(qū)用一條邊相連結(jié)，就能夠把一個(gè)地區(qū)圖抽象為一個(gè)平面圖,這樣就能夠用到遍歷了.固然在編寫代碼的時(shí)候碰到了好多問題，可是更讓人浮躁的是，調(diào)試時(shí)，程序總是出現(xiàn)錯(cuò)誤,這讓我們相當(dāng)喪氣，以后,經(jīng)過小構(gòu)成員不停地努力,終于清除全部的問題，程序成功運(yùn)轉(zhuǎn),這仍是讓我們很有成就感的。參照文件[1]梁述明，陸忠