关于商人过河问题的分析
我的整个国庆假期就在紧张的课业学习与照顾家庭生活中结束了（呵呵别误会，我工作已久，只是今年又读了个在职研究生）。在假期尾声抽出一点时间完成之前我在https://bbs.bccn.net/thread-436739-1-1.html中对朋友的承诺，写一篇关于原贴中问题的分析。同时也算为我计划写的书积累点文字经验。表达能力有限，不到之处欢迎大家批评指正。
问题描述：
3个商人带着3个仆人过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，问商人应如何设计过河顺序才能让所有人都安全地过到河的另一边。
问题分析：
构建解题模型的第一步是分析问题包含的属性。
1 有3个商人和3个仆人。从问题的描述可以认为这里商人与商人之前没有区别，仆人与仆人之前没有区别。
2 有一条河。相应的它将地理空间分隔成三部分。左岸、右岸（只是为了区分河的两侧，怎么叫没关系，也可以叫南岸、北岸，东岸、西岸，或者本岸、对岸等等）和河上。
3 有一只船。它的属性是这个问题的核心，需要详细讨论。
3.1 船无主动动力，移动需要有人在船上控制。但由谁划船并没有限制，问题的一个隐含条件是这3个商人和3个仆人谁都会划船。
3.2 船最多可载两人，包括划船的在内。但由于上一条属性，空船不能往来于两岸之间，所以要使其移动至少要载一人。
3.3 船的位置有三种停靠在左岸、停靠在右岸、载人行驶在河中。这里“行驶在河中”是一个动态属性，其它之前分析的全都是静态属性。这个动态属性的发生受其它静态属性的制约也改变其它静态属性。下面就船的这条动态属性细讨论一下。
3.3.1 船的移动只能从它之前停靠的岸边移动到对岸。
3.3.2 船可以载一个人（可以是商人或者仆人）移动到对岸。进行这个动作的前提条件是本侧至少有一个人，并且这个人离开后本侧岸边的商人数量不少于仆人数量或者干脆没有商人（否则会发生血案）。
基于以上的属性分析我们来选择解题模型。我想大部分人分析到这里想到的可用模型是图。有没有更合适的方案？我不确定，也许有。如果有人想出了更好的算法欢迎分享。
以上面讨论到的所有静态属性构成状态结点，以小船移动这个动态属性作为边连接动作前后两种状态的结点，可以构成一个无向图。而原问题要求的解就变成了在这个图中寻找一条连接初始结点（三商三仆在河左岸，船停靠在左岸）到目的结点（三商三仆在河右岸，船停靠在右岸）的路径。我们可以应用图论的相关算法来完成这件事，这也是选择图模型的主要原因。虽然问题并没有要求找最短的路径，但事实上只要是无环的路径就是最短的（无环的路径只有两条，一条是先一商一仆过河然后商人回来，另一条是两个仆人过河然后一个回来，之后的过程殊途同归）。
寻找路径的方法有两种。一种是广度优先搜索。这是在图论中寻找最短路径最常用的方法，几乎是不二选择。另一种是深度优先搜索，大部分情况下它在找路径尤其是找最短路径方面的效率不如广度优先搜索。但由于此题的特殊性，在这里应用深度优先搜索并不比广度优先差，构造上要简洁一点。原贴中21楼墨清扬应用的就是经典的广度优先搜索，对于想学习这种算法的朋友应该好好看看。而我在原贴23楼使用的则是深度优先搜索。呵呵，其实我一开始打算用的也是广搜的，不过等我准备写代码时墨清扬的代码已经贴上来了，于是决定换一个角度给大家展示点不同的东西。这样大家可以从不同角度对比分析各种算法的优劣，为在自己的应用中选择合适的方案提供多一点的思路。至于19楼erty1001算法，不能说它错，因为它确实找到了路径，但存在大量的环，也就是做很多无用的往返。这不叫蒙特卡罗算法，充其量是在图中的随机行走，直到碰巧走到目的结点为止。这个问题的最短路径长度是11（进行11次摆渡），而erty1001代码的结果我测试了几次，最短是37,长的300+。因为步骤太多我没有实际验证结果的正确性，不过看代码应该没什么问题，至少这一方法是可行的。所以按照约定我会送erty1001 100专家分。就在这贴里吧，erty1001麻烦在这里回个贴。
分析完问题模型和算法选择就确定了程序编码方向，但在实际动手敲代码前还需要做一件事情——问题规模分析，也可以叫解空间分析、状态空间分析等等。
就是估算计算量，用于确定数据存储空间的需量和算法的运算量，以此来确定数据结构和评估算法的效率。
先算一下图中可能的状态结点大概有多少。注意，这里我们估算的是一个上限，并不是精确值。因为计算精确值往往比较复杂耗费的精力时间较多，使用简化的模型估算一个上限比较简单。只要这个上限是可接受的那实际运算就更没问题了。
状态结点包含这么五个量：左岸商人的数量、左岸仆人的数量、右岸商人的数量、右岸仆人的数量以及船的位置。由于商人和仆人的总数量一定，所以也可以描述成商人的总数量、仆人的总数量、左岸商人的数量、右岸仆人的数量和船的位置。
应用组合数学的知识可知，商人在两岸可能的分布方法有4种，仆人在两岸可能的分布方法有4种，船的位置有2种。那么可能的状态有 4 × 4 × 2 = 32种。
这32种里包含了不应该出现的会发现血案的状态，和随然可以出现但实际不会与其它状态有连接的孤立状态。所以实际状态数会比32还小。这个规模很小，怎么算都可以，这也是erty1001的随机行走可行的主要原因。
规模分析完了，下面确定数据结构。一般来讲结构体是描述状态结点的最自然选择。原贴21楼墨清扬的结构体设计的就很好，他将两个运算中不变的量（商人和仆人的各自总数量，事实上他将这两个量合并为一个量n，这样做缺憾的一点是不能解决商人和仆人数量不等的情况，当然解决原问题已经足够了）提到了结构之外，这样缩小了结构的尺寸减少了存储空间。
现在可以开始编码了。在解释原贴23楼我的代码前，先写一个教学级的范本。
呵呵再多说两句。关于我的代码风格在这个论坛里一直存在争议。喜欢的认为它简洁，不喜欢的认为它可读性太差。这个见仁见智了，我那样写代码是因为我喜欢，我喜欢简约的美，无论是算法上还是编码上。除了分隔用的空格和缩进我不允许我的代码中有多余的字符。能用一句表达的意思我不想用两句。至于可读性，我写在这里的代码多是（偏数学的、理论的）算法相关的，阅读这类代码如果没有相关的理论基础，基本是写成什么样都读不懂的。我也常强调切勿模仿这样的代码风格，我也只应用于这类小型的算法代码，我是把它当做一件艺术品在雕琢，应用型代码写成这样就麻烦了。
下面是段工整的代码范本。主要函数和变量都使用了能表述其功能的完整单词，需要说明的大概是几个缩写，比如:
变量s表示状态（state的缩写，大概有人觉得status更合适）
ss数组是状态集(states set的缩写）
ferry_s表示摆渡一个仆人过河（ferry one servant）
ferry_ss表示摆渡两个仆人过河（ferry two servants)
ferry_m表示摆渡一个商人过河（ferry one master，这里我没有用商人这个名词，用的是主人，大家理解它代表什么就好）
其它的大家以此类推。
输出的结果状态而不是状态的转移路径。转移一共需要11步形成11个后续状态，所以包括初始的状态一共12个。左右两组花括号表示两岸，其中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 <stdio.h>
#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(s.boat_location == LEFT_BANK)
{
s.left_servants--;
s.right_servants++;
s.boat_location = RIGHT_BANK;
}
else
{
s.left_servants++;
s.right_servants--;
s.boat_location = LEFT_BANK;
}
return s;
}
STATE ferry_ss(STATE s)
{
if(s.boat_location == LEFT_BANK)
{
s.left_servants -= 2;
s.right_servants += 2;
s.boat_location = RIGHT_BANK;
}
else
{
s.left_servants += 2;
s.right_servants -= 2;
s.boat_location = LEFT_BANK;
}
return s;
}
STATE ferry_m(STATE s)
{
if(s.boat_location == LEFT_BANK)
{
s.left_masters--;
s.right_masters++;
s.boat_location = RIGHT_BANK;
}
else
{
s.left_masters++;
s.right_masters--;
s.boat_location = LEFT_BANK;
}
return s;
}
STATE ferry_mm(STATE s)
{
if(s.boat_location == LEFT_BANK)
{
s.left_masters -= 2;
s.right_masters += 2;
s.boat_location = RIGHT_BANK;
}
else
{
s.left_masters += 2;
s.right_masters -= 2;
s.boat_location = LEFT_BANK;
}
return s;
}
STATE ferry_ms(STATE s)
{
if(s.boat_location == LEFT_BANK)
{
s.left_masters--;
s.left_servants--;
s.right_masters++;
s.right_servants++;
s.boat_location = RIGHT_BANK;
}
else
{
s.left_masters++;
s.left_servants++;
s.right_masters--;
s.right_servants--;
s.boat_location = LEFT_BANK;
}
return s;
}
STATE (* ferry[])(STATE) = {ferry_s, ferry_ss, ferry_m, ferry_mm, ferry_ms};
int legal(STATE s)
{
if(s.left_masters < 0) return 0;
if(s.left_servants < 0) return 0;
if(s.right_masters < 0) return 0;
if(s.right_servants < 0) return 0;
if(s.left_masters > 0 && s.left_masters < s.left_servants) return 0;
if(s.right_masters > 0 && s.right_masters < s.right_servants) return 0;
return 1;
}
int equal(STATE s1, STATE s2)
{
if(s1.left_masters != s2.left_masters) return 0;
if(s1.left_servants != s2.left_servants) return 0;
if(s1.right_masters != s2.right_masters) return 0;
if(s1.right_servants != s2.right_servants) return 0;
if(s1.boat_location != s2.boat_location) return 0;
return 1;
}
int is_end_state(STATE s)
{
return s.left_masters == 0 &&
s.left_servants == 0 &&
s.right_masters == 3 &&
s.right_servants == 3 &&
s.boat_location == RIGHT_BANK;
}
void show_state(STATE s)
{
printf("{m|%d}{s|%d} %s {m|%d}{s|%d}\n",
s.left_masters, s.left_servants, (s.boat_location == LEFT_BANK ? "!~" : "~!"),
s.right_masters, s.right_servants);
}
int search(STATE * existing_states, int states_index)
{
STATE s;
int length, i, j;
if(is_end_state(existing_states[states_index]))
return states_index + 1;
for(i = 0; i < 5; i++)
{
s = ferry[i](existing_states[states_index]);
if(!legal(s)) continue;
for(j = 0; j <= states_index; j++)
if(equal(s, existing_states[j]))
break;
if(j <= states_index) continue;
existing_states[states_index + 1] = s;
length = search(existing_states, states_index + 1);
if(length > 0) return length;
}
return 0;
}
int main()
{
STATE ss[32] = {{3, 3, 0, 0, LEFT_BANK}};
int count, i;
count = search(ss, 0);
for(i = 0; i < count; i++)
show_state(ss[i]);
return 0;
}看完上段代码再来说说我在原贴23楼贴的代码。其实算法与上面是完全一样，之所以看起来如此不同是因为我改变了数据结构。
这里我用位来表示那些状态属性，格式是这样的
1MM1SS1mm1ssB
每一个字母或数字表示一个二进制位。
其中B表示船的位置，值0表示在左岸，1表示在右岸。
s表示左岸仆人的数量。由于个人数量最大为3,所以使用了两个二进制位。
m表示左岸商人的数量。
大写字母表示右岸的情况。
间隔的1是用来隔离各个属性值。由于状态转移过程我是用数值的加减运算来模拟的，这个过程会产生对高位的进位和借位，通过多加一位1来防止运算入侵到别的属性，同时它也成为状态运算结果的一个判断标志。
函数search中的m数组便是转移操作数值。
以0x7E为例，它表示将一个仆人从左岸摆渡到右岸。
对于一个状态1MM1SS1mm1ssB来说，将一个仆人从左岸摆渡到右岸相当于给它加上(二进制）10000000，再减去10。即
s1 = s0 + 10000000b - 10b = s0 + (10000000b - 10b) = s0 + 1111100b = s0 + 7Eh(十六进制）
同理如果是将一个仆人从右岸摆渡到左岸则是 s1 = s0 - 7Eh。
隔离位剥离出来即是1001001001000，写成十六进制就是0x1248。
十六进制是二进制最自然的简写，大家应该熟练掌握它们之间的转换，应该做到看见一种形式就能随手写出另一种形式。这个基本功非常建议大家练好。
这里写成十进制数就没有它的位的意义了，看起来会很别扭。
search函数中的f数组是用来记录已经搜索过的状态的用于消除环路。上面讨论过状态数不超过32个，但我这里数组的大小是0x40，即64个。为什么？
因为商人仆人的各自总数不变，所以只需要查看一侧岸上商仆的数量及船的位置就可以确定一个状态。所以对于我代码中的一个状态表示1MM1SS1mm1ssB来说，我只需要查看低6位的值（mm1ssB）即可确定一种状态（也是因此我将表示船的位安排在了最低位）。只是中间多了一个隔离位，所以多占去32个无用空间。也可以想办法去掉这个隔离位来节省空间。但在每次搜索都增加一次位运算与总体浪费32个整型空间的权衡上，我选择了后者。时间与空间经常呈现出一种矛盾状态，我们经常要做出取此舍彼的选择。
为了查看方面下面将原贴23楼的代码再贴一遍。
程序代码：#include <stdio.h>
void show(int s)
{
printf("{m:%d, s:%d} %s {m:%d, s:%d}\n",
(s>>4)&3, (s>>1)&3, (s&1?"~!":"!~"),(s>>10)&3, (s>>7)&3);
}
int search(int * ss, int es)
{
const int m[] = {0x7E,0xFC,0x3F0,0x7E0,0x46E};
static char f[0x40];
int s, c, t, i;
if(*ss == es) return 1;
f[*ss & 0x3F] = 1;
for(i = 0; i < sizeof(m) / sizeof(m[0]); i++)
{
t = s = *ss + (*ss & 1 ? -m[i] : m[i]) ^ 1;
if((t & 0x1248) != 0x1248) continue;
t |= ((s >> 4 & 3) ? 0 : 0x30) | ((s >> 10 & 3) ? 0 : 0xC00);
if(((t - ((t & 0x186) << 3)) & 0x1248) != 0x1248) continue;
if(f[s & 0x3F]) continue;
ss[1] = s;
c = search(ss + 1, es);
if(c > 0){ f[*ss & 0x3F] = 0; return c + 1;}
}
f[*ss & 0x3F] = 0;
return 0;
}
int main()
{
int ss[16] = {0x127E}, es = 0x1FC9, c, i;
c = search(ss, es);
for(i = 0; i < c; show(ss[i++]));
return 0;
}
