傳教士與野人問題:三個傳教士,三個野人,一條船,船最多搭載兩個人,傳教士和野人都能劃船,如何用求解這個問題?
根據<人工智能>的搜尋算法,定義目标函數,初始狀态,計算出狀态空間,然後進行搜尋,由于路徑耗散是常量,省略了路徑耗散函數
這個問題的推廣:nn野人問題,在n>3時是無解的
#ifndef te_acrossRiver_MOC_H20132417
#define te_acrossRiver_MOC_H20132417
#include "te_common.h"
class AcrossRiver:public Singaleton<AcrossRiver>
{
class StateNode
{
public:
int goodManLeft;
int badManLeft;
int goodManRight;
int badManRight;
bool boatAtLeft;
StateNode* clone()
{
StateNode* p1=new StateNode();
p1->goodManLeft=goodManLeft;
p1->goodManRight=goodManRight;
p1->badManLeft=badManLeft;
p1->badManRight=badManRight;
return p1;
}
bool isSameState(StateNode* p1)
{
return p1->goodManRight==goodManRight&&p1->goodManLeft==goodManLeft&&p1->badManLeft==badManLeft&&p1->badManRight==badManRight
&&p1->boatAtLeft==boatAtLeft;
}
//後繼狀态
vector<StateNode*> linkNodes;
};
bool targetTest(StateNode* p)
{
return p->goodManLeft==0&&p->badManLeft==0;
}
//node是否合法
bool nodeTest(StateNode* p,vector<StateNode*>* states)
{
auto it1=find_if(states->begin(),states->end(),[&](StateNode* p1){
return p->isSameState(p1);
});
bool b1=it1==states->end();
bool bleft=(p->goodManLeft==0)||(p->goodManLeft>=p->badManLeft);
bool bright=(p->goodManRight==0)||(p->goodManRight>=p->badManRight);
bool b3=p->goodManLeft>=0&&p->goodManRight>=0&&p->badManLeft>=0&&p->badManRight>=0;
return b1&&bleft&&bright&&b3;
}
void genStatesColection(StateNode* initial,vector<StateNode*>* states)
{
if(targetTest(initial))
{
return;
}else
{
auto perNodeFunc=[&](StateNode* v){
if(nodeTest(v,states))
{
CCLOG("add state %d %d %d %d",v->goodManLeft,v->badManLeft,v->goodManRight,v->badManRight);
initial->linkNodes.push_back(v);
}else
{
delete v;
}
};
if(initial->boatAtLeft)
{
//右移一個goodman
{
StateNode* n1=initial->clone();
n1->boatAtLeft=false;
n1->goodManLeft--;
n1->goodManRight++;
perNodeFunc(n1);
}
//右移一個badman
{
StateNode* n1=initial->clone();
n1->boatAtLeft=false;
n1->badManLeft--;
n1->badManRight++;
perNodeFunc(n1);
}
//右移兩個good
{
StateNode* n1=initial->clone();
n1->boatAtLeft=false;
n1->goodManLeft-=2;
n1->goodManRight+=2;
perNodeFunc(n1);
}
//右移兩個bad
{
StateNode* n1=initial->clone();
n1->boatAtLeft=false;
n1->badManLeft-=2;
n1->badManRight+=2;
perNodeFunc(n1);
}
//混合右移
{
StateNode* n1=initial->clone();
n1->boatAtLeft=false;
n1->goodManLeft--;
n1->goodManRight++;
n1->badManLeft--;
n1->badManRight++;
perNodeFunc(n1);
}
}else
{
//左移一個goodman
{
StateNode* n1=initial->clone();
n1->boatAtLeft=true;
n1->goodManLeft++;
n1->goodManRight--;
perNodeFunc(n1);
}
//左移一個badman
{
StateNode* n1=initial->clone();
n1->boatAtLeft=true;
n1->badManLeft++;
n1->badManRight--;
perNodeFunc(n1);
}
//左移兩個good
{
StateNode* n1=initial->clone();
n1->boatAtLeft=true;
n1->goodManLeft+=2;
n1->goodManRight-=2;
perNodeFunc(n1);
}
//左移兩個bad
{
StateNode* n1=initial->clone();
n1->boatAtLeft=true;
n1->badManLeft+=2;
n1->badManRight-=2;
perNodeFunc(n1);
}
//混合左移
{
StateNode* n1=initial->clone();
n1->boatAtLeft=true;
n1->goodManLeft++;
n1->goodManRight--;
n1->badManLeft++;
n1->badManRight--;
perNodeFunc(n1);
}
}
states->push_back(initial);
for_each(initial->linkNodes.begin(),initial->linkNodes.end(),[&](StateNode* n1){
genStatesColection(n1,states);
});
}
}
bool containState(vector<StateNode*>* nodes,StateNode* node)
{
auto it1=find_if(nodes->begin(),nodes->end(),[&](StateNode* p1){
return p1->isSameState(node);
});
return it1!=nodes->end();
}
bool DFSSearch(vector<StateNode*>* path)
{
StateNode* curNode=path->back();
for (int i=0;i<curNode->linkNodes.size();i++)
{
StateNode* subNode=curNode->linkNodes[i];
path->push_back(subNode);
if(targetTest(subNode))
{
return true;
}else
{
bool b1=DFSSearch(path);
if(b1)
return true;
}
path->pop_back();
}
return false;
}
public:
void run(int m,int n)
{
StateNode* node1=new StateNode();
node1->goodManLeft=m;
node1->badManLeft=n;
node1->badManRight=0;
node1->goodManRight=0;
node1->boatAtLeft=true;
vector<StateNode*>* nodes=new vector<StateNode*>();
genStatesColection(node1,nodes);
vector<StateNode*> path;
path.push_back(node1);
bool b=DFSSearch(&path);
for_each(path.begin(),path.end(),[&](StateNode* p1){
CCLOG("%d %d %d %d %d",p1->goodManLeft,p1->badManLeft,p1->goodManRight,p1->badManRight,p1->boatAtLeft);
});
CCLOG("state space %d",nodes->size());
}
protected:
};
#endif