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

问题描述

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

分析

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

建模

首先假设商人和仆人都在北岸,他们的目的地是南岸。那么我们可以用\((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\)来说,它必须满足以下三个条件,才能被称为是允许转移集合

  1. \(x_k >= y_k\)
  2. \(x_k+(-1)^ku_k >= y_k+(-1)^kv_k\)
  3. \(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)\),并且中间的每一次转移都属于允许转移集合1

求解

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

商人过河

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

算法

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

最后贴出代码:

#!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()

参考资料

  • 《数学建模》姜启源

  1. 在这个具体的题目中,由于商人人数和仆人人数都是相对较小的,允许转移集合是可以被穷举列出来的,但是如果是m个商人和n个仆人的时候,那就只能通过上述三个条件来进行判断了。 

  2. 我在网上看到有人用的是Dijkstra算法,Dijkstra算法是用来计算固定点到图中其他所有定点的最短路径,而我们的题目中只需要计算两个固定点之间的路径,使用Dijkstra的话,似乎有些“大材小用”了。 

Share on: TwitterFacebookEmail


Flyaway is the owner of this blog.

Published

Category

algorithm

Tags

Contact