有N個(gè)傳教士和N個(gè)野人來(lái)到河邊渡河，河岸有一條船，每次至多可供k人乘渡。河兩岸以及船上的野人數(shù)目總是不超過(guò)傳教士的數(shù)目(否則不安全，傳教士有可能被野人吃掉)。即求解傳教士和野人從左岸全部擺渡到右岸的過(guò)程中，任何時(shí)刻滿足M(傳教士數(shù))≥C(野人數(shù))和M+C≤k的擺渡方案。以下討論三個(gè)傳教士三個(gè)野人還有一條船最多能載兩個(gè)人的方案。
狀態(tài)空間
我們用一個(gè)三元組(m，c，b)來(lái)表示河岸上的狀態(tài)，其中m、c分別代表某一岸上傳教士與野人的數(shù)目，b=1表示船在這一岸，b=0則表示船不在
約束條件是: 兩岸上M≥C, 船上M+C≤2
（mi，ci）為船上的傳教士和野人數(shù)量
左岸初態(tài)為（3,3,1），終態(tài)為（0,0,0）
為什么不能直接暴力窮舉然后剪枝？
因?yàn)榭赡苓\(yùn)過(guò)去兩個(gè)人，然后又把同樣的兩個(gè)人運(yùn)回來(lái)了(或者使用別的形式但是依舊是空轉(zhuǎn))，所以要杜絕這種可能，當(dāng)然最好的方法就是使用帶有記憶的狀態(tài)，如果之前遇到過(guò)這種狀態(tài)那就拒絕執(zhí)行return。
所以....如何實(shí)現(xiàn)去重的目標(biāo)？？？
答：set<string/int>，我采取的是單個(gè)狀態(tài)采用int，記錄路徑經(jīng)過(guò)的狀態(tài)采用string（中間用空格隔開(kāi)）
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<set>
#include<vector>
using namespace std;
int N;
set<string>ans;
void print(vector<int>way){
int i=0;
string h;
for(i=1;i<way.size();i++){
printf("%03d ",way[i]);
if(way[i]<100){
h+="0";
}
h+=to_string(way[i]);
h+=" ";
}
cout<<"\n-------"<<endl;
ans.insert(h);
}
void dfs(int pre,int ni,int nj,int c,set<int>s,vector<int>way){
// set insert
int now=ni*100+nj*10+c;
s.insert(pre);
if(s.count(now)||(N-ni)<0||(N-nj)<0||ni<0||nj<0||(ni<nj&&ni!=0)||((N-ni)<(N-nj)&&(N-ni)!=0)){
return;
}
if(pre==0){
// 如果上一輪就截止了
print(way);
return;
}
way.push_back(pre);
if(c==1){
// zero people . no one on ship is illegal
// dfs(now,ni,nj,0,s,way);
// one people on
dfs(now,ni-1,nj,0,s,way);
dfs(now,ni,nj-1,0,s,way);
// two people on
dfs(now,ni-2,nj,0,s,way);
dfs(now,ni,nj-2,0,s,way);
dfs(now,ni-1,nj-1,0,s,way);
}
else{
// zero people . no one on ship is illegal
// dfs(now,ni,nj,1,s,way);
// one people on
dfs(now,ni+1,nj,1,s,way);
dfs(now,ni,nj+1,1,s,way);
// two people on
dfs(now,ni+2,nj,1,s,way);
dfs(now,ni,nj+2,1,s,way);
dfs(now,ni+1,nj+1,1,s,way);
}
}
int main(){
int chooseN;
int c=1;
// init num and ship side 1 means left and 0 means right
int ni,nj;
// Ni(傳教士),Nj(野人) on the left side.
int pre=-1;
set<int>s;
//cin>>chooseN;
chooseN=3;
N=nj=ni=chooseN;
vector<int>way;
dfs(pre,ni,nj,c,s,way);
cout<<"\nfinally , the answer is:\n\n";
for(auto it=ans.begin();it!=ans.end();it++){
cout<<*it<<endl;
}
}
/*
331 310 321 300 311 110 221 020 031 010 111
-------
331 310 321 300 311 110 221 020 031 010 111
-------
331 310 321 300 311 110 221 020 031 010 021
-------
331 310 321 300 311 110 221 020 031 010 021
-------
331 220 321 300 311 110 221 020 031 010 111
-------
331 220 321 300 311 110 221 020 031 010 111
-------
331 220 321 300 311 110 221 020 031 010 021
-------
331 220 321 300 311 110 221 020 031 010 021
-------
finally , the answer is:
331 220 321 300 311 110 221 020 031 010 021
331 220 321 300 311 110 221 020 031 010 111
331 310 321 300 311 110 221 020 031 010 021
331 310 321 300 311 110 221 020 031 010 111
*/
傳說(shuō)中的基于A*算法的解法：
評(píng)估函數(shù)的建立：
M 表示左岸的傳教士的人數(shù)，N 表示左岸野人的數(shù)目，B 取值為0或1 ，1 表示船在左岸，0 表示船在右岸。d 表示節(jié)點(diǎn)的深度。
- 下面我們來(lái)證明h(n)＝M+C-2B是滿足A*條件的：
我們分兩種情況考慮。
（1）先考慮船在左岸的情況。如果不考慮限制條件，也就是說(shuō)，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個(gè)人將船送回來(lái)。這樣，船一個(gè)來(lái)回可以運(yùn)過(guò)河2人，而船仍然在左岸。而最后剩下的三個(gè)人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡[(M+N-3)/2]*2+1次。其中分子上的"－3"表示剩下三個(gè)留待最后一次運(yùn)過(guò)去。除以"2"是因?yàn)橐粋€(gè)來(lái)回可以運(yùn)過(guò)去2人，需要[(M+N-3)/2]個(gè)來(lái)回，而"來(lái)回"數(shù)不能是小數(shù)，需要向上取整，這個(gè)用符號(hào)[ ]表示。而乘以"2"是因?yàn)橐粋€(gè)來(lái)回相當(dāng)于兩次擺渡，所以要乘以2。而最后的"＋1"，則表示將剩下的3個(gè)運(yùn)過(guò)去，需要一次擺渡。
化簡(jiǎn)得：需要 M+N-2次單向擺渡
（2）再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個(gè)人將船運(yùn)到左岸。因此對(duì)于狀態(tài)(M，N，0)來(lái)說(shuō)，其所需要的最少擺渡數(shù)，相當(dāng)于船在左岸時(shí)狀態(tài)(M+1，N，1)或(M，N+1，1)所需要的最少擺渡數(shù)，再加上第一次將船從右岸送到左岸的一次擺渡數(shù)。因此所需要的最少擺渡數(shù)為：(M+N+1)-2+1。其中(M+N+1)的"＋1"表示送船回到左岸的那個(gè)人，而最后邊的"＋1"，表示送船到左岸時(shí)的一次擺渡。
化簡(jiǎn)有：(M+N+1)-2+1=M+N。
綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數(shù)用一個(gè)式子表示為： ，其中B＝1表示船在左岸，B＝0表示船在右岸。該擺渡次數(shù)是在不考慮限制條件下，推出的最少所需要的擺渡次數(shù)。
