夫妻过河问题毕业论文

1、曲靖师范学院本科生毕业论文论文题目: matlab求解夫妻过河问题作者、学号：郭彩虹 2010111212学院、年级：数学与信息科学学院 2010级学科、专业：数学 数学与应用数学指 导 教 师：郭昀完 成 日 期：2013年12月27日曲靖师范学院教务处摘要渡河问题.始于公元8 世纪，至今它仍是一个逻辑难题，许多数学建模教材上已经提到.这个问题指的是：有不同的对象或生物，他们其中一些相互不共存，逐步地让一小群体从河的一岸到另一岸，经过有限步后，该群体全部从一岸达到另一岸，并且要求没有任何损失在渡河问题的夫妻过河问题中我们发现状态转移问题有时不一定有解，有时的解又不一定有规律，本文对于夫妻过河问题利用图解法和matlab编写程序求解5对、6对夫妻过河是否有解，并推广到对夫妻与船的运载能力对于能否安全渡河时它们之间的关系。关键词：多步决策 matlab 数学模型 渡河问题ProblemofcouplesacrosstheriverAbstract: the problem of crossing the river. In the 8th century, it still is a l

2、ogical 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 solutio

3、n 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 引言12 文献综述12.1 国内外研究现状12.2 国内外研究现状评价22.3 问题提出23 模型假设24 符号说明25 重述3、4对夫妻过河问题的解35.1 3对夫妻过河的解35.2

4、 4对夫妻过河的解36 五对夫妻过河模型46.1 模型构成46.2 模型建立46.3 模型求解46.31 Matlab编程求解46.32 图解法77 六对夫妻过河模型87.1 模型构成87.2 模型求解98 n对夫妻过河情况108.1 求解108.2 验证119 总结与展望129.1 总结129.2后续研究工作展望13参考文献14附 录151 引言这是一个古老的阿拉伯数学问题。有3对夫妻要过河，船最多可载2人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在一起，问此时这3对夫妻能否过河？如果是4对夫妻过河，其他条件不变的情况下，夫妻能否过河？就这一问题我们发现状态转移问题有时不一定有解，有时的解又不一定有规律（当4对夫妻过河，其他条件不变的情况下，夫妻能否过河？我们发现此问题是无解的），但是当我们改变条件船最多可载3人时有解.就其数学建模思想来说, 一般采用将该问题转化为一个多步决策模型, 模型求解的方法大多为图解法然而一旦问题的条件 (例如丈夫、妻子或者小船上每次渡河人数等) 发生变化, 图解法求解犹如大海捞针!很难奏效. 因此计算机编程求解模型的方法就显得

5、非常重要了.该题求解编程的难点在于允许状态与决策这两个方面的处理与实现.此问题中利用的多目标决策方法是从20世纪70年代中期发展起来的一种决策分析方法.决策分析是在系统规划、设计和制造等阶段为解决当前或未来可能发生的问题，在若干可选的方案中选择和决定最佳方案的一种分析过程.在社会经济系统的研究控制过程中我们所面临的系统决策问题常常是多目标的，例如我们在研究生产过程的组织决策时，既要考虑生产系统的产量最大，又要使产品质量高，生产成本低等。这些目标之间相互作用和矛盾，使决策过程相当复杂使决策者常常很难轻易作出决策.这类具有多个目标的决策总是就是多目标决策. 多目标决策方法现已广泛地应用于工艺过程、工艺设计、配方配比、水资源利用、能源、环境、人口、教育、经济管理等领域.2 文献综述2.1国内外研究现状渡河问题有不同的版本，从目前参阅的文献资料中了解的信息来看文献1、5、6的商人和随从渡河问题利用通过遍历状态空间树来搜索可行的渡河方案、建立多步决策模型、计算机编程等方法解决,文献3、4的传教士和食人族难题仿照整数( 二元) 规划的图示方法、用矩阵表示与迭代算法等方法解决，文献5军官渡河问题和人

6、与机器渡河问题利用Dijkstra算法,文献13的人、猫、鸡、米过河问题利用计算机C语言编程求解，文献6、15的人、狼、羊、菜过河问题利用多为向量的方法解决.但是解决方法是类似的,都是要找到允许状态和允许决策.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 符号说明表示渡河的夫妻对数表示第k次渡河前此岸丈夫的人数表示第k次渡

7、河前此岸妻子的人数表示第次过渡船上丈夫的人数表示第次过渡船上妻子的人数表示第几次渡河表示渡河的次数表示允许状态集合表示允许决策集合表示状态表示决策5 重述3、4对夫妻过河问题的解有3对夫妻要过河，船最多可载2人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在一起，问此时这3对夫妻能否过河？如果是4对夫妻过河，其他条件不变的情况下，夫妻能否过河？记次过河前此岸丈夫的人数为，妻子的人数为.记表示状态，=（）,记表示决策，=（）。5.1 3对夫妻过河的解（3,3）去二女（3,2）去二女（3,1）回一女（3,0）回一女（3,1）去二男（1,1）回一男一女（2,2）去二男（0,2）去一女（0,3）去二女（0,1）回一女（0,2）去二女（0,0）5.2 4对夫妻过河的解（4,3）去二女（4,2）回一女（4,4）去二女（4,0）去两男去两女（4,0）（4,2）（4,1）回一女 可看出问题无法再解下去6 五对夫妻过河模型6.1模型构成记第次过河前此岸丈夫的人数为，妻子的人数为，=1,2，3由已知条件知可取状态为（0,1）（0,2）（0,3）（0,4）（0,5）（0,0）（5,

8、5）（5,4）（5,3）（5,2）（5,1）（5,0）（1,1）（2,2）（3,3）（4,4）共16种，用表示可取状态集合，成为允许状态集合，不难验证，对此岸和彼岸都是可行的. 记第次过渡船上的丈夫的人数为，妻子的人数为，由已知条件知可取状态为（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1），其中（1，1）表示1对夫妻，共五种，用表示可取状态集合，成为允许决策集合. 6.2模型建立我们发现当为奇数时船从此岸驶向彼岸，当为偶数时船从此岸驶向彼岸，记表示状态，=（）,记表示决策，=（）。所以状态随的变化规律为： 称为状态转移律求决策（=1,2，3n）使状态按照状态转移律，由初始状态=（1,1）有限步n到达状态=（0，0）6.3模型求解6.31 Matlab编程求解 对于这个问题通常用“穷举求解” 的方法， 即从初始状态（5， 5）开始， 从允许决策集合D 中选择一个决策， 产生一个新状态.若新状态可行， 则保存该状态， 并从这个状态开始继续进行决策寻找下一可行状态； 否则， 从允许决策集合D 中重新选择一个新决策以产生下一状态.如果某个状态的所有可选决策产生的下一状态均不可行， 则返回到上一个可行状态， 从该可行状态开始寻找除了状态的其它状态， 直到找到一个可行的下一状态.这个决策过程反复进行， 直到到达最终状态（0， 0），即可以安全渡河.其中，判断状态是否可行包括两个方面： （1） 该状态是否在允许状态集合S 中.（2） 在由决策所确定产生的一系列状态中，船由此岸驶向彼岸前的所有状态不允许重复， 船由彼岸驶向此岸前的所有状态亦不允许重复. 可以应用人工智能原理中的状态空间搜索法解决.首先定义一个安全渡河问题的状态空间，规定出该空间的初始状态和目标状态，建立相应的渡河规则和控制策略，而后推理搜索，直至找出由初始状态到目标状态的某条路径或一组路径，即安全渡河的操作序列.用matlab编写一段程序求解，程序编写思路如下图开始变量初始赋值化可行状态奇数次移动偶数次移动选择一种可行方案继续移动且下一次移动重新开始结束程序运行结果（程序见附录）：ans =

《夫妻过河问题毕业论文》由会员jiups****uk12分享，可在线阅读，更多相关《夫妻过河问题毕业论文》请在金锄头文库上搜索。