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

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

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

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

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

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

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

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

15、ic:Graph();Graph(); Ver VMaxV;int edgeMaxVMaxV;int numofedges; /注意這個變量的引用位置/讀取地圖節(jié)點信息void ReadVertex();/讀取地圖邊關(guān)系信息void ReadEdge();/取與第V個節(jié)點的第一個鄰接點int GetFirstVertex(int v);/找到第V1個節(jié)點的V2之后的下一個鄰接節(jié)點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)隊列結(jié)構(gòu)寬度優(yōu)先算法以及A*算法 使用到。抽象隊列結(jié)構(gòu)實現(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)的抽象類型實現(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è)計1) 寬度優(yōu)先搜索算法/寬度優(yōu)先算法void Romania_Trip:BroadFirstSearch(Graph &graph, int v)int u, w; i = 0;SeqCQuene queue;visitedv = 1;/訪問節(jié)點count+;if (v = end)return;queue.QueueAppend( v);/入隊列while (queue.QueueNotEmpty()/隊列非空queue.QueueDelete(&am

19、p;u);/取隊列節(jié)點w = graph.GetFirstVertex( u);while (w != -1) /有子節(jié)點的話if (!visitedw)/如果子節(jié)點未被訪問，則訪問子節(jié)點Visit(w, u);visitedw = 1;count+;if (w = end)/找到結(jié)果Print(graph, b, end, v);return;queue.QueueAppend(w);/節(jié)點壓入隊列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;/大于搜索層次時不再深入level+;visitedv = 1;/訪問該節(jié)點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 << "-路徑長度為：" << stack.GetWeight() << endl << "-訪問節(jié)點數(shù)為：" << count << endl<&

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

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

24、回刪除的數(shù)值/cout << "u= " << u << " "w = graph.GetFirstVertex(u);while (w != -1)if (!visitedw)Visit(w, u);/訪問w節(jié)點，將way b 的指向更新if (w = end) /cout << "w=end"count+; return; queue.QueueOrderAppend( w, graph); /圖節(jié)點按優(yōu)先順序入隊列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á)終點queue.Queue_A_OrderAppend(v, graph); count+;while (queue.QueueNotEmpty()queue.QueueDelete( &u);if (u = end)cout << "-路徑長度為：" << graph

26、.GetVerCost(u) + graph.GetVerValue(u) << endl<< "-訪問節(jié)點數(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é)點移動到目標(biāo)節(jié)點的預(yù)估費用queue.Queue_A_OrderAppend( w, graph);/按預(yù)估費用優(yōu)

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

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

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é)點移動到目標(biāo)節(jié)點的預(yù)估費用Ver;class Graphpublic:Graph();Graph(); Ver VMaxV;int ed

30、geMaxVMaxV;int numofedges; /注意這個變量的引用位置/讀取地圖節(jié)點信息void ReadVertex();/讀取地圖邊關(guān)系信息void ReadEdge();/取與第V個節(jié)點的第一個鄰接點int GetFirstVertex(int v);/找到第V1個節(jié)點的V2之后的下一個鄰接節(jié)點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個節(jié)點的第一個鄰接點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個節(jié)點的V2之后的下一個鄰接節(jié)點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 << "隊列已滿" << endl;return 0;elsequeuerear = x;rear = (rear + 1) % MaxSize;count+;return 1;int SeqQueue:QueueDelete( int *d)if (count = 0)cout <<

42、; "隊列已空" << 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 << "隊列已滿" << endl;return 0;elseif (count = 0 | G.Vx.value >= G.Vqueuerea

43、r - 1.value)/隊尾插入queuerear = x;rear = (rear + 1) % MaxSize;count+;return 1;elseif (G.Vx.value <= G.V queuefront .value)/隊頭插入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 << "隊列已

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 )/隊尾插入queuerear = x;rear = (rear + 1) % MaxSize;count+;return 1;else /隊頭插入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 << "-路徑長度為：" <

51、;< Bway << endl << "-訪問節(jié)點數(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()/隊列非空queue.QueueDelete(&u);/取隊列節(jié)點w = graph.GetFirstVertex( u);while (w != -1) /有子節(jié)點的話if (!visitedw)Visit(w, u);visitedw = 1;count+;if (w