商人安全渡河问题

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

【解题思路】

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

在一行6人由河的此岸向彼岸渡河时，用向量（x，y）表示有x个商人、y个随从在此岸，这里x∈{0，1，2}，y∈{0，1，2}，称这样的向量（x，y）为状态向量.由问题的实际含义知，有些状态是允许的，而有些状态是不允许的.例如状态（2，1）是允许的，而状态（2，3）是不允许的.经分析，易知允许状态集合为：S={（x，y）|（0，0），（0，1），（0，2），（0，3），（1，1），（2，2），（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）变化的规律.为此，记状态s_k=（x_k，y_k），其中x_k，y_k分别表示第k次渡河前此岸的商人数、随从数；决策d_k=（u_k，v_k），其中u_k，v_k分别表示第k次渡河时小船上的商人数、随从数.

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

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

【思考题】

当商人数、随从数和小船容量发生变化时，安全渡河问题将会变得更加复杂.请同学们尝试建立数学模型求解商人数N₁、随从数N₂和小船容量N₃的安全渡河问题.