人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和a_算法求解“罗马利亚度假问题”(编辑修改稿)

人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和a_算法求解“罗马利亚度假问题”(编辑修改稿)内容摘要：

5 贪婪算法扩展结点数为 4 所以在求解该问题时，贪婪算法的效率最高，其次是 A*算法，然后是 BFS算法，最后是 DFS 算法。 但是贪婪算法和 A*算法生成的节点数依赖于启发函数的值，因此虽然对于本题来说贪婪算法和 A*算法的效率很高，但是不能说在所有搜索问题中贪婪算法和 A*算法的效率都是最高的。 1）深度优先搜索 // v0起始节点 vg目标节点 // // Expand返回扩展结点数 // // SeqStack * S用堆栈存储路径信息 // // visited[]存储路径访问信息 // // G、 data[]用来读取图的各种信 // void DF_Search(AdjMGraph G, SeqStack * S, HeuristicG data[], int * Expand ,int v0, int vg, int visited[]) { int t, w。 //用于寻找目标节点 static int flag = 0。 static int DFS_flag = 0。 //标志位 找到目标节点后退出递归 StackPush(S,v0)。 //首先将起始节点入栈 flag++。 printf(%s ,data[v0].G)。 visited[v0]=1。 if(v0 != 1) w=GetFirstVex(G,v0,visited)。 //获取第一个临接点 while(!DFS_flag amp。 amp。 w != 1) 人工智能课程报告 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）宽度优先搜索 // v0起始节点 vg目标节点 // // Expand返回扩展结点数 // // count返回路径结点数 // // BFS_path[]存储路径信息 // // G、 data[]用来读取图的各种信息 // 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 将出队列的节点全部进栈 ,LineSave 用于保存路径 StackInitiate(amp。 SaveQ)。 StackInitiate(amp。 LineSave)。 printf(%s ,data[v0].G)。 visited[v0]=1。 QueueInitiate(amp。 Q)。 QueueAppend(amp。 Q,v0)。 //首先将起始节点入队列 while(QueenNotEmpty(Q)) { QueueDelete(amp。 Q,amp。 u)。 StackPush(amp。 SaveQ,u)。 //将每一个出队列的结点进行保存 w = GetFirstVex(G, u, visited)。 if(w == vg) 人工智能课程报告 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)。 //此时 w 为目标节点 StackPush(amp。 LineSave,u)。 //此时 u 为 w 的父节点 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)//如果没有相同的父亲 ,被访问过，并且之间有边则保存路径 StackPush(amp。 LineSave,u)。 } while(StackNotEmpty(LineSave)) { StackPop(amp。 LineSave,amp。 u)。 BFS_path[i++]=u。 * count = i。 } } 人工智能课程报告 11 3） A* 搜索 // v0起始节点 vg目标节点 // // distance用来保存已经过路径值 // // Expand返回扩展结点数 // // G、 data[]用来读取图的各种信息 // 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。 //标志位 找到目标节点后退出递归 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)。 人工智能课程报告 12 } 4）贪心搜索 // v0起始节点 vg目标节点 // // Expand返回扩展结点数 // //。