商人过河实验报告.doc

数学模型实验实验报告6学院： 工商学院 专 业： 电气二类（计算机） 姓 名： 辛文辉 尚磊 张亨 学号：_ 2012484019 2012484091 2012484055 _ 实验时间：_ 3.18 _ 实验地点： b3 一、实验项目：Matlab程序设计安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。二、实验目的和要求a. 了解Matlab程序设计有关基本操作b. 掌握有关程序结构三、实验内容允许的状态向量 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10允许的决策向量: 0 1 0 2 0 3 0 4 0 5 0 6 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 5 0 5 1 6 0 过河步骤：第1步：0商5仆过河，0商1仆返回第2步：5商1仆过河，1商1仆返回第3步：3商3仆过河，1商1仆返回第4步：3商3仆过河，1商1仆返回第5步：3商3仆过河，完成过河过程中状态变化：步骤 此岸商 此岸仆 方向 彼岸商 彼岸仆 1 11 6 = -8 -3 11 7 -3 -3 7 7 -1 -1 5 5 1 1 3 3 3 3对于经典的3对商仆、小船容量为2人时的问题，运行程序求得结果如下11对商仆，小船容量为6人时，运行程序求得结果如下：图 3 11对商仆、小船容量为6时的求解结果事实上，11对商仆时的状态空间如图：02468100246810 1111可行状态图 4 12对商仆时的状态空间显然的船容量必须至少保证状态转移能够沿对角线方向向下移动，问题才会有解。船容量为2时可以使状态转移沿对角线移动，但不能持续向下移动，船容量至少为4才可使状态能够沿对角线向下移动。下面说明何时需要状态空间沿对角线移动。当商仆对数为6时，状态空间为：图 5 6对商仆时的状态空间此时状态中心（3,3）距离边界状态（6,3）的距离为3，船容量至少为4才可避免状态转移沿对角线下行，而船容量为4已经是状态转移沿对角线移动的条件，即当商仆对数大于等于6时，船容量至少为4，问题有解。不难说明，当商仆对数为4或5时，所需的最小船容量为3。综上，使问题有解的商仆对数与船容量之间的关系如下：表 1 商仆对数与船容量的关系商仆对数小船容量1、2、324、5364从图中可以看出，商仆对数为3，容量为2,3,4,5,6的时候，均可以安全过河。当容量为2时并且有4种方式。通过计算机运行此c+程序，当题目中给定出任意数量的商人，随从，以及规定出任意船的容量，都可以判断出“商人们能否安全渡河？”以及解决“如果能，那么安全渡河的方案是什么？”的问题。从而使这个模型更具有一定的推广价值。附件n=input(输入商人数目: );m=input(输入仆人数目: );h=input(输入船的最大容量: );m0=0;n0=0;LS=0; % 允许的状态集合S与个数LSLD=0; % 允许的决策集合D与个数LDfor i=0:n for j=0:m if i=j&n-i=m-j|i=n|i=0 LS=LS+1;S(LS,:)=i j; end if i+j0&i+j=j|i=0) LD=LD+1;D(LD,:)=i j; end endend% 用搜寻法找出符合条件的渡河方案N=15;Q1=inf*ones(2*N,2*N);Q2=inf*ones(2*N,2*N);t=1;le=1;q=m n;f0=0; % 判断循环终止标记while f0=1&t1 % 对重复状态删除处理 f1=0; for ii=1:k-1 if s1=sa(ii,:) f1=1; break end end end if f1=0 sa(k,:)=s1; sb(k,:)=D(i,:); k=k+1; break end end end end end q=sa; le=size(q,1); Q1(1:le,t*2-1:t*2)=q; Q2(1:le,t*2-1:t*2)=sb; t=t+1;end% 在可行方案集合中逆向搜寻唯一方案tr=t-1;saa1=sa;SA=zeros(tr,2);SB=zeros(tr,2);for k=tr:-1:2 k1=k-1;f0=0; sbb=Q2(:,k*2-1:k*2); saa=Q1(:,k1*2-1:k1*2); for i=1:2*N saa2=saa1-(-1)k*sbb(i,:); for j=1:2*N if saa2=saa(j,:) saa1=saa2; sbb1=sbb(i,:); f0=1; break end end if f0=1 break end end SA(k1,:)=saa1; SB(k,:)=sbb1;end SA(tr,:)=m0 n0; SB(1,:)=m,n-SA(1,:);% 输出 SC = ones(size(SA)*3 - SA;nStep = ceil( size(SB,1) / 2 ); fprintf(n允许的状态向量:n); disp(S); fprintf(n允许的决策向量:n); disp(S); fprintf(n过河步骤：n); for i = 1 : nStep fprintf(第%i步：%i商%i仆过河, i, SB(