mcb.cpp

这是我的AI课程实验报告

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
int i=0;
typedef struct _State
{
	int Ml;  // Ml表示传教士在河左岸的人数
	int Cl;  // 表示野人在河左岸的认输
	int Bl;  // b=1，表示船在左岸，b=0，表示船在右岸
}State;

typedef struct _Rule
{
	int m;
	int c;
}Rule;

Rule rule[5] = {{1,1}, {1,0}, {0,1}, {2,0}, {0,2}};  // 规则集

void OutResult(const vector<int>& ruleSet, const vector< State >& StateSet, const int index)
{  
	cout << "  初始状态 \t" <<" \t"<< "(" << 3 << "," << 3 << ")\t" <<"\t"<< "(" << 0 << "," << 0 << ")\t"<<"\t"<<"left" << endl;

	for(int i = 0; i <= index; i ++)
	{
		cout << i +1 << " ";
		if( i % 2 == 0 )
			cout << "L-to-R" << "(" << rule[ ruleSet[i] ].m << "," << rule[ ruleSet[i] ].c << ")";   //从左到右的规则
		else 
			cout << "R-to-L" << "(" << rule[ ruleSet[i] ].m << "," << rule[ ruleSet[i] ].c << ")";   //从右到左的规则

		cout<< "         \t"<<"(" << StateSet[i].Ml<< "," << StateSet[i].Cl<< ")"<< "         \t"<<"(" << 3-StateSet[i].Ml << "," << 3-StateSet[i].Cl << ")";
		if( StateSet[i].Bl == 1 )
			cout  << "         \t" << "left " << endl;
		else 
			cout  << "         \t" << "right " << endl;


	}
}

bool IsExist(const vector< State >& StateSet, const State& state, const int index)
{
	if( state.Ml == 3 && state.Cl == 3 && state.Bl == 1) return true;
	for(int i = 0; i <= index; i ++)
		if(StateSet[i].Ml == state.Ml && StateSet[i].Cl == state.Cl && StateSet[i].Bl == state.Bl)
			return true;
	return false;

}

bool SearchRule(vector<int>& ruleSet, vector< State >& StateSet, int index,State NowState)
{
	if(NowState.Bl == 0 && NowState.Cl == 0 && NowState.Ml == 0) // 达到最终状态
	{
	    if(i++==0)
	   	OutResult(ruleSet, StateSet, index);
		return true;
	    
	}
 //   if(index==9)
//	{
	//	OutResult(ruleSet, StateSet, index);
//	}

	int iSize = ruleSet.size();       //否则
	if( iSize <= index )
	{
		cout << "full" << endl;
		return false;
	}

	State state;
	for(int i = 0; i < 5; i ++)     //搜索规则集
	{
		state = NowState;
		if( NowState.Bl == 1 ) // 船在左岸
		{
			state.Ml -= rule[i].m;
			state.Cl -= rule[i].c;
			if( state.Ml < 0 || state.Cl < 0 ) continue;

			// state为安全状态
			if( state.Ml == state.Cl ||  state.Ml== 3 || state.Ml == 0 )
			{
				state.Bl = 0;
				if( IsExist(StateSet, state, index) ) continue;
				ruleSet[ index + 1 ] = i;
				StateSet[ index + 1 ] = state;
				SearchRule(ruleSet, StateSet, index+1, state);
			}
				
		}
		else  // 在右岸
		{
			state.Ml += rule[i].m;
			state.Cl += rule[i].c;	
			if( state.Ml > 3 || state.Cl > 3 ) continue;		
			if( state.Ml == state.Cl ||  state.Ml == 3 || state.Ml == 0 )
			{
				state.Bl = 1;
				if( IsExist(StateSet, state, index) ) continue;
				ruleSet[ index + 1 ] = i;
				StateSet[ index + 1 ] = state;
				SearchRule(ruleSet, StateSet, index+1, state);
			}	
		}
	}

	

	return false;
}


int main()
{
	State InitState = {3, 3, 1};  // 初始状态	
	vector< int > ruleSet;          // 存放摆渡规则
	vector< State > StateSet;    // 存放状态
	ruleSet.resize( 10000 );     //设置中间经过规则数目
	StateSet.resize( 10000 );    //设置中间经过状态数目
	cout << "********传教士与野人问题求解：(3,3,1)- > (0,0,0)**********" << endl;
	cout << "摆渡规则\t" << "      \t" << "左岸状态\t"  << "右岸状态\t"  << "船的状态" << endl;
	
	SearchRule(ruleSet, StateSet, -1, InitState);
	cout<<endl;
    cout<<"**********解释说明如下*************"<<endl;

	cout << "************L-to-R(2,0)  (1,1)   (2,2)   right**************" << endl;
	cout << "表示从左岸向右岸运2个传教士和0个野人，然后左岸传教士和野人为(1,1), 右岸为(2,2), 船到右岸" << endl;

	getchar();
	return 1;

}