【文章內(nèi)容簡(jiǎn)介】 5 貪婪算法擴(kuò)展結(jié)點(diǎn)數(shù)為 4 所以在求解該問(wèn)題時(shí)，貪婪算法的效率最高，其次是 A*算法，然后是 BFS算法，最后是 DFS 算法。但是貪婪算法和 A*算法生成的節(jié)點(diǎn)數(shù)依賴于啟發(fā)函數(shù)的值，因此雖然對(duì)于本題來(lái)說(shuō)貪婪算法和 A*算法的效率很高，但是不能說(shuō)在所有搜索問(wèn)題中貪婪算法和 A*算法的效率都是最高的。 1）深度優(yōu)先搜索 // v0起始節(jié)點(diǎn) vg目標(biāo)節(jié)點(diǎn) // // Expand返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) // // SeqStack * S用堆棧存儲(chǔ)路徑信息 // // visited[]存儲(chǔ)路徑訪問(wèn)信息 // // G、 data[]用來(lái)讀取圖的各種信 // void DF_Search(AdjMGraph G, SeqStack * S, HeuristicG data[], int * Expand ,int v0, int vg, int visited[]) { int t, w。 //用于尋找目標(biāo)節(jié)點(diǎn) static int flag = 0。 static int DFS_flag = 0。 //標(biāo)志位 找到目標(biāo)節(jié)點(diǎn)后退出遞歸 StackPush(S,v0)。 //首先將起始節(jié)點(diǎn)入棧 flag++。 printf(%s ,data[v0].G)。 visited[v0]=1。 if(v0 != 1) w=GetFirstVex(G,v0,visited)。 //獲取第一個(gè)臨接點(diǎn) while(!DFS_flag amp。amp。 w != 1) 人工智能課程報(bào)告 9 { if(w == vg) { DFS_flag = 1。 *Expand = flag。 break。 } if(! visited[w] amp。amp。 w != vg amp。amp。 DFS_flag == 0) DF_Search(G, S, data, Expand, w, vg, visited)。 if(DFS_flag) break。 StackPop(S, amp。t)。 w = GetNextVex(G, v0, w, visited)。 } } 2）寬度優(yōu)先搜索 // v0起始節(jié)點(diǎn) vg目標(biāo)節(jié)點(diǎn) // // Expand返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) // // count返回路徑結(jié)點(diǎn)數(shù) // // BFS_path[]存儲(chǔ)路徑信息 // // G、 data[]用來(lái)讀取圖的各種信息 // void BF_Search(AdjMGraph G, HeuristicG data[], int v0,int vg, int *Expand, int * count, int visited[], int BFS_path[]) { int u,w,y,SumExpand=1, i=0。 SeqCQueue Q。 SeqStack SaveQ,LineSave。 //SaveQ 將出隊(duì)列的節(jié)點(diǎn)全部進(jìn)棧 ,LineSave 用于保存路徑 StackInitiate(amp。SaveQ)。 StackInitiate(amp。LineSave)。 printf(%s ,data[v0].G)。 visited[v0]=1。 QueueInitiate(amp。Q)。 QueueAppend(amp。Q,v0)。 //首先將起始節(jié)點(diǎn)入隊(duì)列 while(QueenNotEmpty(Q)) { QueueDelete(amp。Q,amp。u)。 StackPush(amp。SaveQ,u)。 //將每一個(gè)出隊(duì)列的結(jié)點(diǎn)進(jìn)行保存 w = GetFirstVex(G, u, visited)。 if(w == vg) 人工智能課程報(bào)告 10 { SumExpand++。 *Expand = SumExpand。 break。 } while(w != 1) { if( !visited[w]) { printf(%s ,data[w].G)。 visited[w] = 1。 QueueAppend(amp。Q,w)。 SumExpand++。 } w = GetNextVex(G, u, w, visited)。 } } StackPush(amp。LineSave,w)。//此時(shí) w 為目標(biāo)節(jié)點(diǎn) StackPush(amp。LineSave,u)。 //此時(shí) u 為 w 的父節(jié)點(diǎn) StackPop(amp。SaveQ,amp。u)。 while(StackNotEmpty(SaveQ)) { StackPop(amp。SaveQ,amp。u)。 StackTop(LineSave,amp。y)。 if ( Edge(G,u,y)==1 amp。amp。 visited[u]==1)//如果沒(méi)有相同的父親 ,被訪問(wèn)過(guò)，并且之間有邊則保存路徑 StackPush(amp。LineSave,u)。 } while(StackNotEmpty(LineSave)) { StackPop(amp。LineSave,amp。u)。 BFS_path[i++]=u。 * count = i。 } } 人工智能課程報(bào)告 11 3） A* 搜索 // v0起始節(jié)點(diǎn) vg目標(biāo)節(jié)點(diǎn) // // distance用來(lái)保存已經(jīng)過(guò)路徑值 // // Expand返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) // // G、 data[]用來(lái)讀取圖的各種信息 // void A_Search(AdjMGraph G, HeuristicG data[], int v0, int vg, int distance, int *Expand, int visited[]) { int i, u, temp=10000。 static int path_num = 0。 static int A_Search_flag = 0。 //標(biāo)志位 找到目標(biāo)節(jié)點(diǎn)后退出遞歸 static int fx = 0。 if(v0 == 2) printf(%s,data[v0].G)。 else printf(%s,data[v0].G)。 visited[v0] = 1。 path_num++。 if(v0 == vg) { A_Search_flag = 1。 *Expand = path_num。 return。 } for(i=0。i20。i++) { if(Edge(G, v0, i) amp。amp。 visited[i] == 0 amp。amp。 A_Search_flag == 0) { fx = distance+data[i].value+[v0][i]。 if(fx temp) { temp = fx。 u = i。 } } } A_Search( G, data, u, vg, distance+[v0][u], Expand, visited)。 人工智能課程報(bào)告 12 } 4）貪心搜索 // v0起始節(jié)點(diǎn) vg目標(biāo)節(jié)點(diǎn) // // Expand返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) // //