态转移律求决策次移动选择种可行方案继续移动且下次移动重新开始结束二〇二年六月六日星期三程序运行，结果程序见附录二〇二年六月六日星期三从运行结果来看通过次可以安全渡河，但是这个解不是最优解即渡河次数最少从我们可看到中间每次的运行步骤都符合我们的可取状态集合，我们也可验证每步渡船上的人数也符合允许决策集合，因此程序可行图解法去二女，回女去两女去两男，二〇二年六月六日星期三五对夫妻过河模型模型构成记第编写程序求问题的解，并用已有程序验证问题模型假设不考虑过河环境因素的影响情况夫妻过河只能依靠小船每个男人和女人都会划船符号说明表示渡河的夫妻对数表示第次渡河前此岸丈夫的人数表示第次渡河前此岸妻子的人数表示第次过渡船上丈夫的人数表示第次过渡船上妻子的人数表示第几次渡河表示渡河的次数表示允许状态集合表示允许决策集合二〇二年六月六日星期三表示状态表示决策重述对夫妻过河问题的解有对夫妻要过河，船最多可载人，约束条件是根据阿拉伯法律，任女子不得在其丈夫不在场的情况下与其他男子在起，问此时这对夫妻能否过河如果是对夫妻过河，其他条件不变的情况下，夫妻能否过河记次过河前此岸丈夫的人数为，妻子的人数为记表示状态记表示决策，的解可看出问题无法再解下去，去二女，去二女，回女，回女，去二男，回男女，去二男，去女，去二女，回女，去二女去二女，回女，为记表示状态记表示决策，。约束条件是根据阿拉伯法律，任女子不得在其丈夫不在场的情况下与其他男子在起，问此时这对夫妻能否过河如果是对夫妻过河，其他条件不变的情况下，夫妻能否过河记次过河前此岸丈夫的人数为，妻子的人数部分内容简介编写程序求问题的解，并用已有程序验证问题模型假设不考虑过河环境因素的影响情况夫妻过河只能依靠小船每个男人和女人都会划船符号说明表示渡河的夫妻对数表示第次渡河前此岸丈夫的人数表示第次渡河前此岸妻子的人数表示第次过渡船上丈夫的人数表示第次过渡船上妻子的人数表示第几次渡河表示渡河的次数表示允许状态集合表示允许决策集合二〇二年六月六日星期三表示状态表示决策重述对夫妻过河问题的解有对夫妻要过河，船最多可载人，约束条件是根据阿拉伯法律，任女子不得在其丈夫不在场的情况下与其他男子在起，问此时这对夫妻能否过河如果是对夫妻过河，其他条件不变的情况下，夫妻能否过河记次过河前此岸丈夫的人数为，妻子的人数为记表示状态记表示决策，。对夫妻过河的解对夫妻过河的解可看出问题无法再解下去，去二女，去二女，回女，回女，去二男，回男女，去二男，去女，去二女，回女，去二女去二女，回女，去二女，回女去两女去两男，二〇二年六月六日星期三五对夫妻过河模型模型构成记第次过河前此岸丈夫的人数为，妻子的人数为，„„由已知条件知可取状态为共种，用表示可取状态集合，成为允许状态集合，不难验证，对此岸和彼岸都是可行的记第次过渡船上的丈夫的人数为，妻子的人数为，由已知条件知可取状态为，其中，表示对夫妻，共五种，用表示可取状态集合，成为允许决策集合模型建立我们发现当为奇数时船从此岸驶向彼岸，当为偶数时船从此岸驶向彼岸，记表示状态记表示决策，。所以状态随的变化规律为称为状态转移律求决策„„使状态按照状态转移律，由初始状态，有限步到达状态，模型求解编程求解对于这个问题通常用穷举求解的方法，即从初始状态，开始，从允许决策集合中选择个决策，产生个新状态若新状态可行，则保存该状态，并从这个状态开始继续进行决策寻找下可行状态否则，从允许决策集合中重新选择个新决策以产生下状态如果个状态的所有可选决策产生的下状态均不可行，则返回到上个可行状态，从该可行状态开始寻找除了状态的其它状态，直到找到个可行的下状态这个决策过程反复进行，直到到达最终状态即可以安全渡河其中，判断状态是否可行包括两个方面二〇二年六月六日星期三该状态是否在允许状态集合中在由决策所确定产生的系列状态中，船由此岸驶向彼岸前的所有状态不允许重复，船由彼岸驶向此岸前的所有状态亦不允许重复可以应用人工智能原理中的状态空间搜索法解决首先定义个安全渡河问题的状态空间，规定出该空间的初始状态和目标状态，建立相应的渡河规则和控制策略，而后推理搜索，直至找出由初始状态到目标状态的条路径或组路径，即安全渡河的操作序列用编写段程序求解，程序编写思路如下图开始变量初始赋值化可行状态奇数次移动偶数次移动选择种可行方案继续移动且下次移动重新开始结束二〇二年六月六日星期三程序运行，结果程序见附录二〇二年六月六日星期三从运行结果来看通过次可以安全渡河，但是这个解不是最优解即渡河次数最少从我们可看到中间每次的运行步骤都符合我们的可取状态集合，我们也可验证每步渡船上的人数也符合允许决策集合，因此程序可行图解法当所讨论问题变量不很多时，我们也常常利用作图的方法来解决状态转移问题对于夫妻过河问题求解，也就是要确定系列的允许运算„使得我们可以在平面上标出允许状态集中的点，而将允许运算看作是沿方格移动格或格，为了区别小船的往返，我们用实线表示小船由此岸至彼岸，用虚线表示小船由彼岸至此岸于是我们给出个夫妻过河问题的最优解法，去三女，回女，去两女，回女，去三男，回男女，去三男，回女去三女回女，去两女，二〇二年六月六编程得到五对夫妻过河最优情况仿照文献中已有的方法求解夫妻过河问题二〇二年六月六日星期三参考文献付艳玲，刘高峰，张伟商人渡河问题解的存在性及算法实现工程数学学报邵建峰，许丙胜商人渡河问题的算法实现数学的实践与认识温鸿航，温鸿翔，任晓莉渡河问题的图解分析电子科技温鸿航，任晓莉，温鸿翔渡河问题的矩阵表示与迭代算法电子科技达瓦，加央种种渡河同题及其算法科教文汇俞涛船运狼羊菜问题的新解法河北师范大学学报自然科学版善强，雷鸣数学模型第二版重庆大学出版社，姜启源，谢金星，叶俊数学模型第三版北京高等教育出版社李天瑞安全渡河问题的计算机求解和模拟工科数学武建林商人渡河游戏的解题算法电脑编程技巧与维护张念发，张宪新，刘长征基于状态空间搜索法的商人过河问题解决方案电脑编程技巧与维护刘卫国程序设计教程第二版北京中国水利水电出版社赵静，但琦数学建模与数学实验第三版北京高等教育出版社张北辰，张建明状态转移问题的计算机模拟益阳师专学报俞哲明，樊艳芬利用数组解决农夫过河问题福建电脑陈义华状态转移问题的图论法建模甘肃工业大学学报二〇二年六月六日星期三附录五对夫妻过河程序判断个状态是否可行状态可行状态为，可行状态为开始状态结束状态第次移动三个人过去过去时人尽量多，去多回来时人尽量少移动次数指示第次移动是采用的是那种方式注意矩阵是否相等的判断二〇二年六月六日星期三，奇数次移动回退偶数次移动二〇二年六月六日星期三当移动状态可行，则保存移动情况且回来船上的人员状态不能和上次的情况完全样，否则就重复操作无意义了。继续移动下次移动选择从新开始回退验证程序输入丈夫数目输入妻子数目输入船的最大容量输入丈夫数目二〇二年六月六日星期三输入妻子数目输入船的最大容量，二〇二年六月六日星期三二〇二年六月六日星期三二〇二年六月六日星期三，没有找到可行路径,二〇二年六月六日星期三文件文件二〇二年六月六日星期三曲靖师范学院本科生毕业论文论文题目求解夫妻过河问题作者学号郭彩虹学院年级数学与信息科学学院级学科专业数学数学与应用数学指导教师郭昀完成日期年月日曲靖师范学院教务处二〇二年六月六日星期三摘要渡河问题始于公元世纪，至今它仍是个逻辑难题，许多数学建模教材上已经提到这个问题指的是有不同的对象或生物，他们其中些相互不共存，逐步地让小群体从河的岸到另岸，经过有限步后，该群体全部从岸达到另岸，并且要求没有任何损失在渡河问题的夫妻过河问题中我们发现状态转移问题有时不定有解，有时的解又不定有规律，本文对于夫妻过河问题利用图解法和编写程序求解对对夫妻过河是否有解，并推广到对夫妻与船的运载能力对于能否安全渡河时它们之间的关系。关键词多步决策数学模型渡河问题二〇二年六月六日星期三，二〇二年六月六日星期三引言文献综述国内外研究现状国内外研究现状评价问题提出模型假设符号说明重述对夫妻过河问题的解对夫妻过河的解对夫妻过河的解五对夫妻过河模型模型构成模型建立模型求解编程求解图解法,六对夫妻过河模型模型构成模型求解对夫妻过河情况求解验证总结与展望总结后续研究工作展望参考文献附录二〇二年六月六日星期三引言这是个古老的阿拉伯数学问题。有对夫妻要过河，船最多可载人，约束条件是根据阿拉伯法律，任女子不得在其丈夫不在场的情况下与其他男子在起，问此时这对夫妻能否过河如果是对夫妻过河，其他条件不变的情况下，夫妻能否过河就这问题我们发现状态转移问题有时不定有解，有时的解又不定有规律当对夫妻过河，其他条件不变的情况下，夫妻能否过河我们发现此问题是无解的，但是当我们改变条件船最多可载人时有解就其数学建模思想来说，般采用将该问题转化为个多步决策模型，模型求解的方法大多为图解法然而旦问题的条件例如丈夫妻子或者小船上每次渡河人数等发生变化，图解法求解犹如大海捞针,很难奏效因此计算机编程求解模型的方法就显得非常重要了该题求解编程的难点在于允许状态与决策这两个方面的处理与实现此问题中利用的多目标决策方法是从世纪年代中期发展起来的种决策分析方法决策分析是在系统规划设计和制造等阶段为解决当前或未来可能发生的问题，在若干可选的方案中选择和决定最佳方案的种分析过程在社会经济系统的研究控制过程中我们所面临的系统决策问题常常是多目标的，例如我们在研究生产过程的组织决策时，既要考虑生产系统的产量最大，又要使产品质量高，生产成本低等。这些目标之间相