用BFS（广度优先搜索queue&&list）算法解决农夫过河问题

本文主要是介绍用BFS（广度优先搜索queue&&list）算法解决农夫过河问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、问题需求分析

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？
二、算法选择

求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。

用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。

广度优先：

广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。**要实现广度优先搜索，一般都采用队列作为辅助结构。**把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。
三、算法的精化

要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。

代码如下：

#include <queue>
#include <list>
#include <iostream>
using namespace std;

//判断状态是否安全
bool isSecure(int s)
{
	bool bFarmer,bWolf,bSheep,bCabbage;
	
	//得出农夫和各物品的位置
	bFarmer = (s&8)==0 ? false : true;
	bWolf = (s&4)==0 ? false : true;
	bSheep = (s&2)==0 ? false : true;
	bCabbage = (s&1)==0 ? false : true;
	
	//狼吃羊
	if ( bWolf==bSheep && bSheep!=bFarmer )
	{
		return false;
	}
	
	//羊吃白菜
	if ( bCabbage==bSheep && bSheep!=bFarmer )
	{
		return false;
	}
	
	//其它状态都是安全的
	return true;
}

//判断num是否在path表里已经存在
bool isHave(list<int> path, int num)
{
	list<int>::iterator it = find(path.begin(), path.end(), num);
	
	if ( it == path.end() )
	{
		return false;
	}
	
	return true;
}

//主函数入口
int main(void)
{
	int n;
	int temp;
	int cur_pos;
	bool bFarmer;
	bool bOther;
	
	int State=0;  //初始状态, 从低位开始，依次为白菜、羊、狼、农夫的位置状态
	
	int flag[4]={1,2,4,8};
	
	queue<int> q;
	list<int> path;
	
	q.push(State);
	path.push_back(State);
	
	while ( 15 != path.back() && !q.empty())
	{
		cur_pos = q.front();
		q.pop();
		
		//判断当前状态是否安全
		if( isSecure(cur_pos) )
		{
			//---找出下一步的所有可能状态，并放入队列
			//1、只有农夫移动的情况
			temp = cur_pos;
			temp ^= 8;
			//新状态是否没有在之前出现过
			if ( !isHave(path, temp) )
			{
				q.push(temp);
			}
			
			//2、农夫与余下三个物品其中之一移动的情况
			for ( n=0; n<3; n++ )
			{
				temp = cur_pos;
				
				bFarmer = (temp&8)==0 ? false : true;
				bOther = (temp&flag[n])==0 ? false : true;
				
				//若与农夫在同一边，则可以移动
				if ( bFarmer==bOther )
				{
					temp ^= flag[n];
					temp ^= 8;
					//新状态是否没有在之前出现过
					if ( !isHave(path, temp) )
					{
						q.push(temp);
					}
				}
			}
			//---
			
			//判断当前状态是否已经在之前没有出现过
			if ( !isHave(path, cur_pos) )
			{
				//农夫是否移动了
				if ( (path.back()&8) != (cur_pos&8) )
				{
					path.push_back( cur_pos );
				}
			}
		}
	}
	
	//输出结果
	if ( path.back() != 15 )
	{
		cout<<"没有找到解！"<<endl;
	}
	else
	{
		char buf[5];
		char temp[5];
		int len;
		
		cout<<"------------------"<<endl;
		cout<<"农夫、狼、羊、白菜"<<endl;
		cout<<"------------------"<<endl;
		
		//输出找到的解
		for ( list<int>::iterator it=path.begin(); it != path.end(); it++ )
		{
			//填充前导零
			itoa(*it,buf,2);
			len = strlen(buf);
			if ( len!=4 )
			{
				memcpy(temp,buf,len);
				memset(buf,'0',4-len);
				memcpy(buf+4-len,temp,len);
				memset(buf+4,0,1);
			}
			
			cout<<buf<<endl;
		}
	}
	
	return 0;
}

------------------
农夫、狼、羊、白菜
------------------
0000
1010
0010
1011
0001
1101
0101
1111

这篇关于用BFS（广度优先搜索queue&&list）算法解决农夫过河问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！