C++基于人工智能搜索策略解決農(nóng)夫過河問題示例
本文實例講述了C++基于人工智能搜索策略解決農(nóng)夫過河問題。分享給大家供大家參考,具體如下:
問題描述
一農(nóng)夫帶著一頭狼,一只羊和一個白菜過河,小船只能一次裝載農(nóng)夫和一樣貨物,狼會吃羊,羊會吃白菜,只有農(nóng)夫在時才安全?,F(xiàn)欲讓所有物品包括農(nóng)夫都安全過道河對岸,求最佳答案。
狀態(tài)空間
用16*4的矩陣:a[16][4],存放每一步的狀態(tài),第一列表示農(nóng)夫的狀態(tài),第二列表示菜的狀態(tài),第三列表示羊的狀態(tài),第四列表示狐貍的狀態(tài),數(shù)組a里面的元素只為0或1,0代表在左岸,1代表在右岸。
初始狀態(tài)a[0][0]=a[0][1]=a[0][2]=a[0][3]=0,目標(biāo)狀態(tài)是矩陣的某一行全為1。
操作規(guī)則
1. 農(nóng)夫做往返運動,即第i步中,a[i][0] = i%2。
2. 每次農(nóng)夫過河,可以選擇帶一件貨物,也可以選擇不帶。
3. 在農(nóng)夫不在場的情況下,狼和羊不能在一起,羊和白菜不能在一起。
搜索策略
為了避免重復(fù),我們將搜索過的狀態(tài)放到set中,之后避開搜索這個狀態(tài)即可。
我們使用深度優(yōu)先搜索。搜索過程為:農(nóng)夫做往返運動,當(dāng)農(nóng)夫從左岸到右岸時,優(yōu)先選擇帶貨物過河,當(dāng)農(nóng)夫從右岸到左岸時,優(yōu)先選擇不帶貨物過河。做出選擇之后,前進(jìn)一步,看看是否達(dá)到目標(biāo)狀態(tài),如果沒有達(dá)到,則農(nóng)夫繼續(xù)往返,知道搜索到目標(biāo)狀態(tài),或者找不到解為止。
C++代碼實現(xiàn)
#include <iostream> #include <cstring> #include <string> #include <set> using namespace std; void search(int i); int a[16][4]; set<int> s; int b[16]; string ss[2]; string t[4]; int k; int level; int count1(int a[])//將當(dāng)前狀態(tài)轉(zhuǎn)化為10進(jìn)制數(shù) { return a[0]*8+a[1]*4+a[2]*2+a[3]; } void show(int a[])//顯示結(jié)果函數(shù) { cout<<" 左邊:"; for(int i=1;i<=3;i++) if(a[i]==0) cout<<t[i]<<" "; cout<<" "; cout<<"右邊:"; for(int i=1;i<=3;i++) if(a[i]==1) cout<<t[i]<<" "; cout<<endl<<endl; } void bringSomething(int i)//假設(shè)農(nóng)夫會帶走某個東西 { for(int j=1;j<=3;j++) { if(a[i][j]==a[i][0])//若j原來和農(nóng)夫同一個位置,則農(nóng)夫有可能將j帶走。 { a[i+1][j]=a[i+1][0];//假設(shè)將j帶走 if((!(a[i+1][1]==a[i+1][2]&&a[i+1][1]!=a[i+1][0]||a[i+1][3]==a[i+1][2]&&a[i+1][2]!=a[i+1][0]))&&s.count(count1(a[i+1]))==0&&i>=level)//第i+1層將j帶走時滿足條件,則繼續(xù)搜索第i+1層 { s.insert(count1(a[i+1])); b[i]=1; cout<<ss[a[i][0]]<<t[j]<<" "; show(a[i+1]); level++; search(i+1); } else //若不滿足條件則恢復(fù) { a[i+1][j]=a[i][j]; } } } } void bringNothing(int i)//假設(shè)農(nóng)夫什么也不帶走 { if((!(a[i+1][1]==a[i+1][2]&&a[i+1][1]!=a[i+1][0]||a[i+1][3]==a[i+1][2]&&a[i+1][2]!=a[i+1][0]))&&s.count(count1(a[i+1]))==0&&i>=level) { if(i==0) cout<<"農(nóng)夫從左邊去右邊,什么也不帶"; else cout<<"農(nóng)夫從右邊回左邊,什么也不帶"; show(a[i+1]); s.insert(count1(a[i+1])); search(i+1); level++; } else b[i]=0; } void search(int i)//從第i層開始搜索判斷第i+1層可能的情況 { if(i>=16||count1(a[i])==15) return; for(int j=1;j<=3;j++)//用第i層來初始化第i+1層 { a[i+1][j]=a[i][j]; } b[i]=-1; if(i%2==1)//在右岸,先考慮農(nóng)夫什么也不帶走 { bringNothing(i); if(b[i]==0) bringSomething(i); } else{//在左岸,先考慮農(nóng)夫會帶走某一樣?xùn)|西。 bringSomething(i); if(b[i]!=1) bringNothing(i); } } int main() { ss[0]="農(nóng)夫從左邊去右邊,帶上"; ss[1]="農(nóng)夫從右邊回左邊,帶上"; t[1]="菜"; t[2]="羊"; t[3]="狐貍"; memset(a,0,sizeof(a)); for(int i=0;i<16;i++) { a[i][0]=i%2; } s.clear(); k=0; level=0; s.insert(0); //先將初始狀態(tài)儲存起來 search(0); //從第0層開始搜索 for(int i=0;i<16;i++) { for(int j=0;j<4;j++) cout<<a[i][j]<<" "; cout<<endl; if(count1(a[i])==15) break; } return 0; }
結(jié)果
農(nóng)夫從右邊回左邊,什么也不帶 左邊:菜 狐貍 右邊:羊 農(nóng)夫從左邊去右邊,帶上菜 左邊:狐貍 右邊:菜 羊 農(nóng)夫從右邊回左邊,帶上羊 左邊:羊 狐貍 右邊:菜 農(nóng)夫從左邊去右邊,帶上狐貍 左邊:羊 右邊:菜 狐貍 農(nóng)夫從右邊回左邊,什么也不帶 左邊:羊 右邊:菜 狐貍 農(nóng)夫從左邊去右邊,帶上羊 左邊: 右邊:菜 羊 狐貍 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1
希望本文所述對大家C++程序設(shè)計有所幫助。
- 基于C++的農(nóng)夫過河問題算法設(shè)計與實現(xiàn)方法
- Java遞歸算法經(jīng)典實例(經(jīng)典兔子問題)
- Java實現(xiàn)的猴子吃桃問題算法示例
- Java數(shù)據(jù)結(jié)構(gòu)及算法實例:漢諾塔問題 Hanoi
- Java基于循環(huán)遞歸回溯實現(xiàn)八皇后問題算法示例
- 淺談java實現(xiàn)背包算法(0-1背包問題)
- Java矩陣連乘問題(動態(tài)規(guī)劃)算法實例分析
- Java算法之最長公共子序列問題(LCS)實例分析
- Java基于遞歸解決全排列問題算法示例
- Java基于分治算法實現(xiàn)的棋盤覆蓋問題示例
- Java簡單實現(xiàn)農(nóng)夫過河問題示例
相關(guān)文章
C語言編程中從密碼文件獲取數(shù)據(jù)的函數(shù)總結(jié)
這篇文章主要介紹了C語言編程中從密碼文件獲取數(shù)據(jù)的函數(shù)總結(jié),包括getpw()函數(shù)和getpwnam()函數(shù)以及getpwuid()函數(shù),需要的朋友可以參考下2015-08-08