農夫過河演算法
『壹』 演算法「農夫過河」程序 望高手指錯修改
v!=1111
能這么用么,這里的1111應該是十進制的1111了吧.
bitset沒用過,不知道是不是要用
v.to_ulong()!=0x0F
演算法上也有問題,就是當某種走法不成功時,退回上層遞歸後,沒有回復到走之前的狀態.應該設個臨時變數等於v,對臨時變數進行flip和search遞歸.
另外,採用某種走法前的判斷if語句也有問題,比如v[farmer]==v[sheep],我們已經知道正確走法的第一步就是農夫和羊過,但第二步的時候, 農夫和羊都在對岸,值都是1,仍相等,就又都走回來了.
我個人認為,這個問題應該構造樹,然後層次遍歷,而現在的程序是深度優先遍歷.
『貳』 農夫過河的圖演算法
#include<iostream>
using namespace std;
#define VertexNum 16 //最大頂點數
typedef struct // 圖的頂點
{
int farmer; // 農夫
int wolf; // 狼
int sheep; // 羊
int veget; // 白菜
}Vertex;
typedef struct
{
int vertexNum; // 圖的當前頂點數
Vertex vertex[VertexNum]; // 頂點向量（代表頂點）
bool Edge[VertexNum][VertexNum]; // 鄰接矩陣. 用於存儲圖中的邊，其矩陣元素個數取決於頂點個數，與邊數無關
}AdjGraph; // 定義圖的鄰接矩陣存儲結構
bool visited[VertexNum] = {false}; // 對已訪問的頂點進行標記（圖的遍歷）
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路徑，即與某頂點到下一頂點的路徑
// 查找頂點（F，W，S，V）在頂點向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 從0開始查找
for (int i = 0; i < graph->vertexNum; i++)
{
if ( graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf
&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget )
{
return i; //返回當前位置
}
}
return -1; //沒有找到此頂點
}
// 判斷目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//當農夫與羊不在一起時，狼與羊或羊與白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true; // 安全返回true
}
}
// 判斷狀態i與狀態j之間是否可轉換
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三個條件不同時滿足兩個且農夫狀態改變時，返回真, 也即農夫每次只能帶一件東西過橋
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 創建連接圖
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的圖的頂點
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 鄰接矩陣初始化即建立鄰接矩陣
graph->vertexNum = i;
for (i = 0; i < graph->vertexNum; i++)
{
for (j = 0; j < graph->vertexNum; j++)
{
// 狀態i與狀態j之間可轉化，初始化為1，否則為0
if (isConnect(graph, i, j))
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判斷在河的那一邊
char* judgement(int state)
{
return ( (0 == state) ? "左岸" : "右岸" );
}
// 輸出從u到v的簡單路徑，即頂點序列中不重復出現的路徑
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;
cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;
while (i != end)
{
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
i = retPath[i];
}
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
}
// 深度優先搜索從u到v的簡單路徑 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //標記已訪問過的頂點
if (start == end)
{
return ;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);
if (visited[end]) // 有結果
{
printPath(&graph, start, end);
return 0;
}
return -1;
}
『叄』 高分跪求求過河問題程序演算法！
paddy102的專欄
CSDNBlog | 我的首頁 | 聯系作者 | 聚合 | 登錄 5篇文章 :: 0篇收藏:: 0篇評論:: 0個Trackbacks
文章
C++/Visual C++(RSS)
演算法設計(RSS)
游戲開發(RSS)
收藏
相冊
存檔
2004年06月(4)
2004年04月(1)
野人過河問題演算法分析
野人過河問題演算法分析
野人過河問題屬於人工智慧學科中的一個經典問題，問題描述如下： 有三個牧師（也有的翻譯為傳教士）和三個野人過河，只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數大於牧師的人數，那麼牧師就會有危險. 你能不能找出一種安全的渡河方法呢？
一、演算法分析
先來看看問題的初始狀態和目標狀態，假設和分為甲岸和乙岸：
初始狀態：甲岸，3野人，3牧師；
乙岸，0野人，0牧師；
船停在甲岸，船上有0個人；
目標狀態：甲岸，0野人，0牧師；
乙岸，3野人，3牧師；
船停在乙岸，船上有0個人；
整個問題就抽象成了怎樣從初始狀態經中間的一系列狀態達到目標狀態。問題狀態的改變是通過劃船渡河來引發的，所以合理的渡河操作就成了通常所說的算符，根據題目要求，可以得出以下5個算符（按照渡船方向的不同，也可以理解為10個算符）：
渡1野人、渡1牧師、渡1野人1牧師、渡2野人、渡2牧師
算符知道以後，剩下的核心問題就是搜索方法了，本文採用深度優先搜索，通過一個FindNext(…)函數找出下一步可以進行的渡河操作中的最優操作，如果沒有找到則返回其父節點，看看是否有其它兄弟節點可以擴展，然後用Process(…)函數遞規調用FindNext(…)，一級一級的向後擴展。
搜索中採用的一些規則如下：
1、渡船優先規則：甲岸一次運走的人越多越好（即甲岸運多人優先），同時野人優先運走；
乙岸一次運走的人越少越好（即乙岸運少人優先），同時牧師優先運走；
2、不能重復上次渡船操作（通過鏈表中前一操作比較），避免進入死循環;
3、任何時候河兩邊的野人和牧師數均分別大於等於0且小於等於3；
4、由於只是找出最優解，所以當找到某一算符（當前最優先的）滿足操作條件後，不再搜索其兄弟節點，而是直接載入鏈表。
5、若擴展某節點a的時候，沒有找到合適的子節點，則從鏈表中返回節點a的父節點b，從上次已經選擇了的算符之後的算符中找最優先的算符繼續擴展b。
二、基本數據結構
仔細閱讀問題，可以發現有些基本東西我們必須把握，例如：每時刻河兩岸野人牧師各自的數目、船的狀態、整個問題狀態。所以我們定義如下幾個數據結構：
typedef struct _riverside // 岸邊狀態類型
{
int wildMan; // 野人數
int churchMan; // 牧師數
}RIVERSIDE;
typedef struct _boat // 船的狀態類型
{
int wildMan; // 野人數
int churchMan; // 牧師數
}BOAT;
typedef struct _question // 整個問題狀態
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸為-1, 乙岸為1
BOAT boat; // 船的狀態
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向後一渡船操作
}QUESTION;
用QUESTION來聲明一個最基本的鏈表。
三、程序流程及具體設計
本文只找出了最優解，據我所知，本問題有三種解。如果真要找出這三種解，^_^，那就得加強對鏈表的操作了，比如說自己寫一個動態鏈表類，順便完成一些初始化工作，估計看起來會舒服些。
下面給出部分關鍵程序：
// 主函數
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍歷鏈表輸出結果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎樣才能渡河呢? 郁悶!"<<endl;
// 回收內存空間
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}
// 渡船過程, 遞規調用函數FindNext(...)
BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan + pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest->riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew->riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew->riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew->riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
if (pPrev == NULL)
return FALSE; // 無解
delete pQuest;
pPrev->pNext = NULL;
return Process(pPrev); // 返回其父節點重新再找
}
return TRUE;
}
// 判斷有否下一個渡河操作, 即根據比較算符找出可以接近目標節點的操作
// 算符共5個: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
BOOL FindNext(QUESTION* pQuest)
{
// 基本規則
// 渡船的優先順序: 甲岸運多人優先, 野人優先; 乙岸運少人優先, 牧師優先.
static BOAT boatState[5]; // 5個算符
if (pQuest->side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用來控制算符
if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始狀態, 第一次渡河時
i = 0; // 取算符1
else
{
for (i=0; i<5; i++) // 擴展同一節點時, 已經用過的算符不再用, 按優先順序來
if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)
break;
i++;
}
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;
int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判斷本次操作的安全性, 即牧師數量>=野人或牧師數為0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重復上次操作,注意方向不同
if (pQuest->pPrev != NULL)
{
if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&
pQuest->pPrev->boat.churchMan == boatState[j].churchMan)
continue;
}
break; // 該操作可行, 推出循環，只找出當前最優節點
}
}
if (j < 5)
{
pQuest->boat.wildMan = boatState[j].wildMan;
pQuest->boat.churchMan = boatState[j].churchMan;
return TRUE;
}
}
return FALSE;
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=21630
[點擊此處收藏本文] 發表於 2004年04月07日 2:18 PM
沒有評論。
發表評論
大名：
請輸入尊姓大名
網址：
驗證碼
評論
請輸入評論
記住我？
--------------------------------------------------------------------------------
網站簡介－廣告服務－網站地圖－幫助信息－聯系方式－English－問題報告
CSDN北京百聯美達美數碼科技有限公司 版權所有 京 ICP 證 020026 號 CSDN
&; 2000-04, CSDN.NET, All Rights Reserved
--------------------------------------------------------------------------------
Copyright &; paddy102 Powered By .Text
『肆』 廣度優先 演算法，各位幫幫。。急
個人對廣度優先演算法的理解是每次優先遍歷父結點下的直接子結點，遍歷完這些直接子結點之後再從這些子結點開始遍歷他們的直接子結點，以此類推下去，直到找到終點。所以，此處肯定是需要使用到迭代了。在此我想寫出我的思路來與樓主交流下。
1.確定startway點和endway點以後，找到startway點，並對該點下的子結點進行遍歷。如你此處選擇的startway是牧野草原04 即位置在ab(04)，endway是牧野草原15，那麼ab(04)下的直接子結點可認為是牧野草原06、牧野草原08和牧野草原10。我們開始按照廣度優先演算法遍歷到牧野草原15。
2.首先我們遍歷完04的子結點（06，08，10），發現沒有15。
3.接下來我們遍歷結點06的子結點（04，05，03），發現沒有15.
4.然後，我們開始遍歷結點08的子結點（4，15，16），發現15，於是整個遍歷結束。
PS:對於迴路的子結點不應該考慮遍歷，比如06中04的迴路。
『伍』 農夫過河問題的求解
#include<iostream.h>
#include<stdio.h>
#defineMAXNUM 20
typedefstruct //順序隊列類型定義
{
int f, r; //f表示頭，r 表示尾
int q[MAXNUM];//順序隊
}SeqQueue,*PSeqQueue;
PSeqQueuecreateEmptyQueue_seq( ) //創建隊列
{
PSeqQueue paqu = new SeqQueue;
if(paqu == NULL)
cout<<"Out of space!"<<endl;
else
paqu->f=paqu->r=0;
return (paqu);
}
intisEmptyQueue_seq( PSeqQueue paqu ) //判斷paqu 所指是否是空隊列
{
return paqu->f==paqu->r;
}
voidenQueue_seq(PSeqQueue paqu,int x) //在隊列中插入一元素 x
{
if ((paqu->r+1)%MAXNUM==paqu->f)
cout<<"隊列已滿."<<endl;
else
{
paqu->q[paqu->r]=x;
paqu->r=(paqu->r+1)%MAXNUM;
}
}
void deQueue_seq(PSeqQueue paqu) //刪除隊列頭部元素
{
if( paqu->f==paqu->r)
cout<<"隊列為空"<<endl;
else
paqu->f=(paqu->f+1)%MAXNUM;
}
intfrontQueue_seq( PSeqQueue paqu ) //對非空隊列,求隊列頭部元素
{
return (paqu->q[paqu->f]);
}
intfarmer(int location) //判斷農夫位置對0做與運算，還是原來的數字，用來判斷位置
{
return 0 != (location & 0x08);
}
intwolf(int location) //判斷狼位置
{
return 0 != (location & 0x04);
}
intcabbage(int location) //判斷白菜位置
{
return 0 != (location & 0x02);
}
intgoat(int location) //判斷羊的位置
{
return 0 !=(location & 0x01);
}
intsafe(int location) // 若狀態安全則返回 true
{
if ((goat(location) == cabbage(location))&& (goat(location) != farmer(location)) )
return 0;
if ((goat(location) == wolf(location))&& (goat(location) != farmer(location)))
return 0;
return 1; //其他狀態是安全的
}
void farmerProblem( )
{
int movers, i, location, newlocation;
int route[16]; //記錄已考慮的狀態路徑
int print[MAXNUM];
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );//新的隊列判斷路徑
enQueue_seq(moveTo, 0x00); //初始狀態為0
for (i = 0; i < 16; i++)
route[i] = -1; //-1表示沒有記錄過路徑
route[0]=0;
while(!isEmptyQueue_seq(moveTo)&&(route[15] == -1))//隊列不為空，路徑未滿時循環
{
location = frontQueue_seq(moveTo); //從隊頭出隊
deQueue_seq(moveTo);
for (movers = 1; movers <= 8;movers<<= 1)
{
if ((0 != (location & 0x08)) == (0 !=(location & movers)))
{
newlocation = location^(0x08|movers);//或運算
if (safe(newlocation) &&(route[newlocation] == -1))//判斷是否安全，以及路徑是否可用
{
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);
}
}
}
}
/*列印出路徑 */
if(route[15] != -1)
{
cout<<"過河步驟是 : "<<endl;
i=0;
for(location = 15; location >= 0; location= route[location])
{
print[i]=location;
i++;
if (location == 0)
break;
}
int num=i-1;
int temp[20][4];
int j;
for(i=num;i>=0;i--)
{
for(j=3;j>=0;j--)
{
temp[num-i][j]=print[i]%2;
print[i]/=2;
temp[0][j]=0;
temp[num+1][j]=1;
}
}
for(i=1;i<=num;i++)
{
cout<<"\t\t\tNO ."<<i<<"\t";
if(i%2==1)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"農夫帶羊過南岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"農夫帶白菜過南岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"農夫帶狼過南岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"農夫自己過南岸";
}
else if(i%2==0)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"農夫帶羊回北岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"農夫帶白菜回北岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"農夫帶狼回北岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"農夫自己回北岸";
}
cout<<endl;
}
}
else
cout<<"Nosolution."<<endl;
}
int main() /*主函數*/
{
farmerProblem();
return 0;
}