过河问题大家都知道,不多说了.解决这个问题的经典方法就是使用有限状态机.根据人，狼，羊，菜，在不同河岸，可以抽象出N种不同的状 态.某些状态之间可以转换. 这些转换就是运算了. 我们的目的就是找到一组这样的运算,可以从初始状 态转换到终止状态.其间的状态必需都是合法的.C++弋码如下：/* 农夫，狼，羊， 菜，过河 */#include #include enumPLACE{NO,//没有过河的YES,//已经过河了};// 状态typedef struct{NO,NO,NO,NO}; // 起始状态const STATUS c_startconst STATUS c_end{PLACEman;//人的状态PLACEwolf;//狼的状态PLACEsheep;//羊有状态PLACEmenu;//菜的状态} STATUS;{YES,YES,YES,YES}; // 终止状态// 结点（保存转换路径）typedef STATUS TURN* }TURN;struct TURN{ status;p;typedefstd：：listLIST_TURN;typedefstd：：listLIST_NODE;// 判断两个状态是否一致bool operator == (const STATUS& sa, const STATUS& sb) {return sa.man == sb.man && sa.wolf == sb.wolf &&sa.sheep}sb.sheep && sa.menusb.menu;// 查找状态是否已经存在bool Find(LIST_TURN& ls, const STATUS& s) {LIST_TURN::iterator it = ls.begin(); for(;it!=ls.end(); it++){if((*it).status==s)return true;}return false;}// 状态转换运算enum OPERATOR{MAN_GO, // 人过河MAN_GO_WITH_WOLF, // 人带狼过河MAN_GO_WITH_SHEEP, // 人带羊过河MAN_GO_WITH_MENU, // 人带菜过河MAN_BACK, // 人回来MAN_BACK_WITH_WOLF, //人带狼回来MAN_BACK_WITH_SHEEP, //人带羊回来MAN_BACK_WITH_MENU,// 人带菜回来OP_FIRST = MAN_GO,OP_LAST = MAN_BACK_WITH_MENU,};desc)// 状态转换bool StatusTurn(const STATUS& src, OPERATOR op, STATUS& {switch(op){case MAN_GO: // 人过河if(src.man == NO) {desc = src;desc.man = YES;return true; }break;case MAN_GO_WITH_WOLF: // 人带狼过河 if(src.man == NO && src.wolf == NO) {desc = src; desc.man = YES; desc.wolf = YES;return true; } break;case MAN_GO_WITH_SHEEP: // 人带羊过河 if(src.man == NO && src.sheep == NO) {desc = src; desc.man = YES; desc.sheep = YES;return true; }break;case MAN_GO_WITH_MENU: // 人带菜过河 if(src.man == NO && src.menu == NO) {desc = src; desc.man = YES; desc.menu = YES;return true; }break;case MAN_BACK: // 人回来 if(src.man == YES) { desc = src;desc.man = NO; return true;}break;case MAN_BACK_WITH_WOLF: // 人带狼回来 if(src.man == YES && src.wolf == YES) { desc = src;desc.man = NO; desc.wolf = NO;return true; }break;case MAN_BACK_WITH_SHEEP: // 人带羊回来 if(src.man == YES && src.sheep == YES) {desc = src;desc.man = NO;desc.sheep = NO;return true;}break;case MAN_BACK_WITH_MENU: // 人带菜回来if(src.man == YES && src.menu == YES) {desc = src;desc.man = NO;desc.menu = NO;return true;}break;}return false;}// 状态检测(检测合法的状态)bool StatusTest(const STATUS& s){// 人不在的时候，狼会吃羊，羊会吃菜if(s.man != NO){s.menu ==if(s.wolf == NO && s.sheep == NO || s.sheep == NO &&NO)return false;}if(s.man != YES){s.menu ==if(s.wolf == YES && s.sheep == YES || s.sheep == YES &&YES)return false;}return true;}int main(){LIST_TURNhistory;//已经搜索过的状态LIST_NODEactive;//需要搜索的状态// 生成起始结点TURN turn;turn.status = c_start;turn.p = 0;history.push_back(turn); active.push_back(&history.back());// 初始化bool bFind = false;TURN* pend = 0;// 状态转换图搜索(广度优先,求转换次数最少的路径) while(!active.empty()){// 待搜索的当前结点TURN* pact = active.front(); active.pop_front();// 如果等于终止状态,则搜索成功if(pact->status == c_end){bFind = true;pend = pact;break;}op=(OPERATOR)(op+1))// 计算当前状态的所有可能的下一个状态for(OPERATOR op = OP_FIRST; op <= OP_LAST; {TURN next;// 下一个状态满足:// (1) 有一个转换运算从当前状态转换到此状态// (2) 此状态是有效的状态// (3) 此状态是一个新状态.已经搜索过的状态不用再搜索 if(StatusTurn(pact->status, op, next.status) && StatusTest(next.status) && !Find(history, next.status)) {// 为搜索图添加下一个结点next.p = pact;history.push_back(next); active.push_back(&history.back());}}// 如果找到if(bFind){// 计算路径active.clear();TURN* p = pend; while(p){active.push_front(p);p = p->p;}// show nodefor(LIST_NODE::iterator itactive.begin(); itactive.end(); it++){if((*it)->status.man ==NO)std::cout<<"[人]";elsestd::cout<<"[..]";if((*it)->status.wolf ==NO)std::cout<<"[狼]";elsestd::cout<<"[..]";if((*it)->status.sheep ==NO)std::cout<<"[羊]";elsestd::cout<<"[..]";if((*it)->status.menu ==NO)std::cout<<"[菜]";elsestd::cout<<"[..]";std::cout << " <=====>";";if((*it)->status.man ==YES)std::cout<<"[人]";elsestd::cout<<"[..]";if((*it)->status.wolf ==YES)std::cout<<"[狼]";elsestd::cout<<"[..]";if((*it)->status.sheep ==YES)std::cout<<"[羊]";elsestd::cout<<"[..]";if((*it)->status.menu ==YES)std::cout<<"[ 菜]";elsestd::cout<<"[..]";std::cout << std::endl;}}else{std::cout<<"NotFound!" << std::endl;}return 0;}。