1、曲靖师范学院毕业论文题目商人渡河问题图解法学号2008111115姓名年级2008级学院数学与信息科学学院专业数学与应用数学指导教师（讲师）完成日期2012年4月20日1商人渡河问题的图解法摘要针对安全渡河这一问题，引入图解方法，提出了又一种新的图解法该方法将顶点设计为由“小船”、“商人、“仆人”组成的三元组，组中的每个元素取值可为“此岸”、“船上”、“彼岸”然后将实际模型转换为图型结构，最后通过路径搜索获得问题的解本文就安全过河问题，采用多步决策建立了数学模型，求解得到商人们安全过河的方案。关键词安全渡河问题；数学建模；图型求解；GRAPHICMETHODONTHEPROBLEMSOFMER
2、CHANTSCROSSINGRIVER2ABSTRACTTHISARTICLEINTRODUCESANOTHERNEWGRAPHICMETHODINBRINGINGTHEDIAGRAMCONCERNINGTHEPROBLEMSOFMERCHANTSSAFERIVERCROSSINGTHISNEWMETHODCONSIDERSTHEVERTEXASTHE“THREEMEMBERGROUP“CONSISTINGOF“THEBOAT“,“MERCHANTS“AND“SERVANTS“THREEELEMENTSINTHEGROUPCANBEVALUEDAS“THESHORE“,“THESHIP“AND
3、“THEOPPOSITESHORE“,THENTHEACTUALMODELCANBETRANSFORMEDASDIAGRAMSTRUCTURETHERESULTSHOWSTHEANSWERTHROUGHTHEMEANSOFROUTESEARCHINGTHISARTICLEFOCUSESONTHESAFERIVERCROSSING,ESTABLISHEDTHEMATHEMATICALMODELINUSINGSTEPANALYSINGMETHOD,AIMEDATGETTINGTHEBESTPLANOFCROSSINGRIVERKEYWORDSTHEPROBLEMOFSAFERIVERCROSSIN
4、GMATHEMATICALMODELINGGRAPHICMETHOD目录31引言12图解法方法介绍13问题重述231问题描述232问题分析233渡河模型假设24求解模型241商人比仆人多时（MN）242商人和仆人相同时（MN）343商人比仆人少时（MN）（1）、1商人0仆人（可行）解答省略（2）、2商人0仆人（可行）解答省略（3）、3商人0仆人（可行）解答省略（4）、4商人0仆人（可行）解答省略3（M）、M商人0仆人（可行）解答省略（M1）、2商人1仆人（可行）解答省略（MM1）、M商人1仆人（可行）解答省略（21MM）（）、M商人M1仆人（可行）解答省略42商人和仆人相同时（MN）（1）、M
5、N1时（可行）解答省略（2）、MN2时（可行）解答省略（3）、MN3时（可行）解答转下一页43,23,30,10,10,10,03,1320,20,10,2010,233003,10,10,23,00,20,32,31,01,03,30,0无效去回，去回，回，无效，无效去去失败去3,20,10,13,20,20,12,21,01,12,11,11,21,22,02,12,31,00,121,1无效回转到下一页回无效去失败去失败去失败回去,232101,1011,133001,32,02,0，回，回，无效，失败去52,01,11,32,11,01,21,30,22,01,32,02,02,22,
6、02,01,31,120,22,03,13,10,21,12,22,01,12,21,1,失败去失败去失败回无效回无效回回去去回,01,21,02,10,20,13,00,30,13,00,10,23,21,11,12,22,10,11,22,00,21,3失败失败回无效去回转下一页去无效去失败去失败去1,20,12,12,11,01,3,00,10,3失败回失败回去60,10,13,20,20,13,10,00,23,30,30,23,00,11,21,13,22,10,11,03,21,11,01,00,12,22,31,1无效去回成功去无效回失败回无效去失败回去去0,03,32,12,0
7、1,2成功失败回7（4）、MN4时（不可行）4,34,40,10,10,10,03,41,01,04,40,20,03,21,11,22,40,12,04,44,20,20,00,24,34,10,1020,10,3无效去回失败去回失败去失败去去，回去2,32,02,13,31,01,13,40,10,12,44,32,01,02,00,14,41,1转到下一页失败去去失败回失败无效去回回0,03,31,13,1无效去84,30,20,14,10,10,3230,12,13,21,01,22,2,2,42,00,22,22,03,31,1114,22,04,10,34,20,10,2无效回无效
8、去，失败回失败回失败去回无效回，回回0,23,21,01,23,11,11,34,20,20,24,00,20,44,30,10,1无效去去无效回去无效回9（5）、MN5时（不可行）5,45,50,10,10,10,05,3540,20,10,2010,255005,30,10,25,20,20,34,51,01,05,50,0无效去回，去回，回，无效，无效去去失败去5,30,10,25,40,20,14,41,01,14,31,11,23,42,02,14,51,00,14,41,11,1无效回无效回无效去失败去失败去失败回去5410011,155003,52,02,0，回，回，无效，失败去
9、10（6）、MN6时不可行一直到MN时不可行（M4时）,1,0,10,10,10,0,210,20,10,2010,200,20,10,20,21,1,01,0,0,0MMMMMMMMMMMMMMMM无效去回，去回，回，无效，无效去去失败去,30,31,11,01,11,21,11,22,42,02,11,1,00,11,11,1101,1MMMMMMMMMMMMMM转到下一页无效去失败去失败去失败回，去回1011,1002,2,02,0MMMM，回，无效，失败去11,30,10,3,20,10,2,40,20,4,30,20,31,21,01,21,31,1,20,11,30,2,30,3M
10、MMMMMMMMMMMMMMM无效去无效回去转到下一页回失败去失去回2,10,12,12,0,22,02,21,22,01,02,21,21,11,11,2,22,00,2MMMMMMMMMMMM败失败回失败回失败去回无效回无效回,10,20,1MM无效回12M,10,10,M1M,10,10,M1M1,21,0M41,M2M,00,10,MM,2M,00,20,20,M20,MM,1M0,12,00,M1M,M30,3无效回无效去失败（因为）去去无效回去回去2,2M42,M2M1,11,1M41,M1M1,11,01,M1M2,12,02,M1M2,01,12,M失败（因为）失败（因为）去失
11、败去失败去失败去M,20,20,M2回43商人比仆人少时（MINCLUDEINCLUDESTRUCTNODE/建立一个类似栈的数据结构并且可以浏览每一个数据点/INTXINTYINTSTATESTRUCTNODENEXTTYPEDEFSTRUCTNODESTATETYPEDEFSTATELINKLINKPPOINTER1NULL15LINKPPOINTER2NULLINTA1,B1INTA2,B2/栈中每个数据都分为0，1状态/VOIDPUSHINTA,INTB,INTNLINKNEWNODENEWNODELINKMALLOCSIZEOFSTATENEWNODEXANEWNODEYBNEWNO
12、DESTATENNEWNODENEXTNULLIFPPOINTER1NULLPPOINTER1NEWNODEPPOINTER2NEWNODEELSEPPOINTER2NEXTNEWNODEPPOINTER2NEWNODEVOIDPOP/弹栈/LINKPOINTERIFPPOINTER1PPOINTER216FREEPPOINTER1PPOINTER1NULLPPOINTER2NULLPOINTERPPOINTER1WHILEPOINTERNEXTPPOINTER2POINTERPOINTERNEXTFREEPPOINTER2PPOINTER2POINTERPPOINTER2NEXTNULLIN
13、THISTORYINTA,INTB,INTN/比较输入的数据和栈中是否有重复的/LINKPOINTERIFPPOINTER1NULLRETURN1ELSEPOINTERPPOINTER1WHILEPOINTERNULLIFPOINTERXAPOINTERPOINTERNEXTRETURN117INTJUDGEINTA,INTB,INTC,INTD,INTN/判断这个状态是否可行，其中使用了HISTORY函数/IFHISTORYA,B,N0RETURN0IFA0RETURN1ELSERETURN0ELSERETURN0INTDUHEINTA,INTB,INTN/递归法解决商人渡河问题，如果这一个
14、状态符合/则判断下一个状态，直至问题解决/IFA019IFN0/判断0状态时，商匪状态是否符合要求/IFJUDGEA1,B1,4A,4B,1IFDUHEA1,B1,11RETURN1IFJUDGEA,B2,3A,5B,1IFDUHEA,B2,11RETURN1IFJUDGEA2,B,5A,3B,1IFDUHEA2,B,11RETURN1IFJUDGEA1,B,4A,3B,1IFDUHEA1,B,11RETURN1IFJUDGEA,B1,3A,4B,1IFDUHEA,B1,11RETURN1ELSE20POPRETURN0IFN1/判断0状态时，商匪状态是否符合要求/IFJUDGEA1,B1,2
15、A,2B,0IFDUHEA1,B1,01RETURN1IFJUDGEA,B2,3A,1B,0IFDUHEA,B2,01RETURN1IFJUDGEA2,B,1A,3B,0IFDUHEA2,B,01RETURN1IFJUDGEA1,B,2A,3B,0IFDUHEA1,B,01RETURN1IFJUDGEA,B1,3A,2B,0IFDUHEA,B1,0121RETURN1ELSEPOPRETURN0RETURN0MAINLINKPOINTERPUSH3,3,0DUHE3,3,0POINTERPPOINTER1WHILEPOINTERNULLPRINTF“D,DDN“,POINTERX,POINTE
16、RY,POINTERSTATEPOINTERPOINTERNEXTGETCH22参考文献1姜启源，谢金星，叶俊数学模型M3版北京高等教育出版社，20032白其峥数学建模案例分析M海洋出版社20003数模竞赛赛题解析与论文点评选编M赫孝良等选编西安交通大学出版社，20024俞涛“船运狼、羊、菜”问题的新解法J河北师范大学学报自然科学版，1996，20427295李天瑞安全渡河问题的计算机求解和模拟J工科数学，1999，151191236薛毅，常金刚，程维虎数学建模基础M北京北京工业大学出版社，20047阮晓清，周义仓数学建模引论M北京高等教育出版社，20058康立山，谢云，尤矢勇，等非数值并行算
17、法模拟退火算法M北京科学出版社，20039严慰敏吴伟民数据结构M北京清华大学出版社，200210百度文库用C语言处理商人过河网址HTTP/WWWBAIDUCOM（仅对附录参考）23致谢值此毕业论文设计完稿之际，首先向我的指导老师讲师表示衷心感谢在我整个论文阶段，老师在百忙中抽出足够的时间来给予了我们悉心的关怀和耐心的指导，并提供了很好的学习、研究的环境和机会。老师平日里工作繁多，但在我做毕业论文设计的整个过程中都给予了我悉心的指导。除了敬佩老师的专业水平外，他的治学严谨和科学研究的精神也是我永远学习的榜样，并将积极影响我今后的学习和工作。其次要感谢和我一起在老师手下做毕业论文设计的其他成员，文中的许多思想来源于平时与他们的交流和讨论。再次，我还要特别感谢我的父母和我的亲人们，在我学习期间，家人一直对我学习和生活等各方面无微不至的关心和支持，我的成长凝聚了他们的心血。最后要感谢大学四年来所有的老师，为我们打下坚实的专业基础知识；同时还要感谢所有的同学们，正是因为有了你们的支持和鼓励。此次毕业论文设计才会顺利完成。我最后在和你们说一声“谢谢您们”。
