fenyou.cpp

人工智能中重要的一个问题, 用广度优先搜索的方法解决

/*
*Copyright by 黄丽福  23020081153237@2009/4/15 
*/
#include<vector>
#include<algorithm>
#define MAX_A 10//容器A的最大值
#define MAX_B 7//容器B的最大值
#define MAX_C 3//容器C的最大值
using namespace std;
int indexForList=0;//当前遍历的节点索引值
typedef struct _tagContainer {//记录每个节点的情况
	int A;//容器A的值
	int B;//容器B的值
	int C;//容器C的值
	int from;//记录父节点的位置，用重构解的顺序
	int ABC;//容器的状态值，对应的一个整数值
    _tagContainer(int a,int b,int c){//构造自己
		A=a;
     	B=b;
		C=c;
		SetABC();
    }
	int returnABC(){//对应的一个整数值
		return A*100+B*10+C;
	}
	void SetABC(){//设置ABC的值和父节点的索引
        ABC=returnABC();
	    from=indexForList;
	}

}Container;	
vector<Container> ListSearchNode;//保存所有节点的容器
int JudgeHasSearch(Container &stats){//判断是否重复遍历和是否是解。
	if (stats.A==stats.B&&stats.A==5) {
		return 2;//找到解了。
	}
	for(int i=0;i<ListSearchNode.size();i++){
		if (ListSearchNode[i].ABC==stats.ABC) {
			return 0;//重复
		}
	}
	return 1;//不重复
}
int DealCurrentStatus(Container &stats){//对当前容器状态的六种倒法，产生新的容器状态
	  //A-->B
	  if (stats.A>0) {
		  if (stats.B<MAX_B) {
			 int chang=MAX_B-stats.B;
             chang=chang<=stats.A?chang:stats.A;
			 Container tem(stats.A-chang,stats.B+chang,stats.C);
			 int res=JudgeHasSearch(tem);
			 if (res==2) {
				 return 1;
			 }else if (res==1)  		 
			 ListSearchNode.push_back(tem);
		  }
	  }
	  //A-->C
	  	  if (stats.A>0) {
	  		  if (stats.C<MAX_C) {
				  int chang=MAX_C-stats.C;
				  chang=chang<=stats.A?chang:stats.A;
				  Container tem(stats.A-chang,stats.B,stats.C+chang);		
				  int res=JudgeHasSearch(tem);
				  if (res==2) {
					  return 1;
				  }else if (res==1) 
					   ListSearchNode.push_back(tem);
			  }
		  } 
	  //B-->A
		  if (stats.B>0) {
			  if (stats.A<MAX_A) {
				  int chang=MAX_A-stats.A;
				  chang=chang<=stats.B?chang:stats.B;
				  Container tem(stats.A+chang,stats.B-chang,stats.C);		
				  int res=JudgeHasSearch(tem);
				  if (res==2) {
					  return 1;
				  }else if (res==1) 
					  ListSearchNode.push_back(tem);
			  }
		  }
	  //B-->C
		  if (stats.B>0) {
			  if (stats.C<MAX_C) {
				  int chang=MAX_C-stats.C;
				  chang=chang<=stats.C?chang:stats.C;
				  Container tem(stats.A,stats.B-chang,stats.C+chang);		
				  int res=JudgeHasSearch(tem);
				  if (res==2) {
					  return 1;
				  }else if (res==1) 
					  ListSearchNode.push_back(tem);
			  }
		  }
	  //C-->A
		  if (stats.C>0) {
			  if (stats.A<MAX_A) {
				  int chang=MAX_A-stats.A;
				  chang=chang<=stats.C?chang:stats.C;
				  Container tem(stats.A+chang,stats.B,stats.C-chang);		
				  int res=JudgeHasSearch(tem);
				  if (res==2) {
					  return 1;
				  }else if (res==1) 
					  ListSearchNode.push_back(tem);
			  }
		  }
	  //C-->B
		  if (stats.C>0) {
			  if (stats.B<MAX_B) {
				  int chang=MAX_B-stats.B;
				  chang=chang<=stats.C?chang:stats.C;
				  Container tem(stats.A,stats.B+chang,stats.C-chang);		
				  int res=JudgeHasSearch(tem);
				  if (res==2) {
					  return 1;
				  }else if (res==1) 
					  ListSearchNode.push_back(tem);
			  }
		  }
	  return 0;
}
void structResult(int from){//构造解的结果。
	  if (from>0) {
          int from2=ListSearchNode[from].from;
		  structResult(from2);
	  }
      printf("<%2d %2d %2d>\n",ListSearchNode[from].A,ListSearchNode[from].B,ListSearchNode[from].C);
}
void FenYouProcess(){//采用广度优先的算法，遍历直到找到一个解，程序结束
	while (indexForList!=ListSearchNode.size()) {
        Container CurStats=ListSearchNode[indexForList];
		int res=DealCurrentStatus(CurStats);
		if (res==1) {
			printf("分油问题求解：\n初始A：10;B：0;C:0\n分油的过程如下所示：\n");
			structResult(indexForList);
			printf("<%2d %2d %2d>\n",5,5,0);
	    	return ;
		}
        indexForList++;
	}

}
int main(){//主程序，初始化参数，并调用主程序进行实验
	Container Head(10,0,0);
	indexForList=0;
    ListSearchNode.push_back(Head);
	FenYouProcess();
	return 0;
}