人工智能課程設(shè)計報告-羅馬尼亞度假問題

1、人工智能課程設(shè)計報告 課 程:人工智能能課程設(shè)計計報告 班 級: 姓 名: 學(xué) 號: 指導(dǎo)教師:趙曼 2015年年11月 - 49 -人工智能課課程設(shè)計報報告課程背景 人工智能（AArtifficiaal Inntellligennce），英英文縮寫為為AI。它它是研究、開發(fā)用于于模擬、延延伸和擴(kuò)展展人的智能能的理論、方法、技技術(shù)及應(yīng)用用系統(tǒng)的一一門新的技技術(shù)科學(xué)。 人工智智能是計算算機(jī)科學(xué)的的一個分支支，它企圖圖了解智能能的實質(zhì)，并并生產(chǎn)出一一種新的能能以人類智智能相似的的方式做出出反應(yīng)的智智能機(jī)器，該該領(lǐng)域的研研究包括機(jī)機(jī)器人、語語言識別、圖像識別別、自然語語言處理和和專家系統(tǒng)統(tǒng)等。人工工

2、智能從誕誕生以來，理理論和技術(shù)術(shù)日益成熟熟，應(yīng)用領(lǐng)領(lǐng)域也不斷斷擴(kuò)大，可可以設(shè)想，未未來人工智智能帶來的的科技產(chǎn)品品，將會是是人類智慧慧的“容器”。人工智能是是對人的意意識、思維維的信息過過程的模擬擬。人工智智能不是人人的智能，但但能像人那那樣思考、也可能超超過人的智智能。人工智能是是一門極富富挑戰(zhàn)性的的科學(xué)，從從事這項工工作的人必必須懂得計計算機(jī)知識識，心理學(xué)學(xué)和哲學(xué)。人工智能能是包括十十分廣泛的的科學(xué)，它它由不同的的領(lǐng)域組成成，如機(jī)器器學(xué)習(xí)，計計算機(jī)視覺覺等等，總總的說來，人人工智能研研究的一個個主要目標(biāo)標(biāo)是使機(jī)器器能夠勝任任一些通常常需要人類類智能才能能完成的復(fù)復(fù)雜工作。但不同的的時代、不

3、不同的人對對這種“復(fù)雜工作作”的理解是是不同的。人工智能是是計算機(jī)學(xué)學(xué)科的一個個分支，二二十世紀(jì)七七十年代以以來被稱為為世界三大大尖端技術(shù)術(shù)之一（空空間技術(shù)、能源技術(shù)術(shù)、人工智智能）。也也被認(rèn)為是是二十一世世紀(jì)三大尖尖端技術(shù)（基基因工程、納米科學(xué)學(xué)、人工智智能）之一一。這是因因為近三十十年來它獲獲得了迅速速的發(fā)展，在在很多學(xué)科科領(lǐng)域都獲獲得了廣泛泛應(yīng)用，并并取得了豐豐碩的成果果，人工智智能已逐步步成為一個個獨立的分分支，無論論在理論和和實踐上都都已自成一一個系統(tǒng)。人工智能是是研究使計計算機(jī)來模模擬人的某某些思維過過程和智能能行為（如如學(xué)習(xí)、推推理、思考考、規(guī)劃等等）的學(xué)科科，主要包包括計算機(jī)機(jī)

4、實現(xiàn)智能能的原理、制造類似似于人腦智智能的計算算機(jī)，使計計算機(jī)能實實現(xiàn)更高層層次的應(yīng)用用。人工智智能將涉及及到計算機(jī)機(jī)科學(xué)、心心理學(xué)、哲哲學(xué)和語言言學(xué)等學(xué)科科?？梢哉f說幾乎是自自然科學(xué)和和社會科學(xué)學(xué)的所有學(xué)學(xué)科，其范范圍已遠(yuǎn)遠(yuǎn)遠(yuǎn)超出了計計算機(jī)科學(xué)學(xué)的范疇，人人工智能與與思維科學(xué)學(xué)的關(guān)系是是實踐和理理論的關(guān)系系，人工智智能是處于于思維科學(xué)學(xué)的技術(shù)應(yīng)應(yīng)用層次，是是它的一個個應(yīng)用分支支。從思維維觀點看，人人工智能不不僅限于邏邏輯思維，要要考慮形象象思維、靈靈感思維才才能促進(jìn)人人工智能的的突破性的的發(fā)展，數(shù)數(shù)學(xué)常被認(rèn)認(rèn)為是多種種學(xué)科的基基礎(chǔ)科學(xué)，數(shù)數(shù)學(xué)也進(jìn)入入語言、思思維領(lǐng)域，人人工智能學(xué)學(xué)科也必須須

5、借用數(shù)學(xué)學(xué)工具，數(shù)數(shù)學(xué)不僅在在標(biāo)準(zhǔn)邏輯輯、模糊數(shù)數(shù)學(xué)等范圍圍發(fā)揮作用用，數(shù)學(xué)進(jìn)進(jìn)入人工智智能學(xué)科，它它們將互相相促進(jìn)而更更快地發(fā)展展。題目一：羅羅馬利亞度度假問題一. 問題題描述分別用代價價一致的寬寬度優(yōu)先、有限制的的深度優(yōu)先先（預(yù)設(shè)搜搜索層次）、貪婪算法法和A*算法求解解“羅馬利亞亞度假問題題”。即找到從從初始地點點 Araad到 目目的地點 Buchharesst 的一條路路徑。要求：分別用文件件存儲地圖圖和啟發(fā)函函數(shù)表，用用生成節(jié)點點數(shù)比較幾幾種算法在在問題求解解時的效率率，并列表給出出結(jié)果。數(shù)據(jù)如下：1、地圖2、啟發(fā)函函數(shù)值A(chǔ)rad 366 Mehaadia 241 Buchhares

6、st 0 Neammt 2334 Craiiova 160 Oraddea 3380 Dobeerta 242Pitessti 1100 Eforrie 1161 Rimmmicu_Vikeea 1993 Fagaaras 176 Sibiiu 2553 Glurrgiu 77Timissoaraa 3299 Hirssova 151 Urziicenii 80 Iasii 2266 Vasllui 1199 Lugooj 2444 Zeriind 33743、地圖數(shù)數(shù)據(jù)表0 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000

7、 1440 10000 1188 10000 10000 11000 10000 10000 7551000 0 10000 10000 11000 10000 75 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 70 100001000 10000 0 10000 11000 10000 10000 1001 10000 10000 2211 10000 900 10000 11000 85 10000 10000 11000 100001000 10000 10000 0 10000 11000 1000

8、0 10000 10000 11000 10000 10000 10000 11000 10000 10000 877 10000 10000 110001000 10000 10000 10000 00 10000 1200 138 10000 1466 10000 10000 11000 10000 10000 10000 11000 10000 10000 100001000 10000 10000 10000 11000 0 10000 10000 11000 10000 10000 1551 10000 10000 11000 10000 10000 10000 11000 7110

9、00 75 10000 10000 1120 10000 0 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 100001000 10000 1011 10000 1388 10000 10000 0 10000 997 10000 10000 10000 11000 10000 10000 10000 11000 10000 100001000 10000 10000 10000 11000 10000 10000 10000 00 11000 10000 10000 10000 11000 86

10、 10000 10000 11000 10000 100001000 10000 10000 10000 1146 10000 10000 977 10000 0 10000 880 10000 11000 10000 10000 10000 11000 10000 100001000 10000 2111 10000 10000 10000 11000 10000 10000 10000 00 999 10000 10000 10000 11000 10000 10000 10000 11000140 10000 10000 10000 11000 151 10000 10000 10000

11、 880 99 0 10000 10000 10000 11000 10000 10000 10000 110001000 10000 90 10000 10000 11000 10000 10000 10000 11000 10000 10000 0 10000 11000 10000 10000 10000 11000 10000118 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 0 10000 10000 11000 10000 1111 100001000 10000 10000 100

12、00 11000 10000 10000 10000 886 10000 10000 10000 11000 10000 0 988 10000 11000 10000 100001000 10000 85 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 98 0 10000 10000 10000 110001000 10000 10000 877 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 10000 0 922 100

13、00 100001000 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 992 0 10000 100001000 70 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 111 10000 10000 10000 11000 0 1000075 10000 10000 10000 11000 71 10000 10000 11000 10000 10000 10000 11000

14、 10000 10000 10000 11000 10000 10000 0二.設(shè)計分分析1.算法分分析 1) 寬度優(yōu)先先搜索算法廣度優(yōu)先搜搜索使用隊隊列（quueue）來來實現(xiàn)1、把根節(jié)節(jié)點放到隊隊列的末尾尾。2、每次從從隊列的頭頭部取出一一個元素，查查看這個元元素所有的的下一級元元素，把它它們放到隊隊列的末尾尾。并把這這個元素記記為它下一一級元素的的前驅(qū)。3、找到所所要找的元元素時結(jié)束束程序。4、如果遍遍歷整個圖圖還沒有找找到，結(jié)束束程序。2)深度優(yōu)優(yōu)先搜索算算法深度優(yōu)先搜搜索用棧（sstackk）來實現(xiàn)現(xiàn)，整個過過程可以想想象成一個個倒立的樹樹形：1、把根節(jié)節(jié)點壓入棧棧中。2、每次從從棧

15、中彈出出一個元素素，搜索所所有在它下下一級的元元素，把這這些元素壓壓入棧中。并把這個個元素記為為它下一級級元素的前前驅(qū)。3、找到所所要找的元元素時結(jié)束束程序。4、如果遍遍歷整個樹樹還沒有找找到，結(jié)束束程序。3)貪婪算算法1.建立數(shù)數(shù)學(xué)模型來來描述問題題把求解的的問題分成成若干個子子問題。對每一子子問題求解解，得到子子問題的局局部最優(yōu)解解。把子問題題的解局部部最優(yōu)解合合成原來解解問題的一一個解。實現(xiàn)該算法法的過程：從問題的某某一初始解解出發(fā)；whilee 能朝給給定總目標(biāo)標(biāo)前進(jìn)一步步do求出可行解解的一個解解元素；由所有解元元素組合成成問題的一一個可行解解。4)A*算算法A*1 （AA-Staa

16、r)算法法是一種靜靜態(tài)路網(wǎng)中中求解最短短路最有效效的直接搜搜索方法。公式表示為為： f(n)=gg(n)+h(n),其中 f(n) 是是從初始點點經(jīng)由節(jié)點點n到目標(biāo)標(biāo)點的估價價函數(shù)，g(n) 是在狀態(tài)態(tài)空間中從從初始節(jié)點點到n節(jié)點點的實際代代價，h(n) 是從n到到目標(biāo)節(jié)點點最佳路徑徑的估計代代價。保證找到最最短路徑（最最優(yōu)解的）條條件，關(guān)鍵鍵在于估價價函數(shù)f(n)的選選?。汗纼r值h(n)實際際值,搜索索的點數(shù)少少，搜索范范圍小，效效率高，但但不能保證證得到最優(yōu)優(yōu)解。2.數(shù)據(jù)結(jié)結(jié)構(gòu)1)圖結(jié)構(gòu)構(gòu)： 實現(xiàn)存儲儲“羅馬尼亞亞度假問題題”的圖空間間； 抽象圖結(jié)結(jié)構(gòu)的實現(xiàn)現(xiàn)：typeddef struu

17、ct /圖節(jié)節(jié)點類型charr cittynamme200;int vallue;int cosst;Ver;classs Grapph /圖圖結(jié)構(gòu)publiic:Grapph();Graaph(); VVer VVMaxxV;int edgeeMaxxVMaxxV;int numoofedgges; /注意這這個變量的的引用位置置/讀取取地圖節(jié)點點信息voidd ReaadVerrtex();/讀取取地圖邊關(guān)關(guān)系信息voidd ReaadEdgge();/取與與第V個節(jié)節(jié)點的第一一個鄰接點點int GetFFirsttVerttex(iint vv);/找到到第V1個個節(jié)點的VV2之后的的下

18、一個鄰鄰接節(jié)點int GetNNextVVerteex(innt v11, innt v22);int GetVVerVaalue(int iindexx);/獲取Vindeex 的的ver 的vallue值int GetVVerCoost(iint iindexx);/獲取Vindeex 的的ver 的cosst 值int GetEEdge(int rrow, int ccol);/獲取取edgeerowwcool 的的值voidd SettVerCCost(int iindexx,intt cosst);2)隊列結(jié)結(jié)構(gòu)寬度優(yōu)先算算法以及AA*算法 使用到。抽象隊列結(jié)結(jié)構(gòu)實現(xiàn)：classs

19、SeqQQueueepubliic:SeqQQueuee();SeqqQueuue();voidd QueeueInnitiaate();int QueuueNottEmptty();int QueuueApppend(int xx);int QueuueDellete(int *d);int QueuueOrdderApppendd(intt x, Grapph &GG);/A*算法使用用int Queuue_A_OrdeerApppend(int xx, Grraph &G);privaate:int queuueMaaxSizze;int rearr;int fronnt;int cou

20、nnt;3)棧結(jié)構(gòu)構(gòu)深度優(yōu)先算算法使用；棧結(jié)構(gòu)的抽抽象類型實實現(xiàn)：classs Stacckpubliic:Stacck();Staack();booll StaackNootFulll();booll StaakNottEmptty();voidd StaackPoop(Grraph &G);voidd StaackPuush(iint xx, Grraph &G);voidd PriintSttack(Grapph &GG);int GetWWeighht();privaate:int a1000;int top11;int weigght;三.算法設(shè)設(shè)計1) 寬度度優(yōu)先搜索索算法/寬度優(yōu)

21、優(yōu)先算法void Romaania_Tripp:BrroadFFirsttSearrch(GGraphh &graaph, int v)int u, ww; i = 0;SeqCCQuenne quueue;visiitedv = 1;/訪問節(jié)點點counnt+;if (v = end)retuurn;queuue.QuueueAAppennd( vv);/入入隊列whille (qqueuee.QueeueNootEmppty()/隊隊列非空queeue.QQueueeDeleete(&u);/取隊列列節(jié)點w = graaph.GGetFiirstVVerteex( uu);whiile (

22、w != -1) /有子子節(jié)點的話話iff (!vvisittedww)/如果子節(jié)節(jié)點未被訪訪問，則訪問子子節(jié)點VVisitt(w, u);vvisittedww = 1;ccountt+;iif (ww = end)/找到到結(jié)果Prinnt(grraph, b, end, v);retuurn;qqueuee.QueeueApppendd(w);/節(jié)點點壓入隊列列w = grraph.GetNNextVVerteex(u, w);2)深度優(yōu)優(yōu)先搜索算算法/深度優(yōu)優(yōu)先算法bool isOKK = ffalsee;int llevell = 00;constt int LLevell = 88;

23、/預(yù)預(yù)設(shè)的搜索索層次void Romaania_Tripp:DeepthFFirsttSearrch(GGraphh &graaph, int v, Stackk &staack)int w; ii = 00;if (isOKK = truee)retuurn;if (leveel+1 Leevel)retuurn;/大于于搜索層次次時不再深深入leveel+;visiitedv = 1;/訪問該節(jié)節(jié)點counnt+;stacck.SttackPPush(v, graaph);if (v = end | sstackk.GettWeigght() = MaxWWeighht)w = -1;if

24、 (v = end&staack.GGetWeeightt() = MaaxWeiight)coout sttack.GetWWeighht()MMaxWeeightt = sstackk.GettWeigght();*/coout 路徑徑長度為： staack.GGetWeeightt() enndl 訪問問節(jié)點數(shù)為為： coount eendl搜索層層次：levvelendll;issOK = truue;elseew = graaph.GGetFiirstVVerteex(v);/取取當(dāng)前節(jié)點點的第一個個子節(jié)點whille (ww != -1)if (!viisiteedw)Deepth

25、FFirsttSearrch(ggraphh, w, staack);/遞歸歸訪問w = graaph.GGetNeextVeertexx(v, w);/取取當(dāng)前節(jié)點點的下一個個子節(jié)點visiitedv = 0;/返回時置置該節(jié)點為為未訪問stacck.SttackPPop( grapph);/將將該節(jié)點彈彈出棧，并并根據(jù)grraph 中weiight 的值更改改當(dāng)前棧值值leveel-;3)貪婪算算法/貪婪算算法void Romaania_Tripp:Grreedyy_Alggoritthms(Grapph &graaph, int v)int u, ww;SeqCCQuenne quueu

26、e;/隊列列存儲圖節(jié)節(jié)點在圖中中的索引值值,優(yōu)先隊隊列，vaalue小小的在隊頭頭visiitedv = 1;if (v = end) reeturnn; queuue.QuueueOOrderrAppeend( v, graaph);/圖節(jié)節(jié)點按優(yōu)先先順序入隊隊列counnt+; /訪訪問節(jié)點數(shù)數(shù)+1whille (qqueuee.QueeueNootEmppty()/寬寬度優(yōu)先，循循環(huán)queeue.QQueueeDeleete( &u);/刪除除隊列頭元元素并返回回刪除的數(shù)數(shù)值/ccout u= u ;w = graaph.GGetFiirstVVerteex(u);whiile (w !

27、= -1)iff (!vvisittedww)VVisitt(w, u);/訪問ww節(jié)點，將將way b 的指指向更新iif (ww = end) /coout ww=ennd;counnt+; retuurn; qqueuee.QueeueOrrderAAppennd( ww, grraph); /圖節(jié)點按按優(yōu)先順序序入隊列ccountt+;w = grraph.GetNNextVVerteex(u, w);4)A*算法/A*算算法void Romaania_Tripp:ASStar_Algoorithhms(GGraphh &graaph, int v)/i = 0; couunt = 0

28、;int u, ww;SeqCCQuenne quueue;if (v = end) retturn;/到達(dá)達(dá)終點queuue.Quueue_A_OrrderAAppennd(v, graaph); counnt+;whille (qqueuee.QueeueNootEmppty()queeue.QQueueeDeleete( &u);if (u = ennd)coout 路徑徑長度為： graaph.GGetVeerCosst(u) + ggraphh.GettVerVValuee(u) eendl 訪問問節(jié)點數(shù)為為： coount eendl;reeturnn;w = graaph.GGe

29、tFiirstVVerteex( uu);whiile (w != -1)innt coost=ggraphh.GettVerCCost(u) + graaph.GGetEddge(ww,u);grraph.SetVVerCoost(ww, coost);/設(shè)置置當(dāng)前節(jié)點點移動到目目標(biāo)節(jié)點的的預(yù)估費(fèi)用用quueue.Queuue_A_OrdeerApppend( w, grapph);/按按預(yù)估費(fèi)用用優(yōu)先入隊隊列 coount+;w = grraph.GetNNextVVerteex(u, w);四.運(yùn)行結(jié)結(jié)果及分析析分析：節(jié)點數(shù)路徑長度耗時msOptimmalitty: Complleten

30、ness: BFS1145016NoYESDFS 1260531NoNOGreeddy845016NONOA*算法164180YESYES通過比較，GGreeddy搜索生生成的結(jié)點點數(shù)目最少少，為8個個，效率最最高；A*算法生成成的結(jié)點數(shù)數(shù)目最多，為為30個，效效率最低。DFS（一一般）、BFS和和Greeedy搜索索找到的都都不一定最最優(yōu)解， A*算法法具有完備備性且始終終找到的是是最優(yōu)解。寬度優(yōu)先先雖然是完完備的（如如果分支因因子有限的的話），在在任何情況況下寬度優(yōu)優(yōu)先都能找找到一個解解，但是，它它找到的第第一個解并并非最優(yōu)的的，此外，最最壞的情況況是，當(dāng)目目標(biāo)結(jié)點是是第d層的的最后一個個

31、被擴(kuò)展的的結(jié)點時，它它將耗費(fèi)大大量的時間間。寬度優(yōu)優(yōu)先時間復(fù)復(fù)雜度：（bb為分支因因子，d為為深度）；空間復(fù)雜雜度為所存存儲的節(jié)點點的個數(shù)。DFS不不是完備的的（除非查查找空間是是有限的），同同時，它也也不能找到到最優(yōu)解。深度優(yōu)先先的時間復(fù)復(fù)雜度：；空間復(fù)雜雜度：（bb為分支因因子，m為為深度，僅僅有一枝需需要存儲）；。貪婪算算法不是完完備的。同同時，它找找到的解也也不一定是是最優(yōu)解。其時間復(fù)復(fù)雜度：（bb代表分支支數(shù)，m為為深度）；空間復(fù)雜雜度為）。所以只有有A*算法法和DFSS（回溯+剪枝）是是完備的，且且能夠找到到最優(yōu)解；其時間復(fù)復(fù)雜度：擴(kuò)擴(kuò)展節(jié)點的的數(shù)目；空空間復(fù)雜度度：所有生生成的結(jié)

32、點點。綜合來來看，BFFS和貪婪婪算法的效效率較高，但但解并非最最優(yōu)，而AA*算法的的效率稍遜遜色，但解解為最優(yōu)；DFS（回回溯+剪枝枝）搜索雖雖能找到最最優(yōu)解但效效率最低。源代碼/Graaph.hh#praggma onceeusingg nameespacce sttd;#defiine MaxVV 20 /*#iffndeff MY_DEBUUG#defiine MMY_DEEBUG #endiif*/typeddef struuctcharr cittynamme200;/城市名int vallue;/權(quán)值int cosst;/A*算法法中從當(dāng)前前節(jié)點移動動到目標(biāo)節(jié)節(jié)點的預(yù)估估費(fèi)用Ve

33、r;classs Grapphpubliic:Grapph();Graaph(); VVer VVMaxxV;int edgeeMaxxVMaxxV;int numoofedgges; /注意這這個變量的的引用位置置/讀取取地圖節(jié)點點信息voidd ReaadVerrtex();/讀取取地圖邊關(guān)關(guān)系信息voidd ReaadEdgge();/取與與第V個節(jié)節(jié)點的第一一個鄰接點點int GetFFirsttVerttex(iint vv);/找到到第V1個個節(jié)點的VV2之后的的下一個鄰鄰接節(jié)點int GetNNextVVerteex(innt v11, innt v22);int GetVVer

34、Vaalue(int iindexx);/獲取Vindeex 的的ver 的vallue值int GetVVerCoost(iint iindexx);/獲取Vindeex 的的ver 的cosst 值int GetEEdge(int rrow, int ccol);/獲取取edgeerowwcool 的的值voidd SettVerCCost(int iindexx,intt cosst);privaate:;/Queeue.hh#praggma oncee#incllude#incllude Staack.hh#defiine MaxSSize 30/*#iffndeff MY_DEBUU

35、G#defiine MMY_DEEBUG #endiif/*/classs SeqQQueueepubliic:SeqQQueuee();SeqqQueuue();voidd QueeueInnitiaate();int QueuueNottEmptty();int QueuueApppend(int xx);int QueuueDellete(int *d);int QueuueOrdderApppendd(intt x, Grapph &GG);/A*算法使用用int Queuue_A_OrdeerApppend(int xx, Grraph &G);privaate:int queuue

36、MaaxSizze;int rearr;int fronnt;int counnt;typeddef SeqQQueuee SeqCCQuenne;/Rommaniaa_Triip.h#praggma oncee#incllude Queeue.hhtypeddef struuctint fathher;int me;way;classs Romaania_Tripppubliic:Romaania_Tripp();Rommaniaa_Triip();voidd Vissit(iint vv, innt u);voidd Priint(GGraphh &grraph, wayy *b, int

37、t endd, innt sttart);voidd BrooadFiirstSSearcch(Grraph &graaph, int vv);voidd DeppthFiirstSSearcch(Grraph &graaph, int vv,Staack &stacck);voidd Greeedy_Algoorithhms(GGraphh &grraph, intt v);voidd ASttar_AAlgorrithmms(Grraph &graaph, int vv);voidd ReSSet();int GetCCountt();int GetMMaxWeeightt();int G

38、etEEnd();way* GettB();privaate:way *b;int i;int end;int counnt;int visiitedCCity20;int MaxWWeighht;int visiited20;/Staack.hh#praggma oncee#inclludeGrapph.h#inclludeusingg nameespacce sttd;/*#iffndeff MY_DEBUUG#defiine MMY_DEEBUG #endiif*/classs Stacckpubliic:Stacck();Staack();booll StaackNootFulll()

39、;booll StaakNottEmptty();voidd StaackPoop(Grraph &G);voidd StaackPuush(iint xx, Grraph &G);voidd PriintSttack(Grapph &GG);int GetWWeighht();privaate:int a1000;int top11;int weigght;/Graaph.ccpp#inclludeGrapph.h#incllude#incllude#incllude#inclludeusingg nameespacce sttd;Graphh:Graaph()numoofedgges =

40、0;Graphh:GGraphh()void Grapph:RReadVVerteex()int i=0, v;charr ch20;fstrream infiile(啟發(fā)式數(shù)數(shù)值.txxt, ios:in);whille (iinfille ch & iinfille v)#ifdeef MYY_DEBBUGpriintf(%st%dn, ch, v);#endiifVii.vaalue = v;Vii.coost = 0;strrcpy(Vi.cittynamme, cch);i+;void Grapph:RReadEEdge()int valuu, i;fstrream infiile(

41、地圖數(shù)據(jù)據(jù)表.txxt, ios:in);i = 0;whille (iinfille vallu)edggei / 200i % 200 = valuu;#ifdeef MYY_DEBBUGif (i % 20 = 00)couut enddl;couuteedgei/200i%20tt;#endiifi+;/取與第第V個節(jié)點點的第一個個鄰接點int GGraphh:GeetFirrstVeertexx(intt v)if (v= 20)retturn -1;for (intt coll = 00; cool00 & edgeevcool11000)retturn col;retuurn -

42、1;/找到第第V1個節(jié)節(jié)點的V22之后的下下一個鄰接接節(jié)點int GGraphh:GeetNexxtVerrtex(int v1, intt v2)if (v1= 20 | vv2= 20)retturn -1;for (intt coll= v22 + 11; cool0 & edggev11cool11000)retturn col;retuurn -1;int GGraphh:GeetVerrValuue(innt indeex)/獲取取Vinndex 的veer 的vvaluees值retuurn VVinddex.valuue;int GGraphh:GeetVerrCostt(in

43、tt indeex)/獲取取Vinndex 的veer 的ccost 值retuurn VVinddex.costt;int GGraphh:GeetEdgge(innt row, int col)/獲取取edgeerowwcool 的的值retuurn eedgerowcol;void Grapph:SSetVeerCosst(innt indeex, intt costt)Vinndex.cosst = costt;/Queeue.ccpp#inclludeQueuue.h#incllude#incllude Staack.hhSeqQuueue:SeqqQueuue()rearr = 0

44、0;fronnt = 0;counnt = 0;SeqQuueue:SeeqQueeue()int SSeqQuueue:QueeueNootEmppty()if (counnt != 0)rreturrn 1;elsee retuurn 00;int SSeqQuueue:QueeueApppendd( innt x)if (counnt0 & rrear = ffrontt)couut 隊列列已滿 eendl;retturn 0;elseequeeuerrear = xx;reaar = (reaar + 1) % MaxxSizee;couunt+;retturn 1;int SSeqQ

45、uueue:QueeueDeeletee( innt *d)if (counnt = 0)couut 隊列列已空 0 & rrear = ffrontt)couut 隊列列已滿 = GG.Vqqueueereaar - 1.valuue)/隊尾插入入quueuerearr = x;reear = (reear + 1) % MaaxSizze;coount+;reeturnn 1;elsseiff (G.Vx.vaalue G.Vqqueueepossitioon.valuue)posiitionn+;iint ii;ffor (i = fronnt; ii0 & rrear = ffront

46、t)couut 隊列列已滿 x22 )/隊尾插入入quueuerearr = x;reear = (reear + 1) % MaaxSizze;coount+;reeturnn 1;elsse /隊頭插插入iff (G.Vx.vaalue + G.Vx.coost G.Vqqueueepossitioon%MaaxSizze.valuue + G.Vqqueueepossitioon%MaaxSizze.costt)posiitionn+;iint ii;ffor (i = fronnt; iipossitioon; ii+)queuue(ii - 11 + MMaxSiize) % Maa

47、xSizze = queeueii%MaxxSizee;qqueuee(i - 1 + MaaxSizze) % MaxxSizee = x;ffrontt = (fronnt - 1 + MaxSSize) % MMaxSiize;ccountt+;rreturrn 1;retuurn 00;/Romaania_Tripp.cppp#inclludeRomaania_Tripp.h#incllude#incllude#inclludeusingg nameespacce sttd;Romannia_TTrip:Rommaniaa_Triip()b = new way1100;i = 0;en

48、d = 2;counnt = 0;MaxWWeighht = 100000;for (sizze_t i = 0; ii 220; ii+)vissiteddi = 0;void Romaania_Tripp:ReeSet()if(NNULL!=b)ddelettebb;b = new way220;i = 0;end = 2;counnt = 0;for (sizze_t i = 0; ii 220; ii+)vissiteddi = 0;Romannia_TTrip:Roomaniia_Trrip()if (NULLL != b)deeleteeb;void Romaania_Tripp:

49、Viisit(int v, intt u)bi.fatther = u;bi.me = v;i +;void Romaania_Tripp:Prrint(Grapph &graaph, way *b, intt end, int starrt)int Bwayy = 00;vecttor CityyNamee;striing nname = grraph.Vennd.ccitynname;CityyNamee.pussh_baack(nname);whille (11)forr (intt j = 0; ji; j+)iff (bj.me = ennd)nname = grraph.Vbj.f

50、athher.cityynamee;CCityNName.pushh_bacck(naame);BBway += ggraphh.edggebj.mebj.fathher;eend = bj.fathher;if (endd = starrt)breaak;coutt 0; i)couut CittyNammei ;coutt Buchharesst enddl;coutt 路徑長度度為： BBway eendl 訪訪問節(jié)點數(shù)數(shù)為： ccountt Leevel)retuurn;/大于于搜索層次次時不再深深入leveel+;visiitedv = 1;/訪問該節(jié)節(jié)點counnt+;stacck

51、.SttackPPush(v, graaph);if (v = end | sstackk.GettWeigght() = MaxWWeighht)w = -1;if (v = end&staack.GGetWeeightt() = MaaxWeiight)coout sttack.GetWWeighht()MMaxWeeightt = sstackk.GettWeigght();*/coout 路徑徑長度為： staack.GGetWeeightt() enndl 訪問問節(jié)點數(shù)為為： coount eendl搜索層層次：levvelendll;issOK = truue;elseew = g

52、raaph.GGetFiirstVVerteex(v);/取取當(dāng)前節(jié)點點的第一個個子節(jié)點whille (ww != -1)if (!viisiteedw)DeepthFFirsttSearrch(ggraphh, w, staack);/遞歸歸訪問w = graaph.GGetNeextVeertexx(v, w);/取取當(dāng)前節(jié)點點的下一個個子節(jié)點visiitedv = 0;/返回時置置該節(jié)點為為未訪問stacck.SttackPPop( grapph);/將將該節(jié)點彈彈出棧，并并根據(jù)grraph 中weiight 的值更改改當(dāng)前棧值值leveel-;/貪婪算算法void Romaania_T

53、ripp:Grreedyy_Alggoritthms(Grapph &graaph, int v)int u, ww;SeqCCQuenne quueue;/隊列列存儲圖節(jié)節(jié)點在圖中中的索引值值,優(yōu)先隊隊列，vaalue小小的在隊頭頭visiitedv = 1;if (v = end) reeturnn; queuue.QuueueOOrderrAppeend( v, graaph);/圖節(jié)節(jié)點按優(yōu)先先順序入隊隊列counnt+; /訪訪問節(jié)點數(shù)數(shù)+1whille (qqueuee.QueeueNootEmppty()/寬寬度優(yōu)先，循循環(huán)queeue.QQueueeDeleete( &u);/

54、刪除除隊列頭元元素并返回回刪除的數(shù)數(shù)值/ccout u= u ;w = graaph.GGetFiirstVVerteex(u);whiile (w != -1)iff (!vvisittedww)VVisitt(w, u);/訪問ww節(jié)點，將將way b 的指指向更新iif (ww = end) /coout ww=ennd;counnt+; retuurn; qqueuee.QueeueOrrderAAppennd( ww, grraph); /圖節(jié)點按按優(yōu)先順序序入隊列ccountt+;w = grraph.GetNNextVVerteex(u, w);/A*算算法void Romaan

55、ia_Tripp:ASStar_Algoorithhms(GGraphh &graaph, int v)/i = 0; couunt = 0;int u, ww;SeqCCQuenne quueue;if (v = end) retturn;/到達(dá)達(dá)終點queuue.Quueue_A_OrrderAAppennd(v, graaph); counnt+;whille (qqueuee.QueeueNootEmppty()queeue.QQueueeDeleete( &u);if (u = ennd)coout 路徑徑長度為： graaph.GGetVeerCosst(u) + ggraphh.

56、GettVerVValuee(u) eendl 訪問問節(jié)點數(shù)為為： coount eendl;reeturnn;w = graaph.GGetFiirstVVerteex( uu);whiile (w != -1)innt coost=ggraphh.GettVerCCost(u) + graaph.GGetEddge(ww,u);grraph.SetVVerCoost(ww, coost);/設(shè)置置當(dāng)前節(jié)點點移動到目目標(biāo)節(jié)點的的預(yù)估費(fèi)用用quueue.Queuue_A_OrdeerApppend( w, grapph);/按按預(yù)估費(fèi)用用優(yōu)先入隊隊列 coount+;w = grraph.Ge

57、tNNextVVerteex(u, w);int RRomannia_TTrip:GettCounnt()retuurn ccountt;int RRomannia_TTrip:GettMaxWWeighht()retuurn MMaxWeeightt;int RRomannia_TTrip:GettEnd()retuurn eend;way *Romaania_Tripp:GeetB()retuurn bb;/Souurce.cpp/*On holiiday in RRomannia; currrentlly inn AraadFlighht leeavess tommorroow frrom BBuchaaresttFormuulatee goaal：Bee in BuchharesstFormuulatee prooblemmStatees: vvarioous ccitieesActioons: drivve beetweeen ciitiessFind soluutionnSequeence of ccitiees; ee.g. Aradd, Siibiu, Faggarass,Buchaarestt,*/#inclludeGrapph.h#inclludeQueuue.h#inclludeStacck.h#inclludeRomaania_Tripp.h#in