一、實驗目的
了解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()&☆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星）。