代码.cpp

本程序解决了n个野人与m个传教士过河的问题

#include<iostream.h>
#include<stdlib.h>

struct state{
	int nc;//传教士的数量
	int nw;//野人的数量
	int bf;//1去左岸，0去右岸,只表示船的位置
	int cost;//代价函数的值
	int used; //是否作为节点扩展过
	int father; //指示该状态的父状态
	//int deep; //当前节点所处的深度
};

state queue[1000];
int flag[100][100][2];
int M,N,K;

int safe(state state3) //判断是否合法。
{
	if(state3.nc>=0&&state3.nc<=M&&state3.nw>=0&&state3.nw<=N)
	{
		if(state3.nc>=state3.nw||state3.nc==0)
		return 1;
	}
	return 0;
}

state revstate(state state4) //对岸的状态。
{
	state state;
	state.nc=M-state4.nc;
	state.nw=N-state4.nw;
	state.bf=state4.bf;
	return state;
}

void output(state state5)  
{
	state out[1000];
	int i=0;
	int index;
	//cout<<state.nc<<" "<<state.nw<<" "<<endl;
	out[i].nc=state5.nc;
	out[i].nw=state5.nw;
	out[i].bf=state5.bf;
	i++;
	index=state5.father;
	while(1)
	{
		if(index==-1)
			break;
		//cout<<queue[index].nc<<" "<<queue[index].nw<<" "<<endl;
		out[i].nc=queue[index].nc;
	    out[i].nw=queue[index].nw;
	    out[i].bf=queue[index].bf;
		index=queue[index].father;
		i++;
	}
    int j;
	cout<<"状态路径如下："<<endl;
	for(j=i-1;j>=0;j--)
		cout<<out[j].nc<<" "<<out[j].nw<<" "<<out[j].bf<<" "<<endl;
}
		


state newstate(int g,int h,state state4)
{
	state state2;
	state2.bf=1-state4.bf;
	if(state4.bf==1)
	{
		state2.nc=state4.nc-g;
		state2.nw=state4.nw-h;
		state2.cost=state2.nc+state2.nw-2*state2.bf;
	}
	else
	{
		state2.nc=state4.nc+g;
		state2.nw=state4.nw+h;
		state2.cost=state2.nc+state2.nw-2*state2.bf;
	}
	return state2;
}



void bfs()
{
	int i,g,h;

	while(1)
	{
		//选取评价值最小的节点进行扩展。
      int temp=32767;
	  int re=-10;
	  i=0;
	  while(1)
	  {
		  if(queue[i].cost==-1)
			  break;
		  if(queue[i].cost<temp&&queue[i].used==0)
		  {
			  temp=queue[i].cost;
			  re=i;
			 
		  }
		  i++;
	  } //cout<<re<<endl;
	  if(re==-10)
	  {
		  cout<<"无解"<<endl;
		  break;
	  }
	  int len=i;
      queue[re].used=1;    //将次节点置为死节点。
	  //判断是否到达目标状态
	  if(queue[re].nc==0&&queue[re].nw==0)
	  {
		  cout<<"该问题有解"<<endl;
		
		  output(queue[re]);
		  break;
	  }
    //进行扩展
	  for(g=0;g<=K;g++)
		  for(h=0;h+g<=K;h++)  //h-运送的传教士，g-运送的野人
		  {
			  if(g==0&&h==0)
				  continue;
			  if(h>=g||h==0)
			  {
			  state state1;
			  state1.nc=newstate(h,g,queue[re]).nc;
			  state1.nw=newstate(h,g,queue[re]).nw;
			  state1.bf=newstate(h,g,queue[re]).bf;
			  state1.cost=newstate(h,g,queue[re]).cost;
			  state1.father=re;
			  //如果扩展出的状态合法，则将该状态加入活节点表。
			  if(safe(state1)&&safe(revstate(state1))&&flag[state1.nc][state1.nw][state1.bf]==0)
			  {
				  //cout<<len<<endl;
				  queue[len].nc=state1.nc;
				  queue[len].nw=state1.nw;
				  queue[len].bf=state1.bf;
				  queue[len].cost=state1.cost;
				  queue[len].father=state1.father;
				  len++;
				  //cout<<state1.nc<<" "<<state1.nw<<" "<<state1.bf<<" "<<state1.cost<<endl;
			  }
			  flag[state1.nc][state1.nw][state1.bf]=1;
			 
			  }
		  }
		  }


}




int main()
{
	
	cin>>M>>N>>K;
	int i,j,v;
	for(i=0;i<=M;i++)
		for(j=0;j<=N;j++)
			for(v=0;v<=1;v++)
				flag[i][j][v]=0;
	flag[M][N][1]=1;

	for(i=0;i<1000;i++)
	{
		queue[i].cost=-1;
		queue[i].used=0;
		//queue[i].deep=0;
		queue[i].father=-1;
	}
	queue[0].nc=M;
	queue[0].nw=N;
	queue[0].bf=1;
	queue[0].cost=M+N-2;
	bfs();
	return 0;
}