商人过河matlab程序以及解析.docx

蒇蚅重庆大学蚂膂芈(商仆过河模型)螆开课课程:数学模型肄指导教师:黄光辉薁小组成员:庄楚斌(20134760)自动化07班羈张俊铭(20133227)材料加工01班螇吴慧(20131966)数学01班膃肁时间:2015年3月8日蝿薅薅蒀葿蚆蚄衿一、问题提出腿3名商人带3名随从乘一条小船过河,小船每次只能承载至多两人。随从们密约,在河的任一岸,一旦随从的人数比商人多,就***,商人们如何才能安全渡河呢?蚇螂二、问题分析薃 商人与随从过河问题可以视为是一个多步决策的过程,通过多次优化,从而得到一个全局最优的决策方案。决策的每一步,即船从此岸到达彼岸,都要对船上的商人和仆人数做出决策。在保证河的任一岸均有商人数比随从人数多和小船每次最多只能承载两人的前提下,经有限步使所有人员到达彼岸。羀蒅三、模型假设膄 商人和随从都会划船,天气很好,无大风大浪,且船的质量很好,可以保证很多次安全的运载商人和随从。羂蚀四、模型建立薆~第k次渡河前此岸的商人数,~第k次渡河前此岸的随从数芃,=0,1,2,3;k=1,2,……蒁=(,,ck)~过程的状态,其中,,ck分别表示对应时刻此岸的商人,仆人数以及船的行进方向,其中c取值1表示即将向彼岸运行,为0表示即将向此岸运行膆S~允许状态集合,S={(x,y)|x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}蚈~第k次渡船上的商人数蚅~第k次渡船上的随从数袁=(,)~决策,D={(u,v)|,,=0,1,2}~允许决策集合袇k=1,2,……蒅因为k为奇数时船从此岸驶向彼岸,k为偶数时船从彼岸驶向此岸,所以状态随决策的变化规律是螃=+~状态转移律芀求∈D(k=1,2,…n),使∈S,并按转移律由=(3,3,1)到达状态=(0,0,0(1))。蚇蒆袂螀莇薈芄腿膈莅莃袂袈莆螅节虿膄袃五、模型求解蚁本模型使用MATLAB软件编程,通过穷举法获得所有可能的决策方案如下(完整matlab程序详见附录):荿第一种:第二种:芅第三种:第四种:羂膀六、模型的推广腿该商人、随从过河模型可以完美解决此类商仆过河的决策问题,并且该模型还可推广至解决m个商人和n个随从过河,以及小船的最大载重人数改变时的问题,只需适当地改变相关的语句即可轻松实现模型的转换。芇如当商人数和随从数均为4,小船最大载重人数为2时,matlab程序运行的结果如下(程序改动详见附录):莄薀推广过程只需要将其中的(x,y)(限定范围)改成相对应的情况即可,例如,商人基于仆人数都为4时允许状态集合,S={(x,y)|x=0,y=0,1,2,3,4;x=4,y=0,1,2,3,4;x=y=1,2,3}袀肄蒂罿薀膅袅蚃肆芇总结羃本程序相对于网上各种结构体,堆栈形式的程序来说简单很多,没有用到那些高级的函数,简单易懂,肂核心要点:袇(1)就是巧妙地将z(a,b)加上了c变成(a,b,c),c用来判断此时船的行进方向,在后面判断是否有重复时非常重要,因为在船行进方向不同时,就算此岸人员分布一样也不是一种情况肄(2)就是设置了m数组,以便于在后面的穷举过程中,记录每一步所采用的决策方案,以防止后面重复或者遗漏肂(3)成功找出所有可能的情况,相对于网络上只能找出一种有效情况来说是个巨大的进步,这得益于其中while函数的使用,回溯思想的建立,以及每次找到成功的路线之后,在将路线输出之后,以未成功的方式继续穷举,向下运行到找到第二条成功路线以及更多的方案到所有的可能进程都被检验为止。薁薇肅蒄羁芈***薂莀附录肈Matlab源代码羄1、三个商人三个随从袅%——商人过河MATLAB程序,3商人,3仆人蝿%本程序相对于网上各种结构体,堆栈形式的程序来说简单很多,没有用到那些高级的函数,简单易懂螈%核心要点(1)就是巧妙地将z(a,b)加上了c变成(a,b,c),c用来判断此时船的行进方向,在后面判断是否有重复时非常重要,因为在船行进方向不同时,就算此岸人员分布一样也不是一种情况羆%核心要点(2)就是设置了m数组,以便于在后面的穷举过程中,记录每一步所采用的决策方案,以防止后面重复或者遗漏羃%核心要点(3)成功找出所有可能的情况,相对于网络上只能找出一种有效情况来说是个巨大的进步蒃蕿z=zeros(30,3);%z为由(a,b,c)的列向量组成的3行30列数组,初始化为0矩阵,a,b,c代表此刻此岸的商人,仆人数量以及船的运行状态,c=1表示即将向彼岸运行肇m=zeros(1,20);%m为一维行向量,初始化为1矩阵,用于在后面的程序中判断第k次选择的乘船方案膁d=[0,1,1;0,2,1;1,0,1;1,1,1;2,0,1];%共有5种可以选择的乘船方案,最后面一列全为1,即用于在后面表示使得z(k