怎样利用坐标解安全渡河问题

在《为什么利用图很容易求得渡河问题有几解》一文中，介绍了应用图论方法来解这类问题的途径。这里，我们介绍利用坐标来解这类问题的方法。为了使大家阅读起来更有趣味，我们把问题的情节和安全渡河的条件，都作了一些改变。

在中国的古典小说或传奇中，时常提到一伙歹徒。表面上，他们是船夫、艄公，一本正经地载货装客。待到船入江心，四顾无人之处，就露出其狰狞本相，杀人越货，无恶不作。《西游记》里唐三藏的父亲，就吃过这种大亏。

但是强盗们杀人抢东西，也是要看双方力量对比的。如果他们在人数上没有取得优势，就不敢动手，宁可空跑一趟也不敢随便冒险。

有一天，三位商人来到河边，打算过江。他们在岸上看到三位身强力壮的船夫，心中不免起了疑心。此时，江中有只小船，每次最多只能容纳两人，人一多了就要翻船沉没。因为有急事非要摆渡不可，江中又无别的船只可以利用，所以他们打算就乘坐这只小船了。商人们经常走南闯北，也非等闲之辈。如果碰到歹徒，一对一是不成问题，可以对付得了的。于是他们就想安排一种巧妙的办法，使在摆渡时，无论江中、这一岸、对岸，任何情况下都不出现不利情况（船夫人数超过商人数）。试问，这样的安排有没有可能性？摆渡是否安全可靠？

由于商人与强盗的人数都是常数，因此为了简单明瞭起见，只要分析河的这一岸的情况就行了。

设横坐标表示商人的人数，纵坐标表示强盗的人数，由于变量只能取0，1，2，3四个整数值，所以一共只能有4×4=16种可能的状态。但是，安全的状态只有以下10种：（3，0），（3，1），（3，2），（3，3）（显然，这4种状态表示商人全在江河的这一岸）；（0，0），（0，1），（0，2），（0，3）（这四种状态表示商人全在河的对岸）；（1，1），（2，2）（这时两岸都各有商人与强盗，但是强盗人数不占优势，不敢下手）。

让我们用坐标来表示（图1），你看起来就清楚了。

图1

我们的意图，就是要找到一种摆渡方案，使得从初始状态（3，3），逐渐引渡到终极状态（0，0）上去。

每一次摆渡，实质上就是—次状态的转移，我们可以用记号d_i来表示。当i为奇数时，表示小船从这一岸摇到对岸；当i为偶数时，表示小船从对岸摇到这一岸。

由于小船最多只能坐两人，自然坐一人也是可以（不坐人当然不可以，因为古代的小船不是自动机，无人就驱动不了）的，所以状态的转移是允许我们沿着方格线移动一格或二格。i为奇数时应向左、下方移动；i为偶数时应向右、上方移动。

我们的模型与决策既然都已正确作出来了，于是只要略为观察，就马上能找出正确的解法（见图2所示）。

图2

从图中可以看出，一共11次，就满足了商人们的愿望，他们安全地到达了彼岸。

值得指出的是，这种摆渡办法把所有的10种安全状态都一一遍历了，没有重复，也没有遗漏。