一、实验目的

了解4种无信息搜索策略和2种有信息搜索策略的算法思想；

能够运用计算机语言实现搜索算法；

应用搜索算法解决实际问题(如罗马尼亚问题)；

学会对算法性能的分析和比较

二、实验硬件软件平台

硬件：计算机

软件：操作系统：WINDOWS 

应用软件：C,Java或者MATLAB

三、实验内容及步骤

使用搜索算法实现罗马尼亚问题的求解

讯享网

1：创建搜索树；

2：实现搜索树的宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法；

3：实现贪婪**优先搜索和A*搜索

4：使用编写的搜索算法代码求解罗马尼亚问题；

5：记录各种算法的时间复杂度并绘制直方图

源代码

#include<iostream> #include<stack> #include<vector> #include<iomanip> #include<queue> using namespace std; string city[20]={ "Oradea","Zerind","Arad","Timisoara","Lugoj","Mehadia","Drobeta","Sibiu","Rimnicu_vilcea","Craiova","Fagaras","Pitesti","Bucharest", "Giurgiu","Urzicenimneamt","Iasi","Vaslui","Hirsova","Eforie","Neamt" //城市名称 }; const int map[13][13]={ {0,71,-1,-1,-1,-1,-1,151,-1,-1,-1,-1,-1}, {71,0,75,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,75,0,118,-1,-1,-1,140,-1,-1,-1,-1,-1}, {-1,-1,118,0,111,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,111,0,70,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,70,0,75,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,75,0,-1,-1,120,-1,-1,-1}, {151,-1,140,-1,-1,-1,-1,0,80,-1,99,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,80,0,146,-1,97,-1,}, {-1,-1,-1,-1,-1,-1,120,-1,146,0,-1,138,-1}, {-1,-1,-1,-1,-1,-1,-1,99,-1,-1,0,-1,211}, {-1,-1,-1,-1,-1,-1,-1,-1,97,138,-1,0,101}, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,211,101,0} }; //存储一个图，在图上建立搜索树 int start=2,finish=12; //起始城市为Ared，终止城市为Bucharest int depth=1,width=1,un=1,iter=1,greed=1,star=1; //标记位，如果搜索到了目标城市，则终止，无需搜索全部路径 int sum=0,num=0; //记录代价值 int gred[]={380,374,366,329,244,241,242,253,193,160,176,100,0}; //直线距离，用于启发式搜索 void depth_serach(int begin,stack<int> temp,int *sign) { sign[begin]=1; //当前结点已经访问，避免死循环 if(begin==finish) //如果搜到了目标 { depth=0; cout<<"深度优先的路径为："; vector<int> result; while(!temp.empty()) { result.push_back(temp.top()); temp.pop(); } int size=result.size(); cout<<city[start]; for(int i=size-1;i>=0;i--) { if(i!=size-1) sum+=map[result[i+1]][result[i]]; else sum+=map[result[i]][2]; cout<<" -> "<<city[result[i]]; //计算代价和路径 } cout<<endl; sum+=map[result[0]][finish]; cout<<"总代价为："<<sum<<endl; cout<<"访问了"<<num<<"个结点"<<endl<<endl; return; } for(int i=0;i<13;i++) //找到可以扩展的结点，并递归扩展 { if(map[begin][i]>0 &&depth) { temp.push(i); if(sign[i]==0) { num++; sign[i]=1; depth_serach(i,temp,sign); sign[i]=0; } temp.pop(); } } } void iterative_deep_search(int begin,stack<int> temp,int *sign,int deep,int now) { sign[begin]=1; if(begin==finish) //如果搜到了目标，停止搜索，计算代价和路径 { iter=0; cout<<"迭代加深的深度优先搜索路径为："; vector<int> result; while(!temp.empty()) { result.push_back(temp.top()); temp.pop(); } int size=result.size(); cout<<city[start]; for(int i=size-1;i>=0;i--) { if(i!=size-1) sum+=map[result[i+1]][result[i]]; else sum+=map[result[i]][2]; cout<<" -> "<<city[result[i]]; } sum+=map[result[0]][finish]; cout<<endl<<"搜索代价为："<<sum<<endl; cout<<"搜索深度为："<<now<<endl; cout<<"搜索了"<<num<<"个结点。"<<endl<<endl; return; } //deep++; for(int i=0;i<13;i++) //如果找到了可以扩展的结点，那么扩展它 { if(map[begin][i]!=-1&&iter) { temp.push(i); if(sign[i]==0) { num++; sign[i]=1; if(now<deep) //如果还没有超过深度限制，那么可以继续递归下一层 { now++; iterative_deep_search(i,temp,sign,deep,now); now--; } sign[i]=0; } temp.pop(); } } } void width_search(int begin,int *sign) { int cost[13]={0,0,0,0,0,0,0,0,0,0,0,0,0}; int father[13]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; queue<int> Q; cout<<"宽度优先搜索的路径为："<<city[begin]; for(int i=0;i<13;i++) //扩展可以扩展的结点，并加入队列依次扩展 if(map[begin][i]>=0 && width) { num++; if(sign[i]==0) { sign[i]=1; Q.push(i); cost[i]=map[begin][i]; father[i]=begin; //更新父结点的值 } } while(!Q.empty()) //循环扩展，直到所有结点都被扩展 { int x=Q.front(); Q.pop(); if(x==finish) { vector<int> show; int tmp=12; while(tmp!=2) { show.push_back(tmp); tmp=father[tmp]; //依据父结点，递推倒序输出即为路径 } for(int i=show.size()-1;i>=0;i--) { cout<<" -> "; cout<<city[show[i]]; } cout<<endl<<"搜索代价为："<<cost[x]<<endl; //cost记录当前结点的搜索代价 cout<<"访问了"<<num<<"个结点。"<<endl<<endl; break; } for(int i=0;i<13;i++) if(map[x][i]>=0 && width) { if(sign[i]==0) { num++; sign[i]=1; Q.push(i); cost[i]=map[x][i]+cost[x]; //对于之后的扩展结点，代价需要累加更新 father[i]=x; } } } } int find(vector<int> temp,int key) { for(int i=0;i<temp.size();i++) { if(key==temp[i]) return i; } return -1; } int min(int a,int b) { if(a>b) return b; return a; } void un_cost_search(int begin,stack<int> temp,int *sign,vector<int> cost,int cur,vector<int> node,int father[]) { if(begin==finish) //搜到了目标就计算路径和总代价 { un=0; cout<<endl<<"一致代价搜索路径为："; int tmp=12; vector<int> result; while(tmp!=2) { result.push_back(tmp); tmp=father[tmp]; //递推父结点，输出路径 } result.push_back(tmp); int size=result.size(); for(int i=size-1;i>=0;i--) { cout<<city[result[i]]; if(i!=0) cout<<" -> "; } cout<<endl<<"搜索代价为："<<cur<<endl; cout<<"访问了"<<num<<"个结点。"<<endl<<endl; return; } int p=-1; for(int i=0;i<13;i++) { if(map[begin][i]!=-1) { if(sign[i]==0) { num++; p=1; if(find(node,i)==-1) //只有当前被扩展的结点，才会被标记访问，因为此时该结点代价已经能确保最小，如果只是被搜到，那么不能被标记已访问，因此会重复搜索 { father[i]=begin; node.push_back(i); if(begin==2) cost.push_back(map[begin][i]); else cost.push_back(map[begin][i]+cur); } else { cost[find(node,i)]=min(cost[find(node,i)],map[begin][i]+cur); //既然会重复访问结点，那么需要更新结点的最小代价，可能是新路径代价最小，也可能是加上当前边最小 if(cost[find(node,i)]==map[begin][i]+cur) father[i]=begin; //如果是新的路径更小，那么切换它的父结点到新的路径上来 } } } } int size=node.size(); for(int i=0;i<size;i++) { for(int i1=i;i1<size;i1++) //对结点依据代价排序，扩展已访问结点中代价最小的那个，名称也相应交换位置 { if(cost[i1]<cost[i]) { int t=node[i1]; node[i1]=node[i]; node[i]=t; t=cost[i1]; cost[i1]=cost[i]; cost[i]=t; } } } for(int i=0;i<node.size();i++) cout<<city[node[i]]<<"（"<<cost[i]<<"） "; cout<<endl; temp.push(begin); p=node[0]; cur=cost[0]; cout<<"搜索："<<city[p]<<endl; sign[p]=1; node.erase(node.begin()); //扩展结点之后删除它 cost.erase(cost.begin()); un_cost_search(p,temp,sign,cost,cur,node,father); } void greedy_bestfirst_search(int begin,stack<int> temp,int *sign) { if(begin==finish) { greed=0; cout<<"贪婪**优先搜索路径为："; vector<int> result; while(!temp.empty()) { result.push_back(temp.top()); temp.pop(); } int size=result.size(); for(int i=size-1;i>=0;i--) { if(i!=size-1) sum+=map[result[i+1]][result[i]]; else sum+=map[result[i]][2]; cout<<city[result[i]]<<" -> "; } sum+=map[result[0]][finish]; cout<<city[finish]; cout<<endl<<"搜索代价为："<<sum<<endl; cout<<"访问了"<<num<<"个结点。"<<endl<<endl; return; } int p=-1; vector<int> temp2; for(int i=0;i<13;i++) { if(map[begin][i]!=-1&&greed) //如果结点可以扩展，有相邻边，那么加入队列 { if(sign[i]==0) { num++; p=1; temp2.push_back(i); } } } int size= temp2.size(); for(int i=0;i<size;i++) //对于预期代价排序，搜索预期代价最小的那个结点并扩展 { for(int i1=i;i1<size;i1++) { if(gred[temp2[i1]]<gred[temp2[i]]) { int t=temp2[i1]; temp2[i1]=temp2[i]; temp2[i]=t; } } } if(p!=-1&&greed) { temp.push(begin); for(int i=0;i<temp2.size();i++) { sign[i]=1; p=temp2[i]; greedy_bestfirst_search(p,temp,sign); sign[i]=0; } } } void A_star_search(int begin,stack<int> temp,int *sign,vector<int> temp2,vector<int> cost) { int p=-1; int parent; for(int i1=0;i1<cost.size();i1++) { if(begin==temp2[i1]) { parent=i1; break; } } for(int i=0;i<13;i++) { if(map[begin][i]>0&&star) { num++; p=1; temp2.push_back(i); cost.push_back(cost[parent]+map[begin][i]); } } int size=temp2.size(); for(int i=0;i<size;i++) { for(int i1=i;i1<size;i1++) { if(cost[i1]+gred[temp2[i1]]<cost[i]+gred[temp2[i]]) //对于所有可扩展结点的已花费代价和直线距离之和排序，扩展最小的那一个 { int t1=cost[i1]; cost[i1]=cost[i]; cost[i]=t1; int t=temp2[i1]; temp2[i1]=temp2[i]; temp2[i]=t; } } } for(int i=0;i<temp2.size();i++) //待扩展的结点需要被删除，以免重复扩展 { if(sign[temp2[i]]==1) { temp2.erase(temp2.begin()+i); cost.erase(cost.begin()+i); sign[i]==0; } } if(p!=-1&&star) { size=temp2.size(); for(int i=0;i<temp2.size()&&star;i++) { sign[temp2[i]]=1; if(map[begin][temp2[i]]!=-1) { temp.push(begin); if(temp2[i]==finish) //如果搜到了目标，停止搜索 { temp.pop(); star=0; cout<<"A*搜索路径为："; vector<int> result; while(!temp.empty()) { result.push_back(temp.top()); temp.pop(); } int size=result.size(); for(int i=size-1;i>=0;i--) { if(i!=size-1) sum+=map[result[i+1]][result[i]]; else sum+=map[result[i]][2]; cout<<city[result[i]]<<" -> "; } sum+=map[result[0]][finish]; cout<<city[finish]; cout<<endl; cout<<"搜索代价为："<<sum<<endl; cout<<"访问了"<<num<<"个结点。"<<endl; return; } p=temp2[i]; //如果还没搜到目标，递归下一层 A_star_search(p,temp,sign,temp2,cost); sign[temp2[i]]=0; temp.pop(); } } } } int main() { sum=0,num=0; stack<int> p1; int sign1[]={0,0,1,0,0,0,0,0,0,0,0,0,0}; width_search(start,sign1); sum=0,num=0; stack<int> p; int sign[]={0,0,0,0,0,0,0,0,0,0,0,0,0}; depth_serach(start,p,sign); sum=0,num=0; vector<int> cost1; vector<int> node; stack<int> p2; int sign2[]={0,0,1,0,0,0,0,0,0,0,0,0,0}; int father[]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; un_cost_search(start,p2,sign2,cost1,0,node,father); sum=0,num=0; int deep=0; while(iter) { deep++; stack<int> ptemp; int sign_temp[]={0,0,0,0,0,0,0,0,0,0,0,0,0}; iterative_deep_search(start,ptemp,sign_temp,deep,0); } sum=0,num=0; stack<int> p3; int sign3[]={0,0,1,0,0,0,0,0,0,0,0,0,0}; greedy_bestfirst_search(start,p3,sign3); sum=0,num=0; stack<int> p4; int sign4[]={0,0,1,0,0,0,0,0,0,0,0,0,0}; vector<int> load; sum=0,num=0; vector<int> cost2; cost2.push_back(0); load.push_back(start); A_star_search(start,p4,sign4,load,cost2); return 0; }

算法原理分析

1、宽度优先搜索（本题中，为了证明某些算法非最优，只搜索一条路径就停下来）

宽度优先搜索，先扩展根节点，然后再扩展根节点所有的后继结点；然后扩展后继结点中的后继节点。我用stack p1来存储已扩展节点，用数组sign1存储13个城市是否被扩展，将它传入递归函数width_search(int begin,stack<int> temp,int *sign),该函数begin为已经扩展的节点，准备扩展它的所有后继节点，sign为扩展到当前节点过程中，已经扩展的城市记录。在函数中间，如果扩展节点为目的城市，则将stack中输出，并将width标记为0，表示已经找到了目的城市，之后的不用再进行扩展。

在输出搜索结果路径的时候，声明了一个父结点数组，全部初始化为-1。当该节点被发现的时候，父结点被更改为发现它的结点，此时，输出的时候就能够通过数组中元素与下标的递推关系，反向打印出路径来。

2、深度优先搜索

深度优先搜索，总是扩展当前边缘节点最深的节点。depth_serach(int begin,stack<int> temp,int *sign)，该算法通过递归函数depth_serach实现，用stack p1来存储已扩展节点，用数组sign1存储13个城市是否被扩展。Begin为当前扩展节点，通过一个for循环搜索其子节点，如果自己的为扩展，则扩展该子节点，调用递归函数继续扩展子节点，直到最后扩展到目的城市，则将depth标记为0，停止后续的调用。

3、一致代价搜索

一致代价搜索，是搜索当前所有节点中，选择达到该节点所需要花费代价最少的点，进行下一步扩展。因此我们需要在宽度优先的基础上加入对于每一个结点当前所需代价的值，并进行从小到大的排序，每次扩展队首的点，并删除，将新加入的结点加入队列，再次进行排序，直到扩展的结点即为所求终点。

值得注意的是，在访问过程中，如搜索到了结束结点，那么搜索过程仍然不会结束；只有当前扩展的结点就是结束结点，那么搜索才算结束，因为仅仅搜索到了结点，证明条件还不够说明这条路径就是最优化的，而一致代价中，只有当前结点被选为了扩展结点，那么此时这个结点的代价值才是最优的。

当多次搜索到同一个结点的时候，需要对于不同路径权值进行判断。更新该节点所需要的最少权值，并更新父结点。

4、迭代加深搜索

迭代加深的深度优先搜索，在宽度优先的基础上进行扩展，逐渐加深迭代深度。在代码中，Deep为迭代深度，我们将迭代深度不断加深，迭代深度就是iterative_deep_search函数可以调用的次数，只有迭代深度最后一位为当前迭代深度，只有满足now<deep，才可以继续迭代。因为每次迭代的时候都需要从根结点重新访问，因此搜索的复杂度比较高。

5、贪婪**优先搜索

贪婪**优先搜索，与一致代价搜索类似，只是在判断对判断扩展哪个后继的时候，通过gred数组来判断扩展哪个后继节点，然后按照依次扩展后继节点。

6、A*搜索

A*搜索，与贪婪**搜索相似，只是在判断对扩展哪个后继时，通过gred和cost来判断扩展哪个节点，gred为直线距离启发式，cost为到当前节点的路径消耗，按照这个两个值对准备扩展节点进行排序，按照最小的值来一次扩展。

运行结果

1、输出情况

2、复杂度分析（我用了访问结点数量，代替程序代码运行时间，来反映复杂度的关系）

思考题

1、宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法哪种方法最优？

答：一致代价搜索是最优的。一致代价搜索扩展所有当前可扩展结点中，已消耗代价最小的点，且及时更新其他结点的代价值（如果有一条代价更小的路到达结点，那么更新那个结点的代价，并更新父结点）这样能够保证结点被扩展到的时候，它已经是最优。相比之下，深度优先搜索和迭代加深搜索会默认搜索出深度最小的路径，但不一定最优，而深度优先搜索则受到搜索偏好（结点编号等）影响，性能难以控制。

2、贪婪**优先搜索和A*搜索那种方法最优？

答：A*搜索最优。这两种搜索算法都是有信息搜素策略，但是贪婪搜索算法只会向着启发式函数代价最低的点进行，这样有可能错过实际代价最低的路径，而A*类似于一致代价，扩展到的结点就能够保证已经找到了该节点的最优路径，因此当A*扩展到目标结点的时候搜索结束，也就能保证最优性。

3、分析比较无信息搜索策略和有信息搜索策略。

答：无信息搜索只基于路径消耗，可以说只是简单计算达到各个结点所需要的消耗值并比较；而有信息搜索策略需要有一个启发式函数，搜索根据启发式函数的值进行（贪婪）或是结合路径消耗一起进行（A星）。