曲靖师范学院
本科生毕业论文论文题目: matlab求解夫妻过河问题
作者、学号：郭彩虹2010111212
学院、年级：数学与信息科学学院2010级
学科、专业：数学数学与应用数学
指导教师：郭昀
完成日期：2013年12月27日
曲靖师范学院教务处
摘要
渡河问题.[]1始于公元8 世纪，至今它仍是一个逻辑难题，许多数学建模教材上已经提到.这个问题指的是：有不同的对象或生物，他们其中一些相互不共存，逐步地让一小群体从河的一岸到另一岸，经过有限步后，该群体全部从一岸达到另一岸，并且要求没有任何损失．在渡河问题的夫妻过河问题中我们发现状态转移问题有时不一定有解，有时的解又不一定有规律，本文对于夫妻过河问题利用图解法和matlab编写程序求解5对、6对夫妻过河是否有解，并推广到n对夫妻与船的运载能力m对于能否安全渡河时它们之间的关系。
关键词：多步决策 matlab 数学模型渡河问题
Problem of couples across the river
Abstract: the problem of crossing the river. In the 8th century, it still is a logical problem, many mathematical modeling teaching material has been mentioned. The question is: have different objects or creatures, they lack some mutual coexistence, gradually to a small group from one bank to another bank of the river, after finite steps, the group all from one side to the other shore, and requires no losses. In crossing the river problem of couples across the river, we found that state transition problem sometimes does not necessarily have a solution, sometimes the solution is not necessarily regular, in this paper, using the graphical method for the problem of couples across the river and the matlab program to solve the 5, 6 for couple across a river if there is a solution,And derived to n couple with the ability to run m to safe crossing the river when the relationship between them.
Keywords: Multistep decision Matlab Mathematical model Problem of crossing the river
目录
1 引言 (1)
2 文献综述 (1)
2.1 国内外研究现状 (1)
2.2 国内外研究现状评价 (2)
2.3 问题提出 (2)
3 模型假设 (2)
4 符号说明 (2)
5 重述3、4对夫妻过河问题的解 (3)
5.1 3对夫妻过河的解 (3)
5.2 4对夫妻过河的解 (3)
6 五对夫妻过河模型 (4)
6.1 模型构成 (4)
6.2 模型建立 (4)
6.3 模型求解 (4)
6.31 Matlab编程求解 (4)
6.32 图解法 (7)
7 六对夫妻过河模型 (8)
7.1 模型构成 (8)
7.2 模型求解 (9)
8 n对夫妻过河情况 (10)
8.1 求解 (10)
8.2 验证 (11)
9 总结与展望 (12)
9.1 总结 (12)
9.2后续研究工作展望 (13)
参考文献 (14)
附录 (15)
1 引言
这是一个古老的阿拉伯数学问题。有3对夫妻要过河，船最多可载2人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在一起，问此时这3对夫妻能否过河？如果是4对夫妻过河，其他条件不变的情况下，夫妻能否过河？就这一问题我们发现状态转移问题有时不一定有解，有时的解又不一定有规律（当4对夫妻过河，其他条件不变的情况下，夫妻能否过河？我们发现此问题是无解的），但是当我们改变条件船最多可载3人时有解.
就其数学建模思想来说, 一般采用将该问题转化为一个多步决策模型, 模型求解的方法大多为图解法然而一旦问题的条件(例如丈夫、妻子或者小船上每次渡河人数等) 发生变化, 图解法求解犹如大海捞针!很难奏效. 因此计算机编程求解模型的方法就显得非常重要了.该题求解编程的难点在于允许状态与决策这两个方面的处理与实现[]2.
此问题中利用的多目标决策方法是从20世纪70年代中期发展起来的一种决策分析方法.决策分析是在系统规划、设计和制造等阶段为解决当前或未来可能发生的问题，在若干可选的方案中选择和决定最佳方案的一种分析过程.在社会经济系统的研究控制过程中我们所面临的系统决策问题常常是多目标的，例如我们在研究生产过程的组织决策时，既要考虑生产系统的产量最大，又要使产品质量高，生产成本低等。这些目标之间相互作用和矛盾，使决策过程相当复杂使决策者常常很难轻易作出决策.这类具有多个目标的决策总是就是多目标决策. 多目标决策方法现已广泛地应用于工艺过程、工艺设计、配方配比、水资源利用、能源、环境、人口、教育、经济管理等领域.
2 文献综述
2.1国内外研究现状
渡河问题有不同的版本，从目前参阅的文献资料中了解的信息来看文献[1]、[5]、[6]的商人和随从渡河问题利用通过遍历状态空间树来搜索可行的渡河方案、建立多步决策模型、计算机编程等方法解决,文献[3]、[4]的传教士和食人族难题[]3仿照整数( 二元) 规划的图示方法、用矩阵表示与迭代算法[]4等方法解决，文献[5]军官渡河问题和人与机器渡河问题[]5利用Dijkstra算法,文献[13]的人、猫、鸡、米过河问题利用计算机C语言编程求解，文献[6]、[15]的人、狼、羊、菜过河问题利用多为向量的方法解
决[]6.但是解决方法是类似的,都是要找到允许状态和允许决策[]7.
2.2国内外研究现状评价
综上所述，渡河问题至今仍是一个逻辑难题.国内外对于过河问题的研究很多，但是不是很全面，由于渡河问题的种类很多，尽管研究方法大体相同，但是他的解却是有很多种，或者有的问题根本无解，就夫妻过河问题而言当4对夫妻过河，船只能载2人时问题无解.本文在夫妻过河问题的基础上从3对、4对夫妻研究至5对、6对，并推至n对夫妻过河情况，利用图解法和matlab编程解决.
2.3 问题提出
问题1：若船最多能载3人，5对夫妻能否过河？六对夫妻呢？如果不可以那么船最多能载几人才可以？
问题2：n对夫妻要过河，船最多能载m人，n和m有怎样的关系？
任务：用matlab编写程序求问题1的解，并用已有程序验证问题2.
3 模型假设
1.不考虑过河环境因素的影响情况；
2.夫妻过河只能依靠小船；
3.每个男人和女人都会划船；
4 符号说明
i表示渡河的夫妻对数
F表示第k次渡河前此岸丈夫的人数
k
Q表示第k次渡河前此岸妻子的人数
k
x表示第k次过渡船上丈夫的人数
k
y表示第k次过渡船上妻子的人数
k
k表示第几次渡河
n表示渡河的次数
S表示允许状态集合
D表示允许决策集合
k s 表示状态 k d 表示决策
5 重述3、4对夫妻过河问题的解
有3对夫妻要过河，船最多可载2人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在一起，问此时这3对夫妻能否过河？如果是4对夫妻过河，其他条件不变的情况下，夫妻能否过河？
记k 次过河前此岸丈夫的人数为k F ，妻子的人数为k Q .记k s 表示状态，k s =（FQ ）,记k d 表示决策，k d =（xy ）。
5.1 3对夫妻过河的解
5.2 4对夫妻过河的解
可看出问题无法再解下去
（3,3） 去二女
（3,2） 去二女
（3,1） 回一女
（3,0） 回一女 （3,1） 去二男 （1,1） 回一男一女
（2,2） 去二男 （0,2） 去一女 （0,3）
去二女
（0,1）
回一女 （0,2）
去二女
（0,0）
（4,4）
去二女
（4,2）
回一女
（4,3）
去二女
（4,1）
回一女
（4,2）
（4,0）
去两女
去两男
（
4,0）
6 五对夫妻过河模型
6.1模型构成
记第k 次过河前此岸丈夫的人数为k F ，妻子的人数为k Q ，k =1,2，3……
由已知条件知可取状态为（0,1）（0,2）（0,3）（0,4）（0,5）（0,0）（5,5）（5,4）（5,3）（5,2）（5,1）（5,0）（1,1）（2,2）（3,3）（4,4）共16种，用S 表示可取状态集合，成为允许状态集合，不难验证，S 对此岸和彼岸都是可行的.
记第k 次过渡船上的丈夫的人数为k x ，妻子的人数为k y ，由已知条件知可取状态为（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1），其中（1，1）表示1对夫妻，共五种，用D 表示可取状态集合，成为允许决策集合[]8.
6.2模型建立
我们发现当k 为奇数时船从此岸驶向彼岸，当k 为偶数时船从此岸驶向彼岸，记k s 表示状态，k s =（FQ ）,记k d 表示决策，k d =（xy ）。所以状态k s 随k d 的变化规律为：
()k k
k 1k d 1s s -+=+
称为状态转移律
求决策k d ∈D （k =1,2，3……n ）使状态k s ∈S 按照状态转移律，由初始状态
1s =（1,1）有限步n 到达状态1n s +=（0，0）
6.3模型求解
6.31 Matlab 编程求解
对于这个问题通常用“穷举求解” 的方法， 即从初始状态（5， 5）开始， 从允许决策集合D 中选择一个决策， 产生一个新状态.若新状态可行， 则保存该状态， 并从这个状态开始继续进行决策寻找下一可行状态； 否则， 从允许决策集合D 中重新选择一个新决策以产生下一状态.如果某个状态的所有可选决策产生的下一状态均不可行， 则返回到上一个可行状态， 从该可行状态开始寻找除了状态的其它状态， 直到找到一个可行的下一状态.这个决策过程反复进行， 直到到达最终状态（0， 0），即可以安全渡河[]9.其中，判断状态是否可行包括两个方面：
（1）该状态是否在允许状态集合S 中.
（2）在由决策所确定产生的一系列状态中，船由此岸驶向彼岸前的所有状态不允许重复，船由彼岸驶向此岸前的所有状态亦不允许重复[]10.
可以应用人工智能原理中的状态空间搜索法解决.首先定义一个安全渡河问题的状态空间，规定出该空间的初始状态和目标状态，建立相应的渡河规则和控制策略，而后推理搜索，直至找出由初始状态到目标状态的某条路径或一组路径，即安全渡河的操作序列[]10.用matlab[]11编写一段程序求解，程序编写思路如下图[]12
开始
变量初始赋值化
可行状态
奇数次移动偶数次移动
选择一种可行方案
继续移动且下一次
移动重新开始
结束
程序运行[]15,14结果（程序见附录）：
ans =
Columns 1 through 11
5 5 5 5 5 5 5 2 3 0 0 5 2 3 0 1 0 2 2 3 3 4
Columns 12 through 22
0 0 0 -1 -1 -1 -1 -1 -1 -1 -1
1 2 0 -1 -1 -1 -1 -1 -1 -1 -1
Columns 23 through 33
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Columns 34 through 44
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Columns 45 through 50
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
从运行结果来看通过13次可以安全渡河，但是这个解不是最优解（即渡河次数最少）.从（5,5）—（0,0）我们可看到中间每一次的运行步骤都符合我们的可取状态集合
S ={（0,1）（0,2）（0,3）（0,4）（0,5）（0,0）（5,5）（5,4）（5,3）（5,2）（5,1）（5,0）
（1,1）（2,2）（3,3）（4,4）}，我们也可验证每一步渡船上的人数也符合允许决策集合D ={（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1）}，因此程序可行.
6.32 图解法[]16
当所讨论问题变量不很多时，我们也常常利用作图的方法来解决状态转移问题．对于“夫妻过河”问题求解，也就是要确定一系列的允许运算d k (k=1，2，…,m)，使得
)0,0()5,5(m 21=+??+++d d d
我们可以在x －y 平面上标出允许状态集S 中的点，
而将允许运算看作是沿方格移动1格或2格，为了区别小船的往返，我们用实线表示小船由此岸至彼岸，用虚线表示小船由彼岸至此岸．于是我们给出一个“夫妻过河”问题的最优解法.
（5,5）
去三女
（5,2）
回一女
（5,3）
去两女
（5,1）
回一女
（5,2）
去三男
（2,2）
回一男一女
（3,3）
去三男
（0,3）
回一女
（0,4）
（0,1）
去三女
回一女
（0,2）
去两女
（0,0）
图解过程如下图所示：
7 六对夫妻过河模型
7.1模型构成
记第k 次过河前此岸丈夫的人数为k F ，妻子的人数为k Q ，k =1,2，3……
由已知条件知可取状态为（0,1）（0,2）（0,3）（0,4）（0,5）（0,6）（0,0）（6,6）（5,5）（5,4）（5,3）（5,2）（5,1）（5,0）（1,1）（2,2）（3,3）（4,4）（5,5）共19种，用S 表示可取状态集合，成为允许状态集合，不难验证，S 对此岸和彼岸都是可行的. 记第k 次过渡船上的丈夫的人数为k x ，妻子的人数为k y ，由已知条件知可取状态为（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1），其中（1，1）表示1对夫妻，共五种，用D 表示可取状态集合，成为允许决策集合.
模型建立：我们发现当k 为奇数时船从此岸驶向彼岸，当k 为偶数时船从此岸驶向彼岸，记k s 表示状态，k s =（FQ ）,记k d 表示决策，k d =（xy ）。所以状态k s 随k d 的变化规律
为： ()k k k 1k d 1s s -+=+称为状态转移律
5
4
3 2 1
（0,0） （5,5）
1
2
3
4
5
x
y
求决策k d ∈D （k =1,2，3……n ）使状态k s ∈S 按照状态转移律，由初始状态1s =（1,1）有限步n 到达状态1n s +=（0，0）
7.2模型求解
同样的我们仿照“五对夫妻过河”在x －y 平面上标出允许状态集S 中的点， 而将允许运算看作是沿方格移动1格或2格，为了区别小船的往返，我们用实线表示小船由此岸至彼岸，用虚线表示小船由彼岸至此岸．
在解题过程中我们发现若要让六对夫妻过河，路径须经由（6，3）到 （0，4）状态，由条件所致，无法通过这条路径. 那么我们改变条件为船最多能载4人，图解过程如下图
y 5
4 3 2
1 （0,0） （6,6）
1
2
3
4
5
x
6
所以由此我们得到6对夫妻，当船至少能载4人时才可以安全渡河
8 n 对夫妻过河情况
8.1求解
因n 对夫妻要过河，船最多能载m 人，我们可以利用一个简单的图解法 在解决前面的问题中，发现当可行时每一次图解法都要经过下图步骤
m
m 或m -1
y
5 4 3
2
1
（0,0）
（6,6）
1
2
3
4
5
x
6
另外我们总结了几组数据：
安全渡河可行数据表
序号夫妻（对）船最大容量（人）
1 3 2
2 4 3
3 5 3
4 6 4
5 7 4
由此可推断如果要使夫妻能安全渡河,n和m的关系应为
n
≤m
1
2-
8.2验证
利用已有程序验证（验证程序见附录）得到以下结果
>> fuqiman
输入丈夫数目：8
输入妻子数目：8
输入船的最大容量：4
ans =
没有找到可行路径！
>> fuqiman
输入丈夫数目：8
输入妻子数目：8
输入船的最大容量：5
ans =
0 0
0 5
0 4
4 4
3 3
8 3
8 2
8 4
8 3 8 8 >> fuqiman
输入丈夫数目：9 输入妻子数目：9 输入船的最大容量：5
ans =
0 0 0 2 0 1 0 5 5 5 4 4 9 4 9 3 9 5 9 4 9 9
>> fuqiman
输入丈夫数目：10 输入妻子数目：10 输入船的最大容量：5
ans =
没有找到可行路径
（此处我们不再举过多的例子）
9 总结与展望
9.1总结
本文对夫妻过河问题进一步探讨，由五对、六对延伸至n 对夫妻.其中五对、六对夫
妻过河利用matlab 编程和图解法解决，解决n 对夫妻要过河，船最多能载m 人，n 和m 有怎样的关系时，利用类比推断的方法推断出12-≤m n
.再利用已有程序检验.鉴于
本人知识水平和计算机编程水平有限，还有很多不足的地方，有待于日后进一步学习和研究．
9.2后续研究工作展望
本文对夫妻过河问题进一步探讨，由五对、六对延伸至n对夫妻.在五对夫妻渡河方案中由于本人计算机编程水平有限得到的结果不是最优解（即过河所用次数最少），在n对夫妻要过河，船最多能载m人，n和m有怎样的关系时，尽管推论得到验证但是说服力不足，所以后续的研究工作在如下几个方面展开：
1.利用matlab编程得到五对夫妻过河最优情况
2.仿照文献中已有的方法求解夫妻过河问题
参考文献
[1] 付艳玲，刘高峰，张伟.k m n --商人渡河问题解的存在性及算法实现[J].工程数学学报，2013,30:561
[2] 邵建峰，许丙胜.商人渡河问题的算法实现[J].数学的实践与认识，2012,42:137 [3] 温鸿航, 温鸿翔, 任晓莉. 渡河问题的图解分析[J].电子科技，2012,25:33
[4] 温鸿航，任晓莉，温鸿翔. 渡河问题的矩阵表示与迭代算法[J].电子科技,2012,25:101 [5] 达瓦, 加央.
种种渡河同题及其算法[J].科教文汇,2008,269
[6] 俞涛.“船运狼、羊、菜”问题的新解法[J]. 河北师范大学学报( 自然科学版),1996,20:27 [7] 善强, 雷鸣. 数学模型( 第二版)[M].重庆大学出版社,1998.24
[8] 姜启源，谢金星，叶俊.数学模型[M].第三版.北京：高等教育出版社，2003,7 [9] 李天瑞.安全渡河问题的计算机求解和模拟[J].工科数学，1999，15:119 [10]武建林.商人渡河游戏的解题算法[J].电脑编程技巧与维护，2009,78
[11]张念发，张宪新，刘长征.基于状态空间搜索法的商人过河问题解决方案[J].电脑编程技巧与维护，2010，36
[12]刘卫国.MATLAB 程序设计教程[M].第二版.北京：中国水利水电出版社，2010,2 [13]赵静,但琦.数学建模与数学实验[M].第三版.北京:高等教育出版社,2003,19 [14]张北辰，张建明.状态转移问题的计算机模拟[J].益阳师专学报，1998，13:67 [15]俞哲明，樊艳芬.利用数组解决农夫过河问题[J].福建电脑，2013,（5）：151 [16]陈义华.状态转移问题的图论法建模[J]. 甘肃工业大学学报,1997,23:92
附录
五对夫妻过河程序：
function kexing = f_kexing(a)
% 判断一个状态a是否可行状态
% 可行状态为（0,i),（i,i),(5,i);0<=i<=5
if (a(1) == a(2) && a(1) >= 0 && a(1) <= 5)%可行状态为（i,i),
kexing = 1;
else
if (a(1) == 0 ) && a(2) >= 0 && a(2) <= 5%可行状态为（0,i)
kexing = 1;
else
if((a(1) == 5) && a(2) >= 0 && a(2) <= 5)%可行状态为（5,i) kexing = 1;
else
kexing = 0;
end
end
end
function jie = guohe()
kaishi = [5,5];%开始状态
jieshu = [0,0];%结束状态
jie = -ones(2,50) ;
jie(:,1) = kaishi;
jie(:,2) = [5,2];%第一次移动三个人过去
%过去时人尽量多，去多
qu = [0 3 2 1 2 0 0 1;
3 0 1 1 0 2 1 0];
%回来时人尽量少
hui = [0 1 0 2 1 0 3 2;
1 0
2 0 1
3 0 1];
yd_cishu = 2;%移动次数
index = zeros(1,50);%指示第yd_cishu次移动是采用的是那种方式
index(1) = 1;
index(2) = 1;
%注意矩阵是否相等的判断
while(jie(1,yd_cishu) ~= jieshu(1) || jie(2,yd_cishu) ~= jieshu(2) )
if( mod(yd_cishu,2) ~= 0 )%奇数次移动
while(index(yd_cishu)<=9)
switch(index(yd_cishu))
case {1}
jixu = jie(:,yd_cishu) - qu(:,1); case {2}
jixu= jie(:,yd_cishu) - qu(:,2);
case {3}
jixu = jie(:,yd_cishu) - qu(:,3);
case {4}
jixu = jie(:,yd_cishu) - qu(:,4);
case {5}
jixu = jie(:,yd_cishu) - qu(:,5);
case {6}
jixu = jie(:,yd_cishu) - qu(:,6);
case {7}
jixu = jie(:,yd_cishu) - qu(:,7);
case {8}
jixu = jie(:,yd_cishu) - qu(:,8);
end
if(f_kexing(jixu))%当移动状态可行，则保存移动情况
yd_cishu = yd_cishu + 1;%继续移动
jie(:,yd_cishu) = jixu;
index(yd_cishu) = index(yd_cishu) + 1;
index(yd_cishu) = 1;%下一次移动选择从新开始
break;
else
index(yd_cishu) = index(yd_cishu) + 1;
end
end
if(index(yd_cishu)>9)
yd_cishu = yd_cishu - 1;%回退
end
else%偶数次移动
while(index(yd_cishu)<=9)
switch(index(yd_cishu))
case {1}
jixu = jie(:,yd_cishu) + hui(:,1);
case {2}%
jixu = jie(:,yd_cishu) + hui(:,2); case {3}%
jixu = jie(:,yd_cishu) + hui(:,3);