关于商人过河问题的分析
-
关于商人过河问题的分析
我的整个国庆假期就
在紧张的课业学习与照顾家庭生活中结束了（呵呵别误会，我工作已久，只是今年又
读了
个在职研究生）。
在假期尾声抽出
一点时间完成之前我在
/
中对朋友的承诺，写一篇
关于原贴中问题的分析。同时也算为我计划写的书积累点文字经验。表达能力有限，不到之处欢迎大家
批
评指正。
问题描述：
3
个商人带着
3
个仆人过河，过河的工具只有一艘小船，只能同
时载两个人过河，包括划船的人。在河的
任何一边，只要仆人的数量超过商人的数量，仆
人就会联合起来将商人杀死并抢夺其财物，问商人应如何
设计过河顺序才能让所有人都安
全地过到河的另一边。
问题分析：
构建解题模型的第一步是分析问题包含的属性。
1
有
3
个商
人和
3
个仆人。从问题的描述可以认为这里商人与商人之前没有
区别，仆人与仆人之前没有区
别。
2
有一条河。相应的它将地理空间分隔成三部分。左岸、右岸（只是为了区分河的两侧，怎
么叫没关系，
也可以叫南岸、北岸，东岸、西岸，或者本岸、对岸等等）和河上。
3
有一只船。它的属性是这个问题的核心，需要详细讨论。
3.1
船无主动动力，移动需要有人在船上控制。但由谁划船
并没有限制，问题的一个隐含条件是这
3
个商
< br>人和
3
个仆人谁都会划船。
3.2
船最多可载两人，包括划船的在内。但由于上一条属性
，空船不能往来于两岸之间，所以要使其移动
至少要载一人。
3.3
船的位置有三种停靠在左岸、
停靠在右岸、
载人行驶在河中。
这里
“
行驶在河中
”
是一个动态属性，其它<
/p>
之前分析的全都是静态属性。这个动态属性的发生受其它静态属性的制约也改变其它静态属
性。下面就船
的这条动态属性细讨论一下。
3.3.1
船的移动只能从它之前停靠的岸边移动到对岸。
3.3.2
船可以载一个人
（可以是
商人或者仆人）
移动到对岸。
进行这个动作的前提条件是本侧至
少有一个人，
并且这个人离开后本侧岸边的商人数量不少于仆人数量或者干脆没有商人（
否则会发生血案）。
基于以上的属
性分析我们来选择解题模型。我想大部分人分析到这里想到的可用模型是图。有没有更合适
的方案？我不确定，也许有。如果有人想出了更好的算法欢迎分享。
以上面讨论到的所有静态属性构成状态结点，以小船移动这个
动态属性作为边连接动作前后两种状态的结
点，可以构成一个无向图。而原问题要求的解
就变成了在这个图中寻找一条连接初始结点（三商三仆在河
左岸，船停靠在左岸）到目的
结点（三商三仆在河右岸，船停靠在右岸）的路径。我们可以应用图论的相
关算法来完成
这件事，这也是选择图模型的主要原因。虽然问题并没有要求找最短的路径，但事实上只要
是无环的路径就是最短的（无环的路径只有两条，一条是先一商一仆过河然后商人回来，另一条是两个仆
人过河然后一个回来，之后的过程殊途同归）。
寻找路径的方法有两种。一种是广度优先搜索。这是在图论中
寻找最短路径最常用的方法，几乎是不二选
择。另一种是深度优先搜索，大部分情况下它
在找路径尤其是找最短路径方面的效率不如广度优先搜索。
但由于此题的特殊性，
在这里应用深度优先搜索并不比广度优先差，
构造上要简洁一点。
原贴中
21
楼墨清
扬应用的就是经典的广度优先搜索，
对于想学习这种算法的朋友应该好好看看。
而我在原贴
23
楼使用的则
是深度优先搜索。呵呵，其实我一开始打算用的也是广搜的，不过等我准备写代码时墨清扬的代码已经贴
上来了，于是决定换一个角度给大家展示点不同的东西。这样大家可以从不同角度对比分析各
种算法的优
劣，为在自己的应用中选择合适的方案提供多一点的思路。至于
19
楼
erty1001
算
法，不能说它错，因为它
确实找到了路径，但存在大量的环，也就是做很多无用的往返。
这不叫蒙特卡罗算法，充其量是在图中的
随机行走，直到碰巧走到目的结点为止。这个问
题的最短路径长度是
11
（进行
11<
/p>
次摆渡），而
erty1001
代码的结
果我测试了几次，最短是
37,
长的
3
00+
。因为步骤太多我没有实际验证结果的正确性，不过看代
码应该没什么问题，至少这一方法是可行的。所以按照约定我会送
erty1001 <
/p>
100
专家分。就在这贴里吧，
e
rty1001
麻烦在这里回个贴。
分析完问题模型和算法选择就确定了程序编码方向，但在实际
动手敲代码前还需要做一件事情
——
问题规
模分析，也可以叫解空间分析、状态空间分析等等。
<
/p>
就是估算计算量，
用于确定数据存储空间的需量和算法的运算量，
以此来确定数据结构和评估算法的效率。
先算一下图中可能的状态结点大概有多少。注意，这里我们估
算的是一个上限，并不是精确值。因为计算
精确值往往比较复杂耗费的精力时间较多，使
用简化的模型估算一个上限比较简单。只要这个上限是可接
受的那实际运算就更没问题了
。
状态结点包含这么五个量：左岸
商人的数量、左岸仆人的数量、右岸商人的数量、右岸仆人的数量以及船
的位置。由于商
人和仆人的总数量一定，所以也可以描述成商人的总数量、仆人的总数量、左岸商人的数
量、右岸仆人的数量和船的位置。
应用组合数学的知识可知，商人在两岸可能的分布方法有
4
种，
仆人在两岸可能的分布方法有
4
种，船的
位置有
2
种。那么可能的状态有
4
×
4
×
2
=
32
种。
这
32
种里包含了不应该出现的会发现
血案的状态，
和随然可以出现但实际不会与其它状态有连接的孤立状
态。所以实际状态数会比
32
还小。这个规模很小，怎么算
都可以，这也是
erty1001
的随机行走可行的主要
原因。
规模分析
完了，
下面确定数据结构。
一般来讲结构体是描述状态结点的最
自然选择。
原贴
21
楼墨清扬的结
构体设计的就很好，他将两个运算中不变的量（商人和仆人的各自总数量，事实上他将这两个
量合并为一
个量
n
，这样做缺憾的一点
是不能解决商人和仆人数量不等的情况，当然解决原问题已经足够了）提到了
结构之外，
这样缩小了结构的尺寸减少了存储空间。
< br>现在可以开始编码了。在解释原贴
23
楼我的代码前，先
写一个教学级的范本。
呵呵再多说
两句。关于我的代码风格在这个论坛里一直存在争议。喜欢的认为它简洁，不喜欢的认为它可
读性太差。这个见仁见智了，我那样写代码是因为我喜欢，我喜欢简约的美，无论是算法上还是编码上。
除了分隔用的空格和缩进我不允许我的代码中有多余的字符。能用一句表达的意思我不想用两
句。至于可
读性，我写在这里的代码多是（偏数学的、理论的）算法相关的，阅读这类代
码如果没有相关的理论基础，
基本是写成什么样都读不懂的。
我
也常强调切勿模仿这样的代码风格，
我也只应用于这类小型的算法代码，
我是把它当做一件艺术品在雕琢，应用型代码写成这样就麻烦了。
下面是段工整的代码范本。主要函数和变量都使用了能表述其
功能的完整单词，需要说明的大概是几个缩
写，比如
:
变量
s
表示
状态（
state
的缩写，大概有人觉得
status
更合适）
ss
数组是状态集
(states
set
的缩写）
ferry_s
表示摆渡一个仆人过河（
ferry
one
servant
）
< br>ferry_ss
表示摆渡两个仆人过河（
ferry
two
servants)
fer
ry_m
表示摆渡一个商人过河（
ferry
one
master
，这里我没有用
商人这个名词，用的是主人，大家理解它
代表什么就好）
其它的大家以此类推。
输出的结果状态而不是状态的转移路径。转移一共需要
11
步形成
11
个后续状态，所以包括初始的状态一
共
12
个。左右两组花括号表示两岸，其中<
/p>
m
后的数字表示商人的数量，
s
后的数字表示仆人的数量，惊叹
号表示船的位置。这样输出是为了方便，
改成输出转移过程也很简单，只需加个动作数组保存转移操作再
改变一下输出函数即可。
具体输出结果如下：
{m:3,
s:3}
!~
{m:0,
s:0}
{m:3,
s:1}
~!
{m:0,
s:2}
{m:3,
s:2}
!~
{m:0,
s:1}
{m:3,
s:0}
~!
{m:0,
s:3}
{m:3,
s:1}
!~
{m:0,
s:2}
{m:1,
s:1}
~!
{m:2,
s:2}
{m:2,
s:2}
!~
{m:1,
s:1}
{m:0,
s:2}
~!
{m:3,
s:1}
{m:0,
s:3}
!~
{m:3,
s:0}
{m:0,
s:1}
~!
{m:3,
s:2}
{m:0,
s:2}
!~
{m:3,
s:1}
{m:0,
s:0}
~!
{m:3,
s:3}
程序代码：
#include
#define
LEFT_BANK
0
#define
RIGHT_BANK
1
typedef
struct
{
int
left_masters;
int
left_servants;
int
right_masters;
int
right_servants;
int
boat_location;
}STATE;
STATE
ferry_s(STATE
s)
{
if
(_location
==
LEFT_BANK)
{
_servants--;
_servants++;
_location
=
RIGHT_BANK;
}
else
{
_servants++;
_servants--;
_location
=
LEFT_BANK;
}
return
s;
}
STATE
ferry_ss(STATE
s)
{
if
(_location
==
LEFT_BANK)
{
_servants
-=
2
;
_servants
+=
2
;
_location
=
RIGHT_BANK;
}
else
{
_servants
+=
2
;
_servants
-=
2
;
_location
=
LEFT_BANK;
}
return
s;
}
STATE
ferry_m(STATE
s)
{
if
(_location
==
LEFT_BANK)
{
_masters--;
_masters++;
_location
=
RIGHT_BANK;
}
else
{