夫妻过河问题

夫妻过河问题 题目: 夫妻过河 三对夫妻要过河，河中只有一条小船，可容两人。每个个丈夫都不愿让自己的妻子和另一个男人在一起，除非自己也在场。 (1)如何过河,有多少种渡河次数最少的方法, (2)三对夫妻改为四对夫妻，其他条件不变，能过河吗,为什么,若船至多可容三人，能过河吗,怎么过, 数学建模 论文题目:夫妻过河问题 姓名1:薛晓辉学号:200816030131班级:国贸081601班 姓名2:王光然学号:200816030126班级:国贸081601班 摘要:主要运用状态转移的方法分析类似于夫妻过河等问题。状态转移矩阵是俄国数学家马尔科夫提出的，他在20世纪初发现:一个系统的某些因素在转移中，第n次结果只受第n-1的结果影响，即只与当前所处状态有关，而与过去状态无关。 在马尔科夫分析中，引入状态转移这个概念。所谓状态是指客观事物可能出现或存在的状态;状态转移是指客观事物由一种状态转移到另一种状态的概率。 关键词:状态转移，状态集合。 正文: 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)( 由于本问题涉及的变量不多，约束条件也不多，我们可以凭简单的演算来求解(当某些问题变量较多，约束条件也较复杂时，我们可以借助计算机，以避免十分繁琐的演算( 下面是利用状态转移方程直接求解“夫妻过河”问题的一条路径: 经过决策经过11次会完成。 于是这两个问题所抽象出来的数学模型其实是一样的，解法自然也是相同的(考虑一下当问题的条件发生变化时，问题的解决会朝什么方向发展是极有意义的(很明显，夫妻数量的增加会使问题难于解答，甚至不可解，而小船载人的数量增加将大大降低问题的难度( 还有所谓“人狗鸡米过河”问题，也是颇有趣味的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人不在时，狗会吃鸡，鸡会吃米，问如何设计顺利过河(另外，用一定容积的若干油瓶倒油的问题也属此类问题( 下面给出状态转移问题的图解法: 当所讨论问题变量不很多时，人们也常常利用作图的方法来解决状态转移问题(例如对于“夫妻过河”问题，可以在M,F平面上标出允许状态集S中的点，而将允许运算看作是沿方格移动1格或2格，为了区别小船的往返，我们用实线表示小船由此岸至彼岸，用虚线表示小船由彼岸至此岸(于是下图就是“夫妻过河”问题的一个图解 法。 若有四对夫妻就过不了河，我们可以用穷举法，若容至三人，能过河，三对夫妻最少有7次完成。若有四对夫妻，至少需要9次。 4(结语 状态转移问题一般并不一定有解存在，有解时解法又不一定唯一(当解法不唯一时，我们应该比较不同解法的优劣，从而确定出最优解法。初次写建模论文，难免有不足之处，请老师批评指正。