本科毕业论文商人渡河问题图解法

1、曲靖师范学院毕业论文题 目： 商人渡河问题图解法 学 号： 2008111115 姓 名： 张斌 年 级： 2008级 学 院： 数学与信息科学学院 专 业： 数学与应用数学 指导教师： 孙丽萍（讲师） 完成日期： 2012年 4月 20 日 商人渡河问题的图解法摘要针对安全渡河这一问题，引入图解方法，提出了又一种新的图解法该方法将顶点设计为由 “小船”、“商人、“仆人”组成的三元组，组中的每个元素取值可为“此岸”、“船上”、“彼岸”然后将实际模型转换为图型结构，最后通过路径搜索获得问题的解本文就安全过河问题，采用多步决策建立了数学模型，求解得到商人们安全过河的方案。关键词：安全渡河问题；数学

2、建模；图型求解；Graphic Method on the Problems of Merchants Crossing RiverAbstractThis article introduces another new graphic method in bringing the diagram concerning the problems of merchants safe river crossing. This new method considers the vertex as the three-member group consisting of the boat, mercha

3、nts and servants. Three elements in the group can be valued as the shore, the ship and the opposite shore, then the actual model can be transformed as diagram structure. The result shows the answer through the means of Route Searching. This article focuses on the safe river crossing, established the

4、 mathematical model in using step analysing method, aimed at getting the best plan of crossing river.Keywords: the problem of safe river crossing; Mathematical modeling; Graphic method目 录1 引言12 图解法方法介绍13 问题重述13.1 问题描述13.2 问题分析23.3 渡河模型假设24 求解模型24.1 商人比仆人多时（mn）24.2 商人和仆人相同时（m=n）34.3 商人比仆人少时（mn）（1）、1商

5、人0仆人（可行）解答：省略.（2）、2商人0仆人（可行）解答：省略.（3）、3商人0仆人（可行）解答：省略.（4）、4商人0仆人（可行）解答：省略. . .（m）、m商人0仆人（可行）解答：省略.（m+1）、2商人1仆人（可行）解答：省略. . .（m+m-1）、m商人1仆人（可行）解答：省略. . . . .（）、m商人m-1仆人（可行）解答：省略.4.2 商人和仆人相同时（m=n）（1）、m=n=1时（可行）解答：省略.（2）、m=n=2时（可行）解答：省略.（3）、m=n=3时（可行）解答：转下一页（4）、m=n=4时（不可行）（5）、m=n=5时（不可行）（6）、m=n=6时不可行 一

6、直到m=n时不可行（m4时）4.3 商人比仆人少时（mn）（1）、0商人1仆人（可行）解答：省略.（2）、0商人2仆人（可行）解答：省略.（3）、0商人3仆人（可行）解答：省略. . .（n）、0商人n仆人（可行）解答：省略.（n+1）、1商人2仆人（不可行）解答：省略. . . （不可行）解答：省略.（n+n-1)、1商人n仆人（不可行）解答：省略.(n+n)、2商人3仆人（不可行）解答：省略. . . （不可行）解答：省略. . . . （不可行）解答：省略.()、n-1商人n仆人（不可行）解答：省略.5 启示图中所有路径构成此问题域的解空间因在算法可解问题在实践中并不一定是有解的，并且在

7、此过程很有可能出现解的无路可走或者走入错误的道路而导致花费的时候较大，因为求解此类问题的时间和空间消耗可能极大，当然，此问题所建立起来的图相对而言较为简单，获取该问题的最优解也就是在图中寻找一条从起点到终点的最短路径在图论中，已有非常完善的方法来求取图的最短路径问题，只要建立了问题的图解模型，求出所有解，就可以直接利用图解的相关算法，直接获取最优解，这也是用图论来解决一类决策问题的优势所在并求出全部解，然后在解通过对比各个解的优劣，然后得出最优解然而，对于复杂问题，这也使得很多采用非图论的数学模型来解决此问题的算法，在求取最优解时遇到很大的困难 6 评价及推广优点和缺点：多步决策不会出现遗漏可

8、能的过河方式，可以将其全部得出来且看起来直观易懂。模型的缺点也很明显，就是解决过程繁琐，且只能解决过河的人少时的过河方案，如果人多的话，这种方法显然不适合。 7 结束语 本文完全以图论的方法来分析和解决安全渡河问题，节点的设计确保了能全面地描述渡河时从此岸到彼岸的动态变迁过程，而非只关注某一岸的状态变迁本方法较为直观形象，易于理解，对于类似的问题，只需修改m和n即可求得结果如何运用图论来解决实际问题，是数学建模中经常要考虑的问题本文提供的解法通过对实际问题进行抽象、建立图结构、最后搜寻路径从而获取结果等几个过程来完成，该求解方法为如何运用图论来解决实际问题提供了方法借鉴将经典的商人过河问题进行

9、了更严格的讨论，在此基础上着重分析了安全渡河的状态，建立了满足问题需求的规则，从而得出了要求解问题的方案。同时图解法为获取分析解、一般解、所有解及最优解提供了方便附录C+程序（仅供参考）#include#include #include struct node /*建立一个类似栈的数据结构并且可以浏览每一个数据点*/ int x; int y; int state; struct node *next; ; typedef struct node state; typedef state *link; link PPointer1=NULL; link PPointer2=NULL; int

10、a1,b1; int a2,b2; /*栈中每个数据都分为0，1状态*/ void Push(int a,int b,int n) link newnode; newnode=(link)malloc(sizeof(state); newnode- x=a; newnode- y=b; newnode- state=n; newnode- next=NULL; if(PPointer1=NULL) PPointer1=newnode; PPointer2=newnode; else PPointer2- next=newnode; PPointer2=newnode; void Pop() /

11、*弹栈*/ link pointer; if(PPointer1=PPointer2) free(PPointer1); PPointer1=NULL; PPointer2=NULL; pointer=PPointer1; while(pointer- next!=PPointer2) pointer=pointer- next; free(PPointer2); PPointer2=pointer; PPointer2- next=NULL; int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/ link pointer; if(PPoint

12、er1=NULL) return 1; else pointer=PPointer1; while(pointer!=NULL) if(pointer- x=a&pointer- y=b&pointer- state=n) return 0; pointer=pointer- next; return 1; int judge(int a,int b,int c,int d,int n) /*判断这个状态是否可行，其中使用了history函数*/ if(history(a,b,n)=0) return 0; if(a=0&b=0&a=3&b=0&d=0&c=3&d=b) Push(a,b,n)

13、; return 1; else return 0; else return 0; int Duhe(int a,int b,int n) /*递归法解决商人渡河问题，如果这一个状态符合*/ /*则判断下一个状态，直至问题解决*/ if(a=0&b=0) return 1; if(n=0) /*判断0状态时，商匪状态是否符合要求*/ if(judge(a-1,b-1,4-a,4-b,1) if(Duhe(a-1,b-1,1)=1) return 1; if(judge(a,b-2,3-a,5-b,1) if(Duhe(a,b-2,1)=1) return 1; if(judge(a-2,b,5

14、-a,3-b,1) if(Duhe(a-2,b,1)=1) return 1; if(judge(a-1,b,4-a,3-b,1) if(Duhe(a-1,b,1)=1) return 1; if(judge(a,b-1,3-a,4-b,1) if(Duhe(a,b-1,1)=1) return 1; else Pop(); return 0; if(n=1) /*判断0状态时，商匪状态是否符合要求*/ if(judge(a+1,b+1,2-a,2-b,0) if(Duhe(a+1,b+1,0)=1) return 1; if(judge(a,b+2,3-a,1-b,0) if(Duhe(a,

15、b+2,0)=1) return 1; if(judge(a+2,b,1-a,3-b,0) if(Duhe(a+2,b,0)=1) return 1; if(judge(a+1,b,2-a,3-b,0) if(Duhe(a+1,b,0)=1) return 1; if(judge(a,b+1,3-a,2-b,0) if(Duhe(a,b+1,0)=1) return 1; else Pop(); return 0; return 0; main() link pointer; Push(3,3,0); Duhe(3,3,0); pointer=PPointer1; while(pointer!

16、=NULL) printf( %d,%d-%dn ,pointer- x,pointer- y,pointer- state); pointer=pointer- next; getch(); 参考文献1姜启源，谢金星，叶俊数学模型M3版北京：高等教育出版社，2003 2白其峥.数学建模案例分析 M海洋出版社.20003数模竞赛赛题解析与论文点评选编 M赫孝良等选编.西安交通大学出版社，20024俞涛“船运狼、羊、菜”问题的新解法J河北师范大学学报：自然科学版，1996，20(4)-2729 5李天瑞安全渡河问题的计算机求解和模拟J工科数学，1999，15：119123 6薛毅，常金刚，程维虎

17、数学建模基础M北京：北京工业大学出版社，2004 7阮晓清，周义仓数学建模引论M北京：高等教育出版社，2005 8康立山，谢云，尤矢勇，等非数值并行算法模拟退火算法M北京：科学出版社，2003 9严慰敏吴伟民数据结构M北京：清华大学出版社，200210百度文库 用C语言处理商人过河 :/ baidu （仅对附录参考）致谢值此毕业论文设计完稿之际，首先向我的指导老师孙丽萍讲师表示衷心感谢！在我整个论文阶段，孙丽萍老师在百忙中抽出足够的时间来给予了我们悉心的关怀和耐心的指导，并提供了很好的学习、研究的环境和机会。孙丽萍老师平日里工作繁多，但在我做毕业论文设计的整个过程中都给予了我悉心的指导。除了敬