2020-06-03

过河问题通用解法及简单证明

过河问题定义

问题定义

过河问题是一个经典的算法问题。假设有 $M$ 只牛和 $N$ 只虎要过河，河中只有一条船，船至多能乘坐 $K$ 只动物。在河的任意一边或船上，虎的数量不能多于牛的数量，否则牛会被吃掉。问：是否存在合理的渡河方案，使得所有动物能够安全过河？若存在，输出最少过河次数的渡河方案。
牛虎过河问题衍生出很多同类问题，如农夫与强盗过河、传教士与野人过河等等，换汤不换药，问题的解法完全相同。

解题思路

此类问题先定义好状态空间，列举所有可行的状态（包括起始状态和终止状态），根据状态间是否可以相互转换（状态 $\mathcal A$ 是否可以通过一次有效的运输转换到状态 $\mathcal B$ ）画出状态间的无向图，再通过图搜索（宽度优先或深度优先）找出从起始状态到终止状态的可行路径，首次到达终止状态的路径即为过河次数最少的渡河方案。

过河问题通解

图论

有关图论的详细介绍不属于本篇文章的范畴，有兴趣的读者自行查阅资料，这里只介绍图的宽度优先搜索。伪代码如下：

Input: 起始节点A，终止节点B
Output: 起始节点到终止节点的最短路径P
function P=BFS(A, B):
	define an empty queue Q;
	push A to Q;
	set A visited;
	set endReached false;
	while Q not empty:
		pop Q to curNode;
		for child of curNode:
			if child not visited:
				set child visited;
				set child backtracking to curNode;
				if child == B:
					set endReached true;
					break;
				end if
				push curNode to Q;
			end if
		end for
		if endReached:
			break;
		end if
	end while
	set curNode to B;
	do
		add curNode to P;
		set curNode to its backtracking;
	while(curNode is not null);
	reverse P;
	return P;

伪代码的思路还是很简单的，每个节点需要设置是否已搜索过的标志位；为方便回溯，还需记录当前节点经由哪个节点搜索而来。用队列记录待搜索的节点，遍历每个节点的子节点，直到遇见了终止节点，从终止节点开始回溯到起始节点即可找到最短路径。上代码，以下为图的通用宽度优先搜索。

template<class T>
class GraphNode
{
public:
	GraphNode() : node(nullptr), visited(false), backtracking(nullptr) {}
	GraphNode(T* n) : node(n), visited(false), backtracking(nullptr) {}
	T* node;
	std::vector<GraphNode<T>*> children;
	bool visited;
	GraphNode<T>* backtracking;
};

template<class T>
void bfs(GraphNode<T>* startNode, GraphNode<T>* endNode, std::vector<T*>& path)
{
	if (startNode == nullptr || endNode == nullptr)
		return;
	if (startNode == endNode || startNode->node == endNode->node)
	{
		path.push_back(startNode->node);
		return;
	}
	std::queue<GraphNode<T>*> que;
	startNode->visited = true;
	que.push(startNode);
	bool endReached = false;
	while (!que.empty())
	{
		GraphNode<T>* curNode = que.front();
		que.pop();
		for (int i = 0; i < curNode->children.size(); ++i)
		{
			GraphNode<T>* child = curNode->children[i];
			if (child->visited == false)
			{
				child->visited = true;
				child->backtracking = curNode;
				if (child == endNode)
				{
					endReached = true;
					break;
				}
				que.push(child);
			}
		}
		if (endReached)
			break;
	}
	if (endReached)
	{
		GraphNode<T>* curNode = endNode;
		do
		{
			path.push_back(curNode->node);
			curNode = curNode->backtracking;
		}while (curNode != nullptr);
	}
	std::reverse(path.begin(), path.end());
}

过河问题

状态空间

一般而言，过河问题的状态空间可以用5元组来表示，即左岸（假设动物从左岸到右岸）牛的数量、左岸虎的数量、船在左岸还是右岸、右岸牛的数量、右岸虎的数量。其中左岸牛（虎）的数量与右岸牛（虎）的数量之和为 $M(N)$ ，因此状态空间可退化为3元组： $\{m,n,b\}$ ，分别表示左岸牛的数量 $m\in\{0,\dots,M\}$ 、左岸虎的数量 $n\in\{0,\dots,N\}$ 、船在左岸还是右岸 $b\in\{0,1\}$ 。
以3只牛3只虎、一条船最大载2只动物为例，状态空间如下表：

(3,3,0)	(3,2,0)	(3,1,0)	(3,0,0)
(3,3,1)	(3,2,1)	(3,1,1)	(3,0,1)
(2,3,0)	(2,2,0)	(2,1,0)	(2,0,0)
(2,3,1)	(2,2,1)	(2,1,1)	(2,0,1)
(1,3,0)	(1,2,0)	(1,1,0)	(1,0,0)
(1,3,1)	(1,2,1)	(1,1,1)	(1,0,1)
(0,3,0)	(0,2,0)	(0,1,0)	(0,0,0)
(0,3,1)	(0,2,1)	(0,1,1)	(0,0,1)

代码（表示状态的类如下）：

/*
* 以左岸牛虎数量及船是否在左岸为状态，共(M+1)*(N+1)*2种状态
*/
class State
{
public:
	int cattle;
	int tiger;
	int boat;
	State() : cattle(0), tiger(0), boat(0) {}
	State(int m, int n, int b) : cattle(m), tiger(n), boat(b) {}
	bool operator == (const State& right) const
	{
		return (cattle==right.cattle)&&(tiger==right.tiger)&&(boat==right.boat);
	}
};

可行性判断

根据题目要求，满足以下条件的状态为不可行状态：

$m<n \quad\text{and}\quad m\neq0$ ，即左岸牛的数量小于虎的数量
$M-m<N-n\quad\text{and}\quad M-m\neq0$ ，即右岸牛的数量小于虎的数量
$m=M, n=N, b=1$ ，即动物都在左岸而船在右岸
$m=0, n=0, b=0$ ，即动物都在右岸而船在左岸

所有可行状态如下表：

(3,3,0)	(3,2,0)	(3,1,0)	(3,0,0)
x	(3,2,1)	(3,1,1)	(3,0,1)
x	(2,2,0)	x	x
x	(2,2,1)	x	x
x	x	(1,1,0)	x
x	x	(1,1,1)	x
(0,3,0)	(0,2,0)	(0,1,0)	x
(0,3,1)	(0,2,1)	(0,1,1)	(0,0,1)

代码如下：

bool isStateFeasible(const State& state, int M, int N)
{
	if (state.cattle < state.tiger && state.cattle > 0)
		return false;
	if (M-state.cattle < N-state.tiger && M-state.cattle > 0)
		return false;

	// 左岸无动物而船在左岸，不可行
	if (state.cattle==0 && state.tiger==0 && state.boat==0)
		return false;
	// 右岸无动物而船在右岸，不可行
	if (state.cattle==M && state.tiger==N && state.boat==1)
		return false;

	return true;
}

状态转移

记状态 $\mathcal A=(m_1,n_1,b_1)$ ，状态 $\mathcal B=(m_2,n_2,b_2)$ 。若 $b_1=1$ ，船从右岸带动物到左岸，左岸动物数量增加，增加量 $\Delta m=m_2-m_1,\Delta n=n_2-n_1$ ；若 $b_1=0$ ，船从左岸带动物到右岸，左岸动物数量减少，减少量 $\Delta m=m_1-m_2,\Delta n=n_1-n_2$ 。通过一次渡河使得状态 $\mathcal A,\mathcal B$ 相互转换需同时满足下列条件（以 $\mathcal A$ 到 $\mathcal B$ 的转换为例，反之亦然）：

$\mathcal A\neq\mathcal B$ ，即两个状态不相等
$b_1\neq b_2$ ，即一次渡河前后船毕竟不在同一个岸边
$m_1\neq m_2,n_1\neq n_2$ ，即必须有动物来划船，左岸动物数量必有所变化
$\Delta m\geq0,\Delta n\geq0,\Delta m+\Delta n\leq K,\ \text{and}\ (\Delta m > 0\ \text{and}\ \Delta m\geq\Delta n\ \text{or}\ \Delta m==0)$ ，即动物增加（减少）量不能为0，且增加（减少）量不能大于船的载重，且增加（减少）的动物（即通过船转移的动物）需满足不被吃掉的条件

代码如下：

bool isTowStatesTransferable(const State& s1, const State& s2, int k = 2)
{
	// 相同两个状态认为不可达
	if (s1==s2)
		return false;
	// 相邻两个状态，船必定在不同岸
	if (s1.boat == s2.boat)
		return false;

	if (s1.tiger==s2.tiger && s1.cattle==s2.cattle)
		return false;

	// s1->s2, 船从右岸带动物到左岸，左岸动物数量增多
	if (s1.boat == 1)
	{
		int dc = s2.cattle - s1.cattle, dt = s2.tiger - s1.tiger;
		if (dc >= 0 && dt >= 0					// 动物数量增加
			&& (dc+dt <= k)						// 增加的数量不能大于船的容量
			&& ((dc>0 && dc>=dt) || dc==0))		// 船上牛的数量不能小于虎的数量
			return true;
		else
			return false;
	}
	// s1->s2, 船从左岸带动物到右岸，左岸动物数量减少
	else
	{
		int dc = s1.cattle - s2.cattle, dt = s1.tiger - s2.tiger;
		if (dc >= 0 && dt >= 0					// 动物数量减少
			&& (dc+dt <= k)						// 减少的数量不能大于船的容量
			&& ((dc>0 && dc>=dt) || dc==0))		// 船上牛的数量不能小于虎的数量
			return true;
		else
			return false;
	}
}

图

仍然以3只牛3只虎、一条船最大载2只动物为例，状态转移图如下所示，从图上看，问题经过转化之后简单了很多，从图上可以一目了然的看出来渡河方案，且最少渡河次数为11次。

构建图的代码再主函数中，如下所示：

int main()
{
	int M, N, K;
	while (std::cin >> M >> N >> K)
	{
		std::vector<State> all_states;
		for (int m = 0; m <= M; ++m)
		{
			for (int n = 0; n <= N; ++n)
			{
				State s1(m,n,0);
				if (isStateFeasible(s1, M, N))
					all_states.push_back(s1);
				State s2(m,n,1);
				if (isStateFeasible(s2, M, N))
					all_states.push_back(s2);
			}
		}

		std::vector<GraphNode<State>*> state_nodes(all_states.size(), nullptr);
		for (int i = 0; i < all_states.size(); ++i)
			state_nodes[i] = new GraphNode<State>(&all_states[i]);
		for (int i = 0; i < all_states.size(); ++i)
		{
			for (int j = 0; j < all_states.size(); ++j)
			{
				if (j == i) continue;
				if (isTowStatesTransferable(all_states[i], all_states[j], K))
				{
					state_nodes[i]->children.push_back(state_nodes[j]);
				}
			}
		}

		std::vector<State*> path;
		bfs(state_nodes.back(), state_nodes[0], path);

		for (int i = 0; i < path.size(); ++i)
			std::cout << path[i]->cattle << ", " << path[i]->tiger << ", " << path[i]->boat << std::endl;
		if (path.size() > 0)
			std::cout << "最少过河次数： " << path.size()-1 << std::endl;
	}

	return 0;
}

结论

运行上述代码，笔者发现：

当牛的数量大于虎的数量时，只要船载重≥2，一定能够顺利过河。
当牛的数量等于虎的数量且船载重为2时，牛或虎的数量≥4时，无法顺利过河。
当牛的数量等于虎的数量且船载重为3时，牛或虎的数量≥6，无法顺利过河。
当牛的数量等于虎的数量且船载重大于3时，无论牛虎数量如何，都能顺利过河。

其中结论2、结论3和结论4是否为一般性结论，尚需进一步证明。目前笔者仅能给出结论1的数学证明。

证明

我们以数学归纳法证明结论1，只需证明船载重为2时能够顺利过河即可，若船载重大于2，必然也能顺利过河（大不了按载重量2使用船）。
已知 $M-N\geq1, K=2$ ，记第 $k$ 次“渡河”后左岸牛虎的数量分别为 $m_k^L, n_k^L$ ，右岸牛虎的数量分别为 $m_k^R, n_k^R$ 。这里渡河的准确定义见下文。
Step 0. 初始状态 $m_0^L=M, n_0^L=N, m_0^R=0, n_0^R=0$ ，船在左岸。
Step 1. 第一次渡河，一牛一虎乘船到右岸， $m_1^L=M-1, n_1^L=N-1, m_1^R=1, n_1^R=1$ ，船在右岸。
Step 2. 假设第 $k$ 次渡河后， $m_k^L-n_k^L\geq1, m_k^R= n_k^R$ ，船在右岸。
Step 3. 第 $k+1$ 次渡河方案如下：一虎乘船回左岸，此时 $m_k^L-(n_k^L+1)\geq0, m_k^R> n_k^R-1$ ；一牛一虎乘船到右岸， $(m_k^L-1)-n_k^L\geq0, m_k^R+1> n_k^R$ ；一牛乘船回左岸， $m_k^L-n_k^L\geq1, m_k^R= n_k^R$ ；一牛一虎乘船到右岸，此时， $(m_k^L-1)-(n_k^L-1)\geq1, m_k^R+1= n_k^R+1$ ，船在右岸，完成第 $k+1$ 次渡河， $m_{k+1}^L-n_{k+1}^L\geq1, m_{k+1}^R= n_{k+1}^R$ .
Step 4. 假设第 $P$ 次渡河后，老虎全部到了右岸，船在右岸，此时，让虎每次去左岸带一只牛到右岸即可完成整个渡河。
Step 5. 证明完毕。

扩展

对已其他过河问题，如农夫、狼、鸡、菜过河问题，只需定义好状态类、可行状态判断以及状态间是否能够转移即可。

最后，欢迎浏览笔者个人主页进行交流.

本文标题:过河问题通用解法及简单证明

文章作者:wenwenzju

发布时间:2020-06-03, 23:49:09

最后更新:2020-06-03, 23:49:09

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。