商人过河实验报告

《商人过河实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数学模型实验—实验报告6学院：工商学院专业：电气二类（计算机）姓名：辛文辉尚磊张亨学号：___201248401920124840912012484055____实验时间：__3.18____实验地点：b3一、实验项目：Matlab程序设计安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律

2、。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。二、实验目的和要求a.了解Matlab程序设计有关基本操作b.掌握有关程序结构三、实验内容第9页/共9页允许的状态向量000102030405060708090100111122334455667788991010110111112第9页/共9页1131141151161171181191110允许的决策向量:010

3、203040506101120212230313233404142505160过河步骤：第1步：0商5仆过河，0商1仆返回第2步：5商1仆过河，1商1仆返回第3步：3商3仆过河，1商1仆返回第4步：3商3仆过河，1商1仆返回第5步：3商3仆过河，完成过河过程中状态变化：步骤此岸商此岸仆方向彼岸商彼岸仆1116==>-8-3第9页/共9页117<==-8-4266==>-3-377<==-4-4344==>-1-155<==-2-2422==>1133<==00500==>33对于经典的3对商仆、小船容量为2人时的问题，运行程序求得结

4、果如下11对商仆，小船容量为6人时，运行程序求得结果如下：第9页/共9页图311对商仆、小船容量为6时的求解结果事实上，11对商仆时的状态空间如图：024681002468101111可行状态图412对商仆时的状态空间显然的船容量必须至少保证状态转移能够沿对角线方向向下移动，问题才会有解。船容量为2时可以使状态转移沿对角线移动，但不能持续向下移动，船容量至少为4才可使状态能够沿对角线向下移动。第9页/共9页下面说明何时需要状态空间沿对角线移动。当商仆对数为6时，状态空间为：图56对商仆时的状态空间此时状态中心（3,3）距离边界状态（

5、6,3）的距离为3，船容量至少为4才可避免状态转移沿对角线下行，而船容量为4已经是状态转移沿对角线移动的条件，即当商仆对数大于等于6时，船容量至少为4，问题有解。不难说明，当商仆对数为4或5时，所需的最小船容量为3。综上，使问题有解的商仆对数与船容量之间的关系如下：表1商仆对数与船容量的关系商仆对数小船容量1、2、3≥24、5≥3≥6≥4从图中可以看出，商仆对数为3，容量为2,3,4,5,6的时候，均可以安全过河。当容量为2时并且有4种方式。通过计算机运行此c++程序，当题目中给定出任意数量的商人，随从，以及规定出任意船的容量，都可

6、以判断出“商人们能否安全渡河？”以及解决“如果能，那么安全渡河的方案是什么？”的问题。从而使这个模型更具有一定的推广价值。．附件n=input('输入商人数目:');m=input('输入仆人数目:');h=input('输入船的最大容量:');第9页/共9页m0=0;n0=0;LS=0;%允许的状态集合S与个数LSLD=0;%允许的决策集合D与个数LDfori=0:nforj=0:mifi>=j&n-i>=m-j

7、i==n

8、i==0LS=LS+1;S(LS,:)=[ij];endifi+j>0&i+j<=h&(i>=j

9、i==0)

10、LD=LD+1;D(LD,:)=[ij];endendend%用搜寻法找出符合条件的渡河方案N=15;Q1=inf*ones(2*N,2*N);Q2=inf*ones(2*N,2*N);t=1;le=1;q=[mn];f0=0;%判断循环终止标记whilef0~=1&t

11、a=[m0,n0];sb=D(i,:);f0=1;breakendforj=2:LS-1%搜索对比S后允许状态ifs1==S(j,:)ifk==1sa(k,:)=s1;sb(k,:)=D(i,:);k=k+1;breakendifk>