-

2021年2月23日发(作者：陪我好不好)

商人过河模型

状态集合

决策集合

平面坐标

图解法

算法

一、问题提出问题：

三名商人各带一 个随从过河，一只小船只能容纳两个人，随

从们约定，只要在河的任何一岸，一旦随从人 数多于商人人数就

杀人越货，但是商人们知道了他们的约定，并且如何过河的大权

掌握在商人们手中，商人们该采取怎样的策略才能安全过河呢？

二、问题分析这个问题已经理想化了，所以我们无需对模型

进行假设 ，该问题可以看作一个多步决策问题。每一步，船由此

岸划到彼岸或者由彼岸划回此岸， 都要对船上的人员进行决策

（此次渡河船上可以有几名商人和几名随从），在保证安全（ 两

岸的随从都不比商人多）的前提下，在有限次的决策中使得所有

人都到对岸去。因此，我们要做的就是要确定每一步的决策，达

到渡河的目标。

三、模型假设与建立记第次过河前此岸的商人数为

,

随从数

为

,

，定义状态 ：将二维向量定义为状态，将安全渡河状态下的状

态集合定义为允许状态集合，

记为记第

次渡河船上的商人数

为

，随从数为、定义决策：将二维向量

定义为决策；允许决策

集合

记作：因为小船容量为

2

，所以船上人员不能超 过

2

，而且

至少要有一个人划船，由此 得到上式。由我们定义的状态

和决

策

，我们可以发现它们之间是存在联系的：

第

1

页

共

1

页

为奇数是表示船由此岸划向彼岸，

为偶数时表示船由彼岸划

回此岸状态

是随着决策变化的，规律为：我们把上式称为状态转

移律，因此 渡河方案可以抽象为如下的多步决策模型：求决策

,

使状态

按照转移率，初始状态经有限 步后到达状态。到这里，整

个数学模型就已经非常清晰了，接下来要做的就是求解模型得 出

结果。

四、模型求解在这个模型的 求解中，我将会使用两种方法，

一种是数学图解法，用于解决和当前题目一样的规模比较 小的问

题，优点是比较简便，但是对于规模比较大的问题就无能为力

了，比如说有

50

个商人携带

50

个随从过河，第二种方法是通过

计算机编程，使用程序来解决该 问题，即使问题规模增大，我们

也可以利用计算机强大的计算能力来解决。

4

、

1

数学图解法我们

首先在

平面坐标系中画出如下方格，方格 中的点表示状态起始状

态（下图绿色点）

,

终止状态（下图红色点）允许决策

表 示的

是在方格中的移动，根据允许决策

的定义，它每次的移动范围为

1~2

格，并且

为奇数时向左或下方或左下方移动，

位偶数时向右

或上方或右上方移动。于是，这个问题就变成了，根据允许决< /p>

策

，在方格中在状态（方格点）之间移 动，找到一条路径，使得

能从起始状态（上图绿色点）

,

到达终止状态（上图图红色点）

在下图中，我们给出了一种方案，我 们可以很清楚的看到该方案

绝对不是最佳方案（渡河次数最少），它只是给出了一种方案 ，

而且我们看来是一种极其不优化的方案，但是可以很清楚地看出

第

1

页

共

1

页

图解法是如何工作的。根据上图，我们得出的方案如下：

1

：两个

随从划到对岸

2

：一个随从划回来

3

：两个随从 划到对岸

4

：一个

随从划回来

5

：两个商人划到对岸

6

：一个商人和一个随从划回来

7

：两个商人划到对岸

8

：一个随从划回来

9

：两个随从划到对岸

10

：一个商人划回来

11

：一个商人和随从划到对岸最终商人们安

全渡河

4

、

2

程序求解我们 看到上面介绍的图解法对于小规模问题

很直观也很简单，但是无法应对大规模的问题，于 是我们采用编

程的方法来再次解决上述问题，这次我使用的编程语言为、

4

、

2

、

1

创建允许状态集合对于允许状态集合，我们要去使用算法对

其进行计算，所谓允许状态无非就是，河岸两边的商人们都是安

全的：一种情况是：两 岸的商人人数都比随从人数多（对于随从

和商人人数相同的情况就是河的任一岸，商人人 数等于随从人

数）另一情况为：所有商人都在河的任何一岸，此时另一岸没有

< p>
任何商人，对于随从的人数在河的任一岸的数量不论是多少，此

时都是安全 的按照以上方法编程如下：创建允许状态集合

(): =

[] (

、

+1): (

、

+1): == 0:

、

([,])

==

、

:

、

([,])

( >= ((

、

-)

>= (

、

-))):

、

([,])

4

、

2

、

2

创建允许决策集合对于创建允许决策集合，它和船的

容量是相关的，只要每次渡河的商人 数量和随从数量小于等于船

的容量即可，代码如下：建允许决策集合，它和船的容量是相 关

第

1

页

共

1

页

的，只要每次渡河的商人数量和随从数量小于等于船的容量即

可，代码如下：创建允许决策集合

(): =

[] (

、

+1): (

、

+1): (+)

<=

、

( + )

!= 0:

、

([,])

4

、

2

、

3

如何渡河对于如何渡河问题我采取的是一种随机的方

法，对于当前安全状态，随机选择一 种决策进行试探，如果采取

该决策可以到达安全状态，则采用，如此循环，直到到达目的

地。如果采取该策略不能到达安全状态，则再次随机选择一种策

略。代码如下：

(,,): =1; = (

、

,

、

)

!=

[0,0]: =

[

、

(0,()-1)] =

[[0]+((-1)**)*[0],[1]+((-1)**)*[1]] ( ): =

[[0]+((-1)**)*[0],[1]+((-1)**)*[1]] ( %2 ==1):

个

商人，

[%]

个随从从此岸划到对岸

( %2 == 0):

个商人，

[%]

个随从从对岸划回此岸

= +

14

、

2

、

4

完整代码有了以上算法之后，我们就可以使用计算

机来解决一些较大规模的问题了，完整代码如下：

# :*- # ()

第

1

页

共

1

页

-

-

-

-

-

-

-

-