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

Forpersonaluseonlyinstudyandresearch;mercialuse葿袇重庆大学袅虿芈(商仆过河模型)羇开课课程:数学模型羂指导教师:黄光辉莁小组成员:庄楚斌(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)成功找出所有可能的情况,相对于网络上只能找出一种有效情况来说是个巨大的进步