商人过河问题常常出现在一些电视剧中作为考察智力的题目，其实这类问题是有迹可循的，本文将从数学建模和算法的角度来分析这一问题，给出具体的解法。

问题描述

三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人，由他们自己划行。若在河的任一岸随从人数比商人多，他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能安全过河呢?

分析

大多数人看到这类问题的第一反应就是一个方案一个方案去试，直到找到一个符合条件的方案。但是这样的寻找过程就像是没头苍蝇一样，没有章法可循。我们首先可以对原题进行建模，将原来用文字描述的问题转化为数学的语言，再从数学角度对其进行搜索。

建模

首先假设商人和仆人都在北岸，他们的目的地是南岸。那么我们可以用$(x,y)$表示在北岸的商人($x$)和仆人($y$)的人数($(x,y)\in\{0,1,2,3\}$)，用$S_k = (x_k,y_k)$表示第k次渡河前北岸的商人和仆人的人数，称其为一个状态。用$d_k=(u_k,v_k)$表示第k次渡河时，船上的商人和仆人的人数($\{(u_k,v_k)\| 0 < u_k+v_k<=2\}$)。将$d_k$称为一次转移。因为k为奇数时，是从北岸到南岸，而k为偶数时是从南岸到北岸，所以$S_k$随$d_k$的变化规律是:

$$ S_{k+1}=S_k+(-1)^kd_k $$

对于状态$S_k$和转移$d_k$来说，它必须满足以下三个条件，才能被称为是允许转移集合：

$x_k >= y_k$
$x_k+(-1)^ku_k >= y_k+(-1)^kv_k$
$3-x_k+(-1)^ku_k >= 3-y_k+(-1)^kv_k$

第一个条件是保证渡河前北岸商人数不小于仆人数，第二个条件是保证渡河后北岸的商人数不小于仆人数，第三个条件是保证渡河后，南岸的商人数不小于仆人数。

因此，原问题就转化为，寻找一个转移序列$\{d_k\|k=1,2...n\}$，使得$S_k$由初始状态$S_1=(3,3)$经有限步n到达状态$S_n=(0,0)$，并且中间的每一次转移都属于允许转移集合。¹

求解

那么，我们应该如何来寻找这样一个转移序列$d_k$呢？这其实是一个多步决策问题，但也可以把它看成一个图的问题。在直角坐标系中，将每一个状态$S_k$对应于图中的每一个点，如图所示:

商人过河

$d_k$表示沿着方格移动1格或2格，当k为奇数时，向左，下方移动，k为偶数时，向右、上方移动。这样，我们的任务就变成了寻找从$S_1=(3,3)$到原点$(0,0)$的一条路径，且这条路径上的每一次转移都属于允许转移集合。

算法

有了上述的思路以后，求解该问题就变得简单了，只要利用图论算法中的最简单的广度或深度遍历就行了²，唯一的不同是，在遍历每一个点的时候，都需要判断一下此次转移是否满足上述的三个条件。

最后贴出代码：

#!python
#coding:utf-8
"""
Author: Flyaway - flyaway1217@gmail.com
Date: 2013-08-12 13:57:31
Last modified: 2013-08-12 14:52:47
Python release: 3.3.2
"""

def issafe(state,d):
    if state[1] > state[0] and state[0] != 0:
        return False
    elif state[1] + d[1] > state[0] + d[0] and state[0] + d[0] !=0:
        return False
    elif 3 - (state[1] + d[1]) > 3 - (state[0] + d[0]) and 3 - (state[0] + d[0]) != 0 :
        return False
    else:
        return True

def explore(state,num,order,lastmove=(0,0)):
    #设置递归层数限制，否则会进入无限递归
    if num >= 20:
        return False
    if state == (0,0):
        order.append(state)
        return True
    #运输规则
    d = [(0,1),(0,2),(1,0),(1,1),(2,0)]
    for item in d:
        if item == lastmove:
            continue
        realitem = (item[0] * ((-1)**num) , item[1] * ((-1)**num))
        if issafe(state,realitem) == True:
            nextstate = ( (state[0] + realitem[0]) , ( state[1] + realitem[1]) )
            if explore(nextstate,num+1,order,item) == True:
                order.append(state)
                return True

def main():
    state = (3,3)
    order = [] 
    explore(state,1,order)
    print(order)
if __name__ == '__main__':
    main()

参考资料

《数学建模》姜启源

在这个具体的题目中，由于商人人数和仆人人数都是相对较小的，允许转移集合是可以被穷举列出来的，但是如果是m个商人和n个仆人的时候，那就只能通过上述三个条件来进行判断了。 ↩
我在网上看到有人用的是Dijkstra算法，Dijkstra算法是用来计算固定点到图中其他所有定点的最短路径，而我们的题目中只需要计算两个固定点之间的路径，使用Dijkstra的话，似乎有些“大材小用”了。 ↩

Flyaway is the owner of this blog.

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

商人过河问题

问题描述

分析

建模

求解

算法

参考资料

Comments

Published

Category

Tags

Contact