2.3 商人安全渡河问题

三名商人各带一个随从乘船从河的此岸渡向彼岸，一只小船最多能载两人，由他们自行划行。随从秘密约定，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人们手里。问：商人怎样安排才能安全渡河？

解题思路

对于此类古老的趣味数学问题，经过一番逻辑思索可以找出解决办法，且有多种解法。这里介绍一种将问题转化为状态转移问题的计算机求解方法。由于这个虚拟的问题已经非常理想化，所以不必再做过多的假设。安全渡河问题可以视为一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员（商人、随从各几人）做出决策，在有限步内使人员全部过河。用状态（变量）表示某一岸的人员状况，决策（变量）表示船上的人员状况，可以找出状态随决策变化的规律。因此，问题转化为在状态允许变化的范围内（即安全渡河条件），确定每一步的决策，以达到渡河的目的。

在一行6人由河的此岸向彼岸渡河时，用向量（x, y）表示有x个商人、y个随从在此岸，这里x∈{0,1,2,3}, y∈{0,1,2,3}。称向量（x, y）为状态向量。由问题的实际含义知，有些状态是允许的，而有些状态是不允许的。例如状态（2,1）是允许的，而状态（2,3）是不允许的。易知允许状态集合为：S={（x, y）|（0,0）, （0,1）, （0,2）, （0,3）, （1,1）, （1,0）, （2,2）, （2,1）, （2,0）, （3,0）, （3,1）, （3,2）, （3,3）}。当渡河时，用向量（u, v）表示有u个商人，v个随从在小船上，由小船的容量易知此时允许决策集合为：D={（u, v）|（0,1）, （0,2）, （1,1）, （2,0）, （1,0）}。

现在考察相邻两次渡河之间状态s=（x, y）随决策d=（u, v）变化的规律。为此，记状态sk=（xk, yk），其中xk, yk分别表示第k次渡河前此岸的商人数、随从数；决策dk=（uk, vk），其中uk, vk分别表示第k次渡河时小船上的商人数、随从数。

若规定二维向量按普通向量加法运算进行，则有sk+1=sk+（-1）kdk。当k为奇数时，小船从河的此岸驶向彼岸；当k为偶数时，小船从河的彼岸驶回此岸。在上述规定下，问题就归结为这样的形式：从初始状态s1=（3,3）出发，求一系列决策dk∈D，使得sk∈S，最后经过n步转化为状态sn+1=（0, 0）。注意到本问题中商人数和随从数不多，情况比较简单，决策的步数肯定也不多，可以用图解法进行求解。为此，在平面坐标系上画出方格如图2-2所示，方格点表示状态s=（x, y），允许状态集S是用圆点标出的13个格子点。允许决策dk是沿方格线移动1格或者2格，当k为奇数时，向左、下移动用实线表示；当k为偶数时，向右、上移动用虚线表示。要确定一系列的dk使由s1=（3,3）经过那些圆点最终移到原点sn+1=（0,0）。图2-2给出了一种安全渡河的移动方案，经过一系列决策d1, …, d11，最终有s12=（0,0）。即：

s1=（3,3）→s2=（3,1）→s3=（3,2）→s4=（3,0）→s5=（3,1）→s6=（1,1）→s7=（2,2）→s8=（0,2）→s9=（0,3）→s10=（0,1）→s11=（0,2）→s12=（0,0）

图2-2 安全渡河问题的解法图

【思考题】 当商人数、随从数和小船容量发生变化时，安全渡河问题将会变得更加复杂。请大家尝试建立数学模型求解商人数N1、随从数N2和小船容量N3的安全渡河问题。