过河问题的算法--有限状态机[1]

过河问题大家都知道,不多说了.
解决这个问题的经典方法就是使用有限状态机. 根据人,狼,羊,菜,在不同河岸,可以抽象出n种不同的状态.某些状态之间可以转换. 这些转换就是运算了. 我们的目的就是找到一组这样的运算,可以从初始状态转换到终止状态. 其间的状态必需都是合法的. c++代码如下:

/*-------------------------------------
  农夫，狼，羊， 菜，过河
  --------------------------------------*/
#include <list>
#include <iostream>

enum place
{
 no,    // 没有过河的
 yes,   // 已经过河了
};

// 状态
typedef struct
{
 place man;    // 人的状态
 place wolf;   // 狼的状态
 place sheep;  // 羊有状态
 place menu;   // 菜的状态
} status;

const status  c_start = {no,no,no,no};    // 起始状态
const status  c_end = {yes,yes,yes,yes};  // 终止状态

// 结点(保存转换路径)
typedef struct turn{
 status   status;
 turn*    p;
}turn;

typedef std::list<turn>  list_turn;
typedef std::list<turn*> list_node;

// 判断两个状态是否一致
bool operator == (const status& sa, const status& sb)
{
 return sa.man == sb.man && sa.wolf == sb.wolf &&
  sa.sheep == sb.sheep && sa.menu == sb.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,
};

// 状态转换
bool statusturn(const status& src, operator op, status& desc)
{
 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){
  if(s.wolf == no && s.sheep == no || s.sheep == no && s.menu == no)
   return false;

 }
 if(s.man != yes){
  if(s.wolf == yes && s.sheep == yes || s.sheep == yes && s.menu == yes)
   return false;
 }

 return true;
}