夫妻过河问题[整理]　

夫妻过河问题[整理]　 夫妻过河问题是一个历史久远的阿拉伯的趣味智力题(问题是这样叙述的: 有三对夫妻一同旅行，途中需要渡过一条河(按照古代当地的规矩，妻子不能在其丈夫不在场的情况下与其他男人在一起，而渡河的小船至多只可以载乘二人(无船夫)(问如何安排渡河程序，使这三对夫妻既不违反当时的规矩，又能顺利地渡过河去( 这类问题在一些智力竞赛中，常常是根据问题所给条件，逐一试验，最后得出结论(但这样做似乎与数学并无什么联系(其实只要对这些问题加以分析，建立适当的模型，就会发现判定这类问题是否有解，以及如何求解都并不困难，而这类数学模型一般被称为状态转移模型( 1(建模 我们把此岸有M个男人(丈夫)，F个女人(妻子)的情形称为一种状态，用一对数组(M，F)示，注意M、F的顺序不要变，其中M、F均为不小于0且不大于3的整数(很显然，在我们的问题中，并非所有数组所表示的状态。 (M，F) M，F?Z，0?M，F?3 都是被允许的(例如在0,M,F?3时，状态(M，F)就不允许，因为它表示必有女子在其丈夫不在场的情形下与其他男人在一起了(除去不允许状态后，剩下的就都称为允许状态(于是我们可以把本问题的允许状态集合S写出来: S={(0，0)，(0，1)，(0，2)，(0，3)，(1，1)，(2， 2)，(3，3)，(3，2)，(3，1)，(3，0)，(2，1)}( 有了允许状态集S，还需要知道这些允许状态之间是如何变化的，特别是如何从三对夫妻全在此岸是的状态(3，3)一步步地变为三对夫妻全在彼岸的状态(0，0)的(这就需要讨论所谓运算(或决策)，它们也是由一对有序数组表示的(因为小船每次从河的一岸驶向另一岸都使状态发生变化，故我们把小船的一次运送称为一次运算(或决策)( 我们第n次运算dn由第n+1个状态Sn+1减去第n个状态Sn来确定，即 dn=Sn+1,Sn( 注意到小船由此岸驶向彼岸时，此岸人数由多变少，而船由彼岸驶回此岸时，此岸人数由少变多(又由于小船载乘人数不多于2人，故运算dn必然满足: dn=(,1)n(p，q)，p，q?0且1?p+q?2，n?N， 其中p，q分别表示小船离岸时船上男人与女人的数量(当Sn+1，Sn均为允许状态时，称dn为允许运算，我们把方程 Sn+1=Sn+dn 称为状态转移方程( 至此，我们已经把问题完全抽象化了( 2(解法 我们下面的任务就是利用状态转移方程来求解(实际上是要一步一步地考虑由一个允许状态加上一个允许运算，得出另一个允许状态的过程，试图寻求一条由初始状态(3，3)转为期望状态(0，0)的路径(当然对有些问题这种路径不一定存在)，也就是要确定一系列的允许运算dn(n=1，2，„，m)，使得 (3，3)+d1+d2+„+dm=(0，0)( 由于本问题涉及的变量不多，约束条件也不多，我们可以凭简单的演算来求解(当某些问题变量较多，约束条件也较复杂时，我们可以借助计算机，以避免十分繁琐的演算( 下面是利用状态转移方程直接求解“夫妻过河”问题的一条路径: 3(讨论 与“夫妻过河”类似的有“商人过河”或“传教士与野蛮人过河”的问题(其中“传教士与野蛮人过河”问题是这样叙述的:三个传教士与三个野蛮人要过河，小船最多可载二人(传教士以为只要野蛮人多于他们的人数，他们就会被害，问如何设计渡河方案(细心的读者可能会注意到，前面讨论过的“夫妻过河问题中“女子不得在其丈夫不在场时与其他男人在一起”这一条件实际上是限定了在任何情况下，女子的数量不得多于男子，这样就与“野蛮人的人数不得多于传教士的人数”相似了(于是这两个问题所抽象出来的数学模型其实是一样的，解法自然也是相同的( 考虑一下当问题的条件发生变化时，问题的解决会朝什么方向发展是极有意义的(很明显，夫妻数量的增加会使问题难于解答，甚至不可解(请读者考虑四对夫妻的情形)，而小船载人的数量增加(比如可载3人)将大大降低问题的难度(若小船可载4人的话，则无论多少对夫妻过河，就都不成问题了( 还有所谓“人狗鸡米过河”问题，也是颇有趣味的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人不在时，狗会吃鸡，鸡会吃米，问如何设计顺利过河方案(我们把这个问题的解答留给同学们(另外，用一定容积的若干油瓶倒油的问题也属此类问题( 下面给出状态转移问题的图解法: 当所讨论问题变量不很多时，人们也常常利用作图的方法来解决状态转移问题(例如对于“夫妻过河”问题，可以在M,F平面上标出允许状态集S中的点，而将允许运算看作是沿方格移动1格或2格，为了区别小船的往返，我们用实线表示小船由此岸至彼岸，用虚线表示小船由彼岸至此岸(于是下图就是“夫妻过河”问题的一个图解法。 4(结语 状态转移问题一般并不一定有解存在，有解时解法又不一定唯一(当解法不唯一时，我们应该比较不同解法的优劣，从而确定出最优解法(有兴趣的同学请考虑一下“夫妻过河”问题的解法是否唯一，图解法或许对你很有帮助。