【文章內(nèi)容簡介】 法具有完備性且始終找到的是最優(yōu)解。寬度優(yōu)先雖然是完備的（如果分支因子有限的話），在任何情況下寬度優(yōu)先都能找到一個(gè)解，但是，它找到的第一個(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)。綜合來看，BFS和貪婪算法的效率較高，但解并非最優(yōu)，而A*算法的效率稍遜色，但解為最優(yōu)；DFS（回溯+剪枝）搜索雖能找到最優(yōu)解但效率最低。源代碼//pragma onceusing namespace std。define MaxV 20 /*ifndef MY_DEBUGdefine MY_DEBUG endif*/typedef struct{ char cityname[20]。//城市名 int value。//權(quán)值 int cost。//A*算法中從當(dāng)前節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)的預(yù)估費(fèi)用}Ver。class Graph{public: Graph()。 ~Graph()。 Ver V[MaxV]。 int edge[MaxV][MaxV]。 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)。//獲取V[index] 的ver 的value值 int GetVerCost(int index)。//獲取V[index] 的ver 的cost 值 int GetEdge(int row, int col)。//獲取edge[row][col] 的值 void SetVerCost(int index,int cost)。private:}。//pragma onceincludeiostreaminclude define MaxSize 30/*ifndef MY_DEBUGdefine MY_DEBUG endif/*/class SeqQueue{public: SeqQueue()。 ~SeqQueue()。 void QueueInitiate()。 int QueueNotEmpty()。 int QueueAppend(int x)。 int QueueDelete(int *d)。 int QueueOrderAppend(int x, Graph amp。G)。 //A*算法使用 int Queue_A_OrderAppend(int x, Graph amp。G)。private: int queue[MaxSize]。 int rear。 int front。 int count。}。 typedef SeqQueue SeqCQuene。//pragma onceinclude typedef struct{ int father。 int me。}way。class Romania_Trip{public: Romania_Trip()。 ~Romania_Trip()。 void Visit(int v, int u)。 void Print(Graph amp。graph, way *b, int end, int start)。 void BroadFirstSearch(Graph amp。graph, int v)。 void DepthFirstSearch(Graph amp。graph, int v,Stack amp。stack)。 void Greedy_Algorithms(Graph amp。graph, int v)。 void AStar_Algorithms(Graph amp。graph, int v)。 void ReSet()。 int GetCount()。 int GetMaxWeight()。 int GetEnd()。 way* GetB()。private: way *b。 int i。 int end。 int count。 int visitedCity[20]。 int MaxWeight。 int visited[20]。}。//pragma onceincludeincludeiostreamusing namespace std。/*ifndef MY_DEBUGdefine MY_DEBUG endif*/class Stack{public: Stack()。 ~Stack()。 bool StackNotFull()。 bool StakNotEmpty()。 void StackPop(Graph amp。G)。 void StackPush(int x, Graph amp。G)。 void PrintStack(Graph amp。G)。 int GetWeight()。private: int a[100]。 int top1。 int weight。}。//includeincludeiostreamincludeincludefstreamincludestringusing namespace std。Graph::Graph(){ numofedges = 0。}Graph::~Graph(){}void Graph::ReadVertex(){ int i=0, v。 char ch[20]。 fstream infile(, ios::in)。 while (infile ch amp。amp。 infile v) {ifdef MY_DEBUG printf(%s\t%d\n, ch, v)。endif V[i].value = v。 V[i].cost = 0。 strcpy(V[i].cityname, ch)。 i++。 }}void Graph::ReadEdge(){ int valu, i。 fstream infile(, ios::in)。 i = 0。 while (infile valu) { edge[i / 20][i % 20] = valu。ifdef MY_DEBUG if (i % 20 == 0)cout endl。 coutedge[i/20][i%20]\t。endif i++。 }}//取與第V個(gè)節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)int Graph::GetFirstVertex(int v){ if (v0 || v = 20) { return 1。 } for (int col = 0。 col20。 col++) if (edge[v][col]0 amp。amp。 edge[v][col]1000) return col。 return 1。}//找到第V1個(gè)節(jié)點(diǎn)的V2之后的下一個(gè)鄰接節(jié)點(diǎn)int Graph::GetNextVertex(int v1, int v2){ if (v10 || v1 = 20 || v20 || v2 = 20) { return 1。 } for (int col= v2 + 1。 col20。 col++) if (edge[v1][col]0 amp。amp。 edge[v1][col]1000) return col。 return 1。}int Graph::GetVerValue(int index)//獲取V[index] 的ver 的values值{ return V[index].value。}int Graph::GetVerCost(int index)//獲取V[index] 的ver 的cost 值{ return V[index].cost。}int Graph::GetEdge(int row, int col)//獲取edge[row][col] 的值{ return edge[row][col]。}void Graph::SetVerCost(int index, int cost){ V[index].cost = cost。}//includeincludeiostreaminclude SeqQueue::SeqQueue(){ rear = 0