人工智能實驗一

一．概述及要求

對于我們的實驗，先進行一個總的說明，之後進行各個算法的詳細介紹。由老師提供的readme文檔可得，我們的這次試驗要求我們對于書中學過的羅馬尼亞問題進行所有經典搜尋的實作，并對比他們的算法效率優劣。具體要求和參考步驟如下：

1：建立搜尋樹；

2：實作搜尋樹的寬度優先搜尋，深度優先搜尋，一緻代價搜尋，疊代加深的深度優先搜尋算法；

3：實作貪婪最佳優先搜尋和A*搜尋

4：使用編寫的搜尋算法代碼求解羅馬尼亞問題；

5：記錄各種算法的時間複雜度并繪制直方圖

二．問題描述

使用搜尋算法實作羅馬尼亞問題的求解

人工智能實驗一

根據書中說明我們假定起點是ARAD，終點是BUCHAREST。我們需要找到一條從起點到終點的路徑。

三．資料結構及輸入輸出

1.資料結構

首先根據羅馬尼亞問題的特點，我們把這個問題歸結為圖搜尋問題，是以建樹時不能忘記标記。同時我們注意到每個節點都有一個很長的英文名字，這不利于我們進行查找及搜尋，想到使用map的相關操作來實作序号（數字）與他名字的對應。有了這些啟示，我們可以建立如下的資料結構來容納我們的算法。

人工智能實驗一

建立标志數組，記錄圖中邊的情況的二維矩陣，規定輸入輸出流，用input，output代替cin,cout。

同時規定了初始節點和終點。

優先隊列比較标準：

由于我們的搜尋算法是基于結點的不同資訊，是以我們要為每一個節點建立結構體數組，分别儲存他們的名字，序号，深度，從起點到該點的路徑代價，從該點到終點的估計代價以及特定為優先隊列設計的擴充标準，即，先擴充f較小的那一個。

Map操作：

這裡比較重要的是使用了map的操作，這裡利于我學習的map操作的知識如下：

map 容器的insert成員與順序容器的類似，但有一點要注意：必須考慮鍵的作用。鍵影響了實參的類型：插入單個元素的insert版本使用鍵–值 pair 類型的參數。類似的，對于參數為一對疊代器的版本，疊代器必須指向鍵–值 pair 類型的元素。另一個差别則是：map容器的接受單個值的insert版本的傳回類型。map對象中一個給定鍵隻對應一個元素。如果試圖插入的元素所對應的鍵已經在容器中，則insert 将不做任何操作。這個insert 函數的實參是map<string,int>::value_type(“Anna”,1)。是一個新建立的pair 對象，将直接插入到map 容器中。謹記 value_type是pair< const K, V>類型的同義詞，K為鍵類型，V為鍵所關聯的值的類型。

是以我們這裡先定義一下map操作的名稱，name_id表示name轉id，id_name表示id轉name。

2.輸入函數設計

與之對應的，之後我們對map容器進行填充，兩個map都進行填充，這樣就實作了名字與編号的一一對應，并且是互相對應。

有了map這個基礎後輸入函數就可以直接輸入名字來建立節點之間的關系。

如圖，在城市數量限制下循環輸入，直接輸入名字後利于map操作将他們轉換為id，是以可以直接用名字後的數字來表示點點之間的路徑長度。同理，我們可以将每個節點到終點的估計代價填充完畢。具體輸入檔案如下：

四．不同算法實作

1.DFS

實驗名稱

用深度優先搜尋算法實作羅馬尼亞問題

實驗目的嘗試用深搜解決路徑最短問題。進而發現不同算法對于這個問題的優劣性。為以後的問題解決積累經驗。

實驗原理

從一個頂點v出發，首先将v标記為已周遊的頂點，然後選擇一個鄰接于v的尚未周遊的頂點u，如果u不存在，本次搜素終止。如果u存在，那麼從u又開始一次DFS。如此循環直到不存在這樣的頂點。

假設有如下樹，深度優先舉例：

實驗步驟

初始準備：建立棧，之後為節點通路數組動态配置設定好空間，初始化起點，将起點加入棧中，同時輸出起點資訊。

擴充：隻要棧不為空，先進行終點判斷，如果是終點，就輸出路徑代價，這個路徑代價記錄在結構體的g中。如果不是終點，我們就看這個節點與其他節點是否有邊且沒有通路過，如果滿足條件，就擴充該節點到邊連接配接的下一節點，實作擴充。

建立關系：下一節點要與之前的節點建立關系，首先是定義它的父節點為目前節點，再将這個節點定義為目前節點，最後在輸出這個節點的資訊。

回溯：如果搜尋完所有其他節點都沒有滿足判斷條件，就将該節點出棧，實作回溯。

重點：使用棧的結構，後進先出，是以剛剛擴充的節點會被接着擴充，不斷加深，實作深搜。

關鍵代碼

void DFS(){ //深度優先搜尋，使用棧，後進先出，lifo

stacks;//建立棧，内部資料存儲類型為node

memset(mark,0,sizeof(mark));//節點通路标志

node start;//定義初始節點

start.id = name_id[Start];

start.g = 0;

s.push(start);//初始節點入棧

output<<“DFSmodel:”<<endl;

output<<Start<<"->";

while(!s.empty()){

node temp = s.top();

if(temp.id == name_id[End]){

output<<“end”<<endl;

output<<“路徑代價為：”<<temp.g<<endl;

break;

}

mark[temp.id] = 1;//通路過添加标記

int x=0;

for(;x<num;x++){

if(!mark[x]&&bian[temp.id][x]!=0){//沒有通路過且目前節點與要加入的新節點有邊相連

node t;

t.id = x;

t.g = temp.g + bian[temp.id][x];//路徑代價累計

fu[t.id] = temp.id;//目前節點變為下一節點的父節點

s.push(t);

string name=id_name[t.id];

output<<name<<"->" ;

break;

}

if(x==num)

s.pop();//出棧,當搜尋完所有其他所有未标記節點也沒有找到可行節點時出棧，實作回溯。

}

} }

2.BFS

實驗名稱

用寬度優先搜尋算法實作羅馬尼亞問題

實驗目的

嘗試用寬搜解決路徑最短問題。進而發現不同算法對于這個問題的優劣性。為以後的問題解決積累經驗。

實驗原理

按層次來周遊的，先是根節點，然後是第二層子節點，依次是第三層子節點，将節點分别放入隊列中，每次從隊列中探出首元素，周遊後的點放入closed表中，還未周遊的店放入open表中，當open表為空時，則整個數周遊完全。

假設有如下樹，寬度優先舉例：

實驗步驟

初始準備：建立隊列，之後為節點通路數組動态配置設定好空間，初始化起點，将起點加入隊列中，同時輸出起點資訊。

擴充：隻要隊列不為空，先進行終點判斷，如果是終點，就輸出路徑代價，這個路徑代價記錄在結構體的g中。如果不是終點，我們就看這個節點與其他節點是否有邊且沒有通路過，如果滿足條件，就擴充該節點到邊連接配接的下一節點，實作擴充。

建立關系：下一節點要與之前的節點建立關系，首先是定義它的父節點為目前節點，再将這個節點定義為目前節點，最後在輸出這個節點的資訊。

重點：使用隊列的結構，先進先出，是以最後擴充的節點會被首先擴充，将一層節點擴充完後進入下一層，實作寬搜。

關鍵代碼

void BFS(){ //寬度優先搜尋

memset(mark,0,sizeof(mark));

node q[num*4];//建立node型數組，實際上作為隊列，實作先進先出的擴充順序。

for(int x=0;x<num;x++) fu[x]=x;

int l=0,r=1;

q[l].id = name_id[Start];

q[l].g = 0;

output<<“BFSmodel:”<<endl;

while(l<r){

node temp = q[l];

if(temp.id==name_id[End]){

output<<“end”<<endl;

output<<“路徑代價為：”<<q[l].g<<endl;

break;

}

mark[temp.id]=1;

for(int x=0;x<num;x++){

if(!mark[x]&&bian[temp.id][x]!=0){

q[r].id = x;

q[r].g = temp.g + bian[temp.id][x];

fu[q[r].id] = temp.id;//目前節點為擴充出節點的父節點

r++;//擴充出來的節點逐漸後排

}
    }
	string name=id_name[temp.id];
    output<<name<<"->" ;
    l++;//擴充下一節點

}

3.UCS

實驗名稱

用一緻代價搜尋算法實作羅馬尼亞問題

==實驗目的 ==

嘗試用UCS解決路徑最短問題。進而發現不同算法對于這個問題的優劣性。為以後的問題解決積累經驗。

實驗原理

在BFS的基礎上，一緻代價搜尋不在擴充深度最淺的節點，而是通過比較路徑消耗，并選擇目前代價最小的節點進行擴充，是以可以保證無論每一步代價是否一緻，都能夠找到最優解。

假設有如下樹，一緻代價優先舉例：

實驗步驟

初始準備：建立隊列，之後為節點通路數組動态配置設定好空間，初始化起點，将起點加入隊列中，同時輸出起點資訊。

建立關系：下一節點要與之前的節點建立關系，首先是定義它的父節點為目前節點，再将這個節點定義為目前節點，最後在輸出這個節點的資訊。

重點：同樣使用隊列的結構，但不是先進先出，他用了優先隊列，會根據啟發式函數進行擴充，這裡定義F是G，是以總路徑代價最小的節點會被首先擴充。

關鍵代碼

void UCS(){ //一緻代價搜尋

memset(mark,0,sizeof(mark));

for(int x=0;x<num;x++) fu[x]=x;

node start;

start.g = 0;

start.f = 0;

start.id = name_id[Start];

output<<“UCSmodel:”<<endl;

output<<Start<<"->";

priority_queue<node, vector, greater >p;//優先隊列

p.push(start);

while(!p.empty()){

node temp = p.top();

if(temp.id==name_id[End]){

output<<“end”<<endl;

output<<“路徑代價為：”<<p.top().g<<endl;

break;

}

mark[temp.id]=1;

p.pop();

for(int x=0;x<num;x++){

if(!mark[x]&&bian[temp.id][x]!=0){

node t;

t.id = x;

t.g = temp.g + bian[temp.id][x];

t.f = t.g;//啟發式函數定義為路徑耗散的加和。

fu[t.id] = temp.id;

string name=id_name[t.id];

output<<name<<"->" ;

p.push(t);

}

4.IDS

實驗名稱

用疊代加深搜尋算法實作羅馬尼亞問題

實驗目的

嘗試用疊代加深解決路徑最短問題。進而發現不同算法對于這個問題的優劣性。為以後的問題解決積累經驗。

==實驗原理 ==

疊代加深搜尋是以DFS為基礎的，它限制DFS遞歸的層數。

疊代加深搜尋的基本步驟是：

1、設定一個固定的深度depth，通常是depth = 1，即隻搜尋初始狀态

2、DFS進行搜尋，限制層數為depth，如果找到答案，則結束，如果沒有找到答案則繼續下一步

3、如果DFS途中遇到過更深的層，則++depth，并重複2；如果沒有遇到，說明搜索已經結束，沒有答案。

實驗步驟

初始準備：建立棧，之後為節點通路數組動态配置設定好空間，初始化起點，将起點加入棧中，同時輸出起點資訊。不同的是還要規定最大深度。

建立關系：下一節點要與之前的節點建立關系，首先是定義它的父節點為目前節點，再将這個節點定義為目前節點，最後在輸出這個節點的資訊。

回溯：如果搜尋完所有其他節點都沒有滿足判斷條件，就将該節點出棧，實作回溯。

深度判斷：首先是擴充節點時有是否超過目前深度的判斷，其次是最後再加一層目前深度是否超過最大深度的判斷，如果已經超過，就脫出函數。不超過重新載入，目前深度加一。

重點：同樣使用棧的結構，後進先出，是以剛剛擴充的節點會被接着擴充，不斷加深，實作深搜。但是再這個基礎上加上深度判斷。

關鍵代碼

void IDS(){ //疊代加深的深度優先搜尋

memset(mark,0,sizeof(mark));

int cur_dep = 1;

node start;

start.id = name_id[Start];

start.g = 0;

start.dep = 0;

stacks;//建立棧

s.push(start);

output<<“IDSmodel:”<<endl;

output<<Start<<"->";

while(!s.empty()){

node temp = s.top();

if(temp.id == name_id[End]){

output<<“end”<<endl;

output<<“路徑代價為：”<<temp.g<<endl;

break;

}

mark[temp.id] = 1;

int x=0;

for(;x<num;x++){

if(!mark[x]&&bian[temp.id][x]!=0&&temp.dep <= cur_dep){

node t;

t.id = x;

t.g = temp.g + bian[temp.id][x];

fu[t.id] = temp.id;

t.dep = temp.dep + 1;

string name=id_name[t.id];

output<<name<<"->" ;

s.push(t);

break;

}

if(x==num)

s.pop();//同樣的回溯過程

if(s.empty()){//周遊完所有節點後仍找不到目标節點，增加疊代加深過程，而不是直接退出

memset(mark,0,sizeof(mark));

s.push(start);//所有過程重新來

cur_dep++;//增加深度上限

}

5.GBFS

實驗名稱

用貪婪最佳優先搜尋算法實作羅馬尼亞問題

實驗目的

嘗試解決路徑最短問題。進而發現不同算法對于這個問題的優劣性。為以後的問題解決積累經驗。

實驗原理

最佳優先搜尋（Best First Search），是一種啟發式搜尋算法（Heuristic Algorithm）,我們也可以将它看做廣度優先搜尋算法的一種改進；最佳優先搜尋算法在廣度優先搜尋的基礎上，用啟發估價函數對将要被周遊到的點進行估價，然後選擇代價小的進行周遊，直到找到目标節點或者周遊完所有點，算法結束。

實驗步驟初始準備：建立隊列，之後為節點通路數組動态配置設定好空間，初始化起點，将起點加入隊列中，同時輸出起點資訊。

建立關系：下一節點要與之前的節點建立關系，首先是定義它的父節點為目前節點，再将這個節點定義為目前節點，最後在輸出這個節點的資訊。

重點：同樣使用隊列的結構，但不是先進先出，他用了優先隊列，會根據啟發式函數進行擴充，這裡定義F是估計值gu[]，是以到終點估計距離最小的節點會被首先擴充。

關鍵代碼

void GBFS(){ //貪婪最佳優先搜尋

memset(mark,0,sizeof(mark));

node start;

start.id = name_id[Start];

start.g = 0;

start.f = gu[start.id];

priority_queue<node, vector, greater >p;

p.push(start);

output<<“GBFSmodel:”<<endl;

output<<Start<<"->";

int sum=0;

while(!p.empty()){

node temp = p.top();
       if(temp.id==name_id[End]){
           output<<"end"<<endl;
           output<<"路徑代價為："<<p.top().g<<endl;
           break;
      }
      mark[temp.id]=1;
      p.pop();
      for(int x=0;x<num;x++){
         if(!mark[x]&&bian[temp.id][x]!=0){
            node t;
            t.id = x;
            t.g = temp.g + bian[temp.id][x];
            fu[t.id]=temp.id;
            t.f = gu[t.id];//啟發式函數定義為路徑估計值。 
            p.push(t);
            string name=id_name[t.id];
            output<<name<<"->" ;
        }
    }
 }

}

6.AS

實驗名稱

用A*搜尋算法實作羅馬尼亞問題

實驗目的嘗試用寬搜解決路徑最短問題。進而發現不同算法對于這個問題的優劣性。為以後的問題解決積累經驗。

實驗原理

基本原理：

公式表示為： f(n)=g(n)+h(n),

其中 f(n) 是從初始點經由節點n到目标點的估價函數，

g(n) 是在狀态空間中從初始節點到n節點的實際代價，

h(n) 是從n到目标節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在于估價函數f(n)的選取

實驗步驟

初始準備：建立隊列，之後為節點通路數組動态配置設定好空間，初始化起點，将起點加入隊列中，同時輸出起點資訊。

建立關系：下一節點要與之前的節點建立關系，首先是定義它的父節點為目前節點，再将這個節點定義為目前節點，最後在輸出這個節點的資訊。

重點：同樣使用隊列的結構，但不是先進先出，他用了優先隊列，會根據啟發式函數進行擴充，這裡定義F是估計值gu[]加上目前路徑總代價G，是以F最小的節點會被首先擴充。

關鍵代碼

void AS(){ //A*搜尋

memset(mark,0,sizeof(mark));

node start;

start.id = name_id[Start];

start.g = 0;

start.f = start.g + gu[start.id];

priority_queue<node, vector, greater >p;

p.push(start);

output<<“ASmodel:”<<endl;

output<<Start<<"->";

while(!p.empty()){

node temp = p.top();

if(temp.id==name_id[End]){

output<<“end”<<endl;

output<<“路徑代價為：”<<p.top().g<<endl;

break;

}

mark[temp.id]=1;

p.pop();

for(int x=0;x<num;x++){

if(!mark[x]&&bian[temp.id][x]!=0){

node t;

t.id = x;

t.g = temp.g + bian[temp.id][x];

fu[t.id]=temp.id;

t.f = t.g + gu[t.id];

p.push(t);

string name=id_name[t.id];

output<<name<<"->" ;

}

五．輸出結果總覽及對比：

人工智能實驗一

六．思考題

1：寬度優先搜尋，深度優先搜尋，一緻代價搜尋，疊代加深的深度優先搜尋算法哪種方法最優？

針對于我們這個羅馬尼亞問題來說，一緻代價搜尋找到了最優解，不過對于其他問題并不一定，要看具體建構好的樹的結構。如果是比較深的解，用深搜好點，比較淺的解用寬搜。深搜寬搜是兩種基礎思考模式，優化的話可以用基于此思想的其他搜尋模式

2：貪婪最佳優先搜尋和A搜尋那種方法最優？

A搜尋更優，由于A搜尋考慮到的f(n)=g(n)+h(n),但是貪婪最佳優先隻考慮了h(n)，而且A搜尋既是最優的，又是完備的。貪婪最佳優先沒有這種特性。

3：分析比較無資訊搜尋政策和有資訊搜尋政策。

人工智能中的搜尋政策大體分為兩種：無資訊搜尋和有資訊搜尋。無資訊搜尋是指我們不知道接下來要搜尋的狀态哪一個更加接近目标的搜尋政策，是以也常被成為盲目搜尋；而有資訊搜尋則是用啟發函數f（n）來衡量哪一個狀态更加接近目标狀态，并優先對該狀态進行搜尋，是以與無資訊搜尋相比往往能夠更加高效得解決問題。

人工智能實驗一

人工智能實驗一

繼續閱讀

KEKR的機器學習筆記二———神經網絡流程及如何矯正過拟合與欠拟合

Deep Reinforcement Learning 深度增強學習資源

基礎篇 | 06 Apriori 算法

PaddleOCR使用

資訊熵--決策樹的建立算法ID3中使用

為什麼使用梯度下降法或者梯度上升法

第一章.Classification -- 06.Evaluation Methods for Classifiers翻譯

色域

OpencvSharp

CLARANS算法

第一章.Classification -- 01.Introduction to Classification翻譯

什麼是深度學習(Deep Learning)1 The Development of Deep Learning2. 機器學習3. 深度學習與傳統神經網絡的差別

Reinforcement learning and Deep learning1.Artificial Intelligence2. Machine Learning3. Reinfrocement Learning4. Deep Learning5.Reinforcement Learning和Deep learning的差別6. Reference

Machine Learning in Action(4) —— Classifying with probability theory: naïve BayesMachine Learning in Action(4) —— Classifying with probability theory: naïve Bayes

基于内容推薦算法詳解

人工智能是什麼？歡迎大家邁入人工智能的大門