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

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

2、類智慧的“容器”。人工智能是對(duì)人的意識(shí)、思維的信息過程的模擬。人工智能不是人的智能，但能像人那樣思考、也可能超過人的智能。人工智能是一門極富挑戰(zhàn)性的科學(xué)，從事這項(xiàng)工作的人必須懂得計(jì)算機(jī)知識(shí)，心理學(xué)和哲學(xué)。人工智能是包括十分廣泛的科學(xué)，它由不同的領(lǐng)域組成，如機(jī)器學(xué)習(xí)，計(jì)算機(jī)視覺等等，總的說來，人工智能研究的一個(gè)主要目標(biāo)是使機(jī)器能夠勝任一些通常需要人類智能才能完成的復(fù)雜工作。但不同的時(shí)代、不同的人對(duì)這種“復(fù)雜工作”的理解是不同的。人工智能是計(jì)算機(jī)學(xué)科的一個(gè)分支，二十世紀(jì)七十年代以來被稱為世界三大尖端技術(shù)之一（空間技術(shù)、能源技術(shù)、人工智能）。也被認(rèn)為是二十一世紀(jì)三大尖端技術(shù)（基因工程、納米科學(xué)、人工

3、智能）之一。這是因?yàn)榻陙硭@得了迅速的發(fā)展，在很多學(xué)科領(lǐng)域都獲得了廣泛應(yīng)用，并取得了豐碩的成果，人工智能已逐步成為一個(gè)獨(dú)立的分支，無論在理論和實(shí)踐上都已自成一個(gè)系統(tǒng)。人工智能是研究使計(jì)算機(jī)來模擬人的某些思維過程和智能行為（如學(xué)習(xí)、推理、思考、規(guī)劃等）的學(xué)科，主要包括計(jì)算機(jī)實(shí)現(xiàn)智能的原理、制造類似于人腦智能的計(jì)算機(jī)，使計(jì)算機(jī)能實(shí)現(xiàn)更高層次的應(yīng)用。人工智能將涉及到計(jì)算機(jī)科學(xué)、心理學(xué)、哲學(xué)和語言學(xué)等學(xué)科?？梢哉f幾乎是自然科學(xué)和社會(huì)科學(xué)的所有學(xué)科，其范圍已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)科學(xué)的范疇，人工智能與思維科學(xué)的關(guān)系是實(shí)踐和理論的關(guān)系，人工智能是處于思維科學(xué)的技術(shù)應(yīng)用層次，是它的一個(gè)應(yīng)用分支。從思維觀點(diǎn)看

4、，人工智能不僅限于邏輯思維，要考慮形象思維、靈感思維才能促進(jìn)人工智能的突破性的發(fā)展，數(shù)學(xué)常被認(rèn)為是多種學(xué)科的基礎(chǔ)科學(xué)，數(shù)學(xué)也進(jìn)入語言、思維領(lǐng)域，人工智能學(xué)科也必須借用數(shù)學(xué)工具，數(shù)學(xué)不僅在標(biāo)準(zhǔn)邏輯、模糊數(shù)學(xué)等范圍發(fā)揮作用，數(shù)學(xué)進(jìn)入人工智能學(xué)科，它們將互相促進(jìn)而更快地發(fā)展。題目一：羅馬利亞度假問題一. 問題描述分別用代價(jià)一致的寬度優(yōu)先、有限制的深度優(yōu)先（預(yù)設(shè)搜索層次）、貪婪算法和A*算法求解“羅馬利亞度假問題”。即找到從初始地點(diǎn) Arad到 目的地點(diǎn) Bucharest 的一條路徑。要求：分別用文件存儲(chǔ)地圖和啟發(fā)函數(shù)表，用生成節(jié)點(diǎn)數(shù)比較幾種算法在問題求解時(shí)的效率，并列表給出結(jié)果。數(shù)據(jù)如下：1、地圖

5、2、啟發(fā)函數(shù)值A(chǔ)rad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Doberta 242Pitesti 100 Eforie 161 Rimmicu_Vikea 193 Fagaras 176 Sibiu 253 Glurgiu 77Timisoara 329 Hirsova 151 Urziceni 80 Iasi 226 Vaslui 199 Lugoj 244 Zerind 3743、地圖數(shù)據(jù)表0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 140 10

6、00 118 1000 1000 1000 1000 1000 751000 0 1000 1000 1000 1000 75 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 70 10001000 1000 0 1000 1000 1000 1000 101 1000 1000 211 1000 90 1000 1000 85 1000 1000 1000 10001000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 87 1000

7、 1000 10001000 1000 1000 1000 0 1000 120 138 1000 146 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 151 1000 1000 1000 1000 1000 1000 1000 711000 75 1000 1000 120 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1

8、01 1000 138 1000 1000 0 1000 97 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 10001000 1000 1000 1000 146 1000 1000 97 1000 0 1000 80 1000 1000 1000 1000 1000 1000 1000 10001000 1000 211 1000 1000 1000 1000

9、1000 1000 1000 0 99 1000 1000 1000 1000 1000 1000 1000 1000140 1000 1000 1000 1000 151 1000 1000 1000 80 99 0 1000 1000 1000 1000 1000 1000 1000 10001000 1000 90 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000118 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 100

10、0 1000 0 1000 1000 1000 1000 111 10001000 1000 1000 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 1000 0 98 1000 1000 1000 10001000 1000 85 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 98 0 1000 1000 1000 10001000 1000 1000 87 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0

11、 92 1000 10001000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 92 0 1000 10001000 70 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 111 1000 1000 1000 1000 0 100075 1000 1000 1000 1000 71 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0二.設(shè)計(jì)分析1.

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

13、法1.建立數(shù)學(xué)模型來描述問題把求解的問題分成若干個(gè)子問題。對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。實(shí)現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while 能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；由所有解元素組合成問題的一個(gè)可行解。4)A*算法A*1 （A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù)，g(n) 是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n) 是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。保證找到最短路徑（最優(yōu)解的

14、）條件，關(guān)鍵在于估價(jià)函數(shù)f(n)的選?。汗纼r(jià)值h(n)<= n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。并且如果h(n)=d(n)，即距離估計(jì)h(n)等于最短距離，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行， 此時(shí)的搜索效率是最高的。如果 估價(jià)值>實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。2.數(shù)據(jù)結(jié)構(gòu)1)圖結(jié)構(gòu)： 實(shí)現(xiàn)存儲(chǔ)“羅馬尼亞度假問題”的圖空間； 抽象圖結(jié)構(gòu)的實(shí)現(xiàn)：typedef struct /圖節(jié)點(diǎn)類型char cityname20;int value;int cost;Ver;class Graph /圖結(jié)構(gòu)publ

15、ic:Graph();Graph(); Ver VMaxV;int edgeMaxVMaxV;int numofedges; /注意這個(gè)變量的引用位置/讀取地圖節(jié)點(diǎn)信息void ReadVertex();/讀取地圖邊關(guān)系信息void ReadEdge();/取與第V個(gè)節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)int GetFirstVertex(int v);/找到第V1個(gè)節(jié)點(diǎn)的V2之后的下一個(gè)鄰接節(jié)點(diǎn)int GetNextVertex(int v1, int v2);int GetVerValue(int index);/獲取Vindex 的ver 的value值int GetVerCost(int index);

16、/獲取Vindex 的ver 的cost 值int GetEdge(int row, int col);/獲取edgerowcol 的值void SetVerCost(int index,int cost);2)隊(duì)列結(jié)構(gòu)寬度優(yōu)先算法以及A*算法 使用到。抽象隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)：class SeqQueuepublic:SeqQueue();SeqQueue();void QueueInitiate();int QueueNotEmpty();int QueueAppend(int x);int QueueDelete(int *d);int QueueOrderAppend(int x, Graph

17、 &G);/A*算法使用int Queue_A_OrderAppend(int x, Graph &G);private:int queueMaxSize;int rear;int front;int count;3)棧結(jié)構(gòu)深度優(yōu)先算法使用；棧結(jié)構(gòu)的抽象類型實(shí)現(xiàn)：class Stackpublic:Stack();Stack();bool StackNotFull();bool StakNotEmpty();void StackPop(Graph &G);void StackPush(int x, Graph &G);void PrintStack(Graph

18、&G);int GetWeight();private:int a100;int top1;int weight;三.算法設(shè)計(jì)1) 寬度優(yōu)先搜索算法/寬度優(yōu)先算法void Romania_Trip:BroadFirstSearch(Graph &graph, int v)int u, w; i = 0;SeqCQuene queue;visitedv = 1;/訪問節(jié)點(diǎn)count+;if (v = end)return;queue.QueueAppend( v);/入隊(duì)列while (queue.QueueNotEmpty()/隊(duì)列非空queue.QueueDelete(&am

19、p;u);/取隊(duì)列節(jié)點(diǎn)w = graph.GetFirstVertex( u);while (w != -1) /有子節(jié)點(diǎn)的話if (!visitedw)/如果子節(jié)點(diǎn)未被訪問，則訪問子節(jié)點(diǎn)Visit(w, u);visitedw = 1;count+;if (w = end)/找到結(jié)果Print(graph, b, end, v);return;queue.QueueAppend(w);/節(jié)點(diǎn)壓入隊(duì)列w = graph.GetNextVertex(u, w);2)深度優(yōu)先搜索算法/深度優(yōu)先算法bool isOK = false;int level = 0;const int Level = 8

20、;/預(yù)設(shè)的搜索層次void Romania_Trip:DepthFirstSearch(Graph &graph, int v, Stack &stack)int w; i = 0;if (isOK = true)return;if (level+1 > Level)return;/大于搜索層次時(shí)不再深入level+;visitedv = 1;/訪問該節(jié)點(diǎn)count+;stack.StackPush(v, graph);if (v = end | stack.GetWeight() >= MaxWeight)w = -1;if (v = end&&s

21、tack.GetWeight() <= MaxWeight)cout << "-深度優(yōu)先遍歷路徑為："stack.PrintStack(graph);/*if (MaxWeight>stack.GetWeight()MaxWeight = stack.GetWeight();*/cout << "-路徑長(zhǎng)度為：" << stack.GetWeight() << endl << "-訪問節(jié)點(diǎn)數(shù)為：" << count << endl<&

22、lt;"-搜索層次："<<level<<endl;isOK = true;elsew = graph.GetFirstVertex(v);/取當(dāng)前節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)while (w != -1)if (!visitedw)DepthFirstSearch(graph, w, stack);/遞歸訪問w = graph.GetNextVertex(v, w);/取當(dāng)前節(jié)點(diǎn)的下一個(gè)子節(jié)點(diǎn)visitedv = 0;/返回時(shí)置該節(jié)點(diǎn)為未訪問stack.StackPop( graph);/將該節(jié)點(diǎn)彈出棧，并根據(jù)graph 中weight 的值更改當(dāng)前棧值lev

23、el-;3)貪婪算法/貪婪算法void Romania_Trip:Greedy_Algorithms(Graph &graph, int v)int u, w;SeqCQuene queue;/隊(duì)列存儲(chǔ)圖節(jié)點(diǎn)在圖中的索引值,優(yōu)先隊(duì)列，value小的在隊(duì)頭visitedv = 1;if (v = end) return; queue.QueueOrderAppend( v, graph);/圖節(jié)點(diǎn)按優(yōu)先順序入隊(duì)列count+; /訪問節(jié)點(diǎn)數(shù)+1while (queue.QueueNotEmpty()/寬度優(yōu)先，循環(huán)queue.QueueDelete( &u);/刪除隊(duì)列頭元素并返

24、回刪除的數(shù)值/cout << "u= " << u << " "w = graph.GetFirstVertex(u);while (w != -1)if (!visitedw)Visit(w, u);/訪問w節(jié)點(diǎn)，將way b 的指向更新if (w = end) /cout << "w=end"count+; return; queue.QueueOrderAppend( w, graph); /圖節(jié)點(diǎn)按優(yōu)先順序入隊(duì)列count+;w = graph.GetNextVertex(u,

25、w);4)A*算法/A*算法void Romania_Trip:AStar_Algorithms(Graph &graph, int v)/i = 0; count = 0;int u, w;SeqCQuene queue;if (v = end) return;/到達(dá)終點(diǎn)queue.Queue_A_OrderAppend(v, graph); count+;while (queue.QueueNotEmpty()queue.QueueDelete( &u);if (u = end)cout << "-路徑長(zhǎng)度為：" << graph

26、.GetVerCost(u) + graph.GetVerValue(u) << endl<< "-訪問節(jié)點(diǎn)數(shù)為：" << count << endl;return;w = graph.GetFirstVertex( u);while (w != -1)int cost=graph.GetVerCost(u) + graph.GetEdge(w,u);graph.SetVerCost(w, cost);/設(shè)置當(dāng)前節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)的預(yù)估費(fèi)用queue.Queue_A_OrderAppend( w, graph);/按預(yù)估費(fèi)用優(yōu)

27、先入隊(duì)列 count+;w = graph.GetNextVertex(u, w);四.運(yùn)行結(jié)果及分析分析：節(jié)點(diǎn)數(shù)路徑長(zhǎng)度耗時(shí)msOptimality: Completeness: BFS1145016NoYESDFS 1260531NoNOGreedy845016NONOA*算法164180YESYES通過比較，Greedy搜索生成的結(jié)點(diǎn)數(shù)目最少，為8個(gè)，效率最高；A*算法生成的結(jié)點(diǎn)數(shù)目最多，為30個(gè)，效率最低。DFS（一般）、BFS和Greedy搜索找到的都不一定最優(yōu)解， A*算法具有完備性且始終找到的是最優(yōu)解。寬度優(yōu)先雖然是完備的（如果分支因子有限的話），在任何情況下寬度優(yōu)先都能找到一個(gè)

28、解，但是，它找到的第一個(gè)解并非最優(yōu)的，此外，最壞的情況是，當(dāng)目標(biāo)結(jié)點(diǎn)是第d層的最后一個(gè)被擴(kuò)展的結(jié)點(diǎn)時(shí)，它將耗費(fèi)大量的時(shí)間。寬度優(yōu)先時(shí)間復(fù)雜度：（b為分支因子，d為深度）；空間復(fù)雜度為所存儲(chǔ)的節(jié)點(diǎn)的個(gè)數(shù)。DFS不是完備的（除非查找空間是有限的），同時(shí)，它也不能找到最優(yōu)解。深度優(yōu)先的時(shí)間復(fù)雜度：；空間復(fù)雜度：（b為分支因子，m為深度，僅有一枝需要存儲(chǔ)）；。貪婪算法不是完備的。同時(shí)，它找到的解也不一定是最優(yōu)解。其時(shí)間復(fù)雜度：（b代表分支數(shù)，m為深度）；空間復(fù)雜度為）。所以只有A*算法和DFS（回溯+剪枝）是完備的，且能夠找到最優(yōu)解；其時(shí)間復(fù)雜度：擴(kuò)展節(jié)點(diǎn)的數(shù)目；空間復(fù)雜度：所有生成的結(jié)點(diǎn)。綜合來看，

29、BFS和貪婪算法的效率較高，但解并非最優(yōu)，而A*算法的效率稍遜色，但解為最優(yōu)；DFS（回溯+剪枝）搜索雖能找到最優(yōu)解但效率最低。源代碼/Graph.h#pragma onceusing namespace std;#define MaxV 20 /*#ifndef MY_DEBUG#define MY_DEBUG #endif*/typedef structchar cityname20;/城市名int value;/權(quán)值int cost;/A*算法中從當(dāng)前節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)的預(yù)估費(fèi)用Ver;class Graphpublic:Graph();Graph(); Ver VMaxV;int ed

30、geMaxVMaxV;int numofedges; /注意這個(gè)變量的引用位置/讀取地圖節(jié)點(diǎn)信息void ReadVertex();/讀取地圖邊關(guān)系信息void ReadEdge();/取與第V個(gè)節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)int GetFirstVertex(int v);/找到第V1個(gè)節(jié)點(diǎn)的V2之后的下一個(gè)鄰接節(jié)點(diǎn)int GetNextVertex(int v1, int v2);int GetVerValue(int index);/獲取Vindex 的ver 的value值int GetVerCost(int index);/獲取Vindex 的ver 的cost 值int GetEdge(in

31、t row, int col);/獲取edgerowcol 的值void SetVerCost(int index,int cost);private:;/Queue.h#pragma once#include<iostream>#include "Stack.h"#define MaxSize 30/*#ifndef MY_DEBUG#define MY_DEBUG #endif/*/class SeqQueuepublic:SeqQueue();SeqQueue();void QueueInitiate();int QueueNotEmpty();int Q

32、ueueAppend(int x);int QueueDelete(int *d);int QueueOrderAppend(int x, Graph &G);/A*算法使用int Queue_A_OrderAppend(int x, Graph &G);private:int queueMaxSize;int rear;int front;int count;typedef SeqQueue SeqCQuene;/Romania_Trip.h#pragma once#include "Queue.h"typedef structint father;int

33、 me;way;class Romania_Trippublic:Romania_Trip();Romania_Trip();void Visit(int v, int u);void Print(Graph &graph, way *b, int end, int start);void BroadFirstSearch(Graph &graph, int v);void DepthFirstSearch(Graph &graph, int v,Stack &stack);void Greedy_Algorithms(Graph &graph, int

34、 v);void AStar_Algorithms(Graph &graph, int v);void ReSet();int GetCount();int GetMaxWeight();int GetEnd();way* GetB();private:way *b;int i;int end;int count;int visitedCity20;int MaxWeight;int visited20;/Stack.h#pragma once#include"Graph.h"#include<iostream>using namespace std;/

35、*#ifndef MY_DEBUG#define MY_DEBUG #endif*/class Stackpublic:Stack();Stack();bool StackNotFull();bool StakNotEmpty();void StackPop(Graph &G);void StackPush(int x, Graph &G);void PrintStack(Graph &G);int GetWeight();private:int a100;int top1;int weight;/Graph.cpp#include"Graph.h"

36、#include<iostream>#include<stdlib.h>#include<fstream>#include<string>using namespace std;Graph:Graph()numofedges = 0;Graph:Graph()void Graph:ReadVertex()int i=0, v;char ch20;fstream infile("啟發(fā)式數(shù)值.txt", ios:in);while (infile >> ch && infile >> v)#

37、ifdef MY_DEBUGprintf("%st%dn", ch, v);#endifVi.value = v;Vi.cost = 0;strcpy(Vi.cityname, ch);i+;void Graph:ReadEdge()int valu, i;fstream infile("地圖數(shù)據(jù)表.txt", ios:in);i = 0;while (infile >> valu)edgei / 20i % 20 = valu;#ifdef MY_DEBUGif (i % 20 = 0)cout << endl;cout<

38、<edgei/20i%20<<"t"#endifi+;/取與第V個(gè)節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)int Graph:GetFirstVertex(int v)if (v<0 | v >= 20)return -1;for (int col = 0; col<20; col+)if (edgevcol>0 && edgevcol<1000)return col;return -1;/找到第V1個(gè)節(jié)點(diǎn)的V2之后的下一個(gè)鄰接節(jié)點(diǎn)int Graph:GetNextVertex(int v1, int v2)if (v1<0

39、| v1 >= 20 | v2<0 | v2 >= 20)return -1;for (int col= v2 + 1; col<20; col+)if (edgev1col>0 && edgev1col<1000)return col;return -1;int Graph:GetVerValue(int index)/獲取Vindex 的ver 的values值return Vindex.value;int Graph:GetVerCost(int index)/獲取Vindex 的ver 的cost 值return Vindex.cos

40、t;int Graph:GetEdge(int row, int col)/獲取edgerowcol 的值return edgerowcol;void Graph:SetVerCost(int index, int cost)Vindex.cost = cost;/Queue.cpp#include"Queue.h"#include<iostream>#include "Stack.h"SeqQueue:SeqQueue()rear = 0;front = 0;count = 0;SeqQueue:SeqQueue()int SeqQueue

41、:QueueNotEmpty()if (count != 0)return 1;else return 0;int SeqQueue:QueueAppend( int x)if (count>0 && rear = front)cout << "隊(duì)列已滿" << endl;return 0;elsequeuerear = x;rear = (rear + 1) % MaxSize;count+;return 1;int SeqQueue:QueueDelete( int *d)if (count = 0)cout <<

42、; "隊(duì)列已空" << endl;return 0;else*d = queuefront;front = (front + 1) % MaxSize;count-;return 1;int SeqQueue:QueueOrderAppend( int x, Graph &G)if (count>0 && rear = front)cout << "隊(duì)列已滿" << endl;return 0;elseif (count = 0 | G.Vx.value >= G.Vqueuerea

43、r - 1.value)/隊(duì)尾插入queuerear = x;rear = (rear + 1) % MaxSize;count+;return 1;elseif (G.Vx.value <= G.V queuefront .value)/隊(duì)頭插入queuefront - 1 = x;front = (front - 1 + MaxSize) % MaxSize;count+;return 1;else /排序找位置插入int position = front;while (G.Vx.value>G.Vqueueposition.value)position+;int i;for

44、(i = front; i<position; i+)queue(i - 1 + MaxSize) % MaxSize = queuei%MaxSize;queue(i - 1 + MaxSize) % MaxSize = x;front = (front - 1 + MaxSize) % MaxSize;count+;return 1;return 0;/A*int SeqQueue:Queue_A_OrderAppend(int x, Graph &G)if (count>0 && rear = front)cout << "隊(duì)列已

45、滿" << endl;return 0;elseint x1 = G.Vx.value + G.Vx.cost;int x2 = 0;if(count !=0 ) x2=G.Vqueuerear - 1.value + G.Vqueuerear - 1.cost;if (count = 0 |x1 >x2 )/隊(duì)尾插入queuerear = x;rear = (rear + 1) % MaxSize;count+;return 1;else /隊(duì)頭插入if (G.Vx.value + G.Vx.cost<G.Vqueuefront.value + G.Vque

46、uefront.cost)queuefront - 1 = x;front = (front - 1 + MaxSize) % MaxSize;count+;return 1;else /排序找位置插入int position = front;while (G.Vx.value + G.Vx.cost > G.Vqueueposition%MaxSize.value + G.Vqueueposition%MaxSize.cost)position+;int i;for (i = front; i<position; i+)queue(i - 1 + MaxSize) % MaxSi

47、ze = queuei%MaxSize;queue(i - 1 + MaxSize) % MaxSize = x;front = (front - 1 + MaxSize) % MaxSize;count+;return 1;return 0;/Romania_Trip.cpp#include"Romania_Trip.h"#include<iostream>#include<vector>#include<string>using namespace std;Romania_Trip:Romania_Trip()b = new way1

48、00;i = 0;end = 2;count = 0;MaxWeight = 10000;for (size_t i = 0; i < 20; i+)visitedi = 0;void Romania_Trip:ReSet()if(NULL!=b)deleteb;b = new way20;i = 0;end = 2;count = 0;for (size_t i = 0; i < 20; i+)visitedi = 0;Romania_Trip:Romania_Trip()if (NULL != b)deleteb;void Romania_Trip:Visit(int v, i

49、nt u)bi.father = u;bi.me = v;i +;void Romania_Trip:Print(Graph &graph, way *b, int end, int start)int Bway = 0;vector<string> CityName;string name = graph.Vend.cityname;CityName.push_back(name);while (1)for (int j = 0; j<i; j+)if (bj.me = end)name = graph.Vbj.father.cityname;CityName.pu

50、sh_back(name);Bway += graph.edgebj.mebj.father;end = bj.father;if (end = start)break;cout << "-遍歷路徑為："for (size_t i = CityName.size()-1; i >0; i-)cout << CityNamei << "->"cout <<"Bucharest"<< endl;cout << "-路徑長(zhǎng)度為：" <

51、;< Bway << endl << "-訪問節(jié)點(diǎn)數(shù)為：" << count << endl;/寬度優(yōu)先算法void Romania_Trip:BroadFirstSearch(Graph &graph, int v)int u, w; i = 0;SeqCQuene queue;visitedv = 1;count+;if (v = end)return;queue.QueueAppend( v);while (queue.QueueNotEmpty()/隊(duì)列非空queue.QueueDelete(&u);/取隊(duì)列節(jié)點(diǎn)w = graph.GetFirstVertex( u);while (w != -1) /有子節(jié)點(diǎn)的話if (!visitedw)Visit(w, u);visitedw = 1;count+;if (w