资源描述：
《商人过河问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、商人过河问题摘要本文就商人们如何能够安全过河问题,采用多步决策建立了数学模型，求解得到商人们安全过河的方案。将经典的商人过河问题进行了更广的讨论，在此基础上着重分析了安全渡河的状态空间，建立了满足问题需求的规则，从而得出了要求解问题的方案。模型主要通过穷举的方法对各种过河的方案进行一一列举，然后根据小船的容量和商人们要安全渡河为前提对各种方案进行层层筛选。最终，得到商人安全渡河的方案。最后本文就此问题进行推广，当有名商人名随从且小船的容量为时，将会得到几种解决方案给出了说明。关键词：穷举法多步决策图解法商人过河状态空间一、问题重述三名商人各带一名
2、随从过河，随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.但乘船渡河的方案由商人决定.现在需要解决的问题如下：1.13名商人在不被随从谋杀和小船最多能容2人的情况下，商人们将如何安全过河?1.2如果有名商人名随从，小船的容量为时，商人们又将如何安全过河？二、模型的假设2.1假设过河的过程中不会发生意外事故。2.2假设当随从人数多过商人时，不会改变杀人越货计划。2.3假设所有人最终都必须到达河对岸。三、符号说明表示商人的数量表示随从的数量表示河的此岸和彼岸表示小船的容量表示此岸的商人数量表示此岸随从的数量表示彼岸的商人数量表示彼岸的随
3、从数量四、模型分析本题针对商人们能否安全过河问题，需要选择一种合理的过河方案。对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案。对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对允许的状态量的层层筛选，从而得到过河的目标。五、模型建立与求解5.1模型的建立本题为多步决策模型，每一次过河都是状态量的转移过程。可以用三维向量表示（）的取值范围:{0,1,2,3}的取值范围:{0,1,2,3}那么允许状态量（即两岸同时必须满足
4、（））可以表示为（1）当=0或3,={0,1,2,3}，（2）当=1或2，=或用三维向量表示允许状态量如下表格1：表（1）过河安全状态量（3,3,1）（3,2,1）（3,1,1）（2,2,1）（3,0,1）（0,3,1）（0,2,1）（1,1,1）（0,1,1）（3,2,0）（3,1,0）（2,2,0）（3,0,0）（0,3,0）（0,2,0）（1,1,0）（0,1，0）（0,0,0）5.2模型的求解模型的要求从（3,3,1）开始经过对每次过河的安全状态量的选择最终安全到达（0,0,0）。根据题意状态转移必须满足以下规则;（1）从1变0或0变1交
5、替进行。（2）从1变为0即从河的此岸到彼岸，此案的人数减少1或2；即时，两岸的人数满足且，且或。（3）从0变为1时，即从河的彼岸到此案，则此案的人数增加1或2；即时，两岸的人数满足，，或。（4）对重复出现过的状态不计入安全状态，如（3,3,1）（3,2,0）（3,3,1）按照以上的规则方法可得到整个过河过程的状态量可表示为如下图：从（3,3,1）对每步出现的状态量进行层层选取安全状态量，最终得到所有的答案最终我们得到商人们安全渡河的方案有四种如下第一种方案第二种方案第三种方案第四种方案六、模型的评价及推广模型的优点和缺点：多步决策不会出现遗漏可能
6、的过河方式，可以将其全部得出来且看起来直观易懂。模型的缺点也很明显，就是解决是复杂繁琐，且只能解决过河的人少时的过河方案，如果人多的话，这种方法显然不适合。模型的推广：这个模型还可以解决名商人带名随从过河的问题。要解决名商人带随从过河的方案就见（程序二）。七、参考文献7格式不正确.1张念发文献格式不正确张宪新刘长征《电脑编程技巧与维护》2010第18期7.2储理才《大学数学》2005第3期附录一functionjueche=guohe%%%%%%%%%%%程序开始需要知道商人和仆人数；n=input(‘输入商人数目:’,’12’);nn=inpu
7、t(‘输入仆人数目:’,’12’);nnn=input(‘输入船的最大容量:’,’20’);ifnn>nn=input(‘输入商人数目:’,’23’);nn=input(‘输入仆人数目:’,’23’);nnn=input(‘输入船的最大容量:’,’34’);end%%%%%%%%%%%%%%%%决策生成jc=1;%决策向量放在矩阵d中，jc为插入新元素的行标初始为1；fori=0:nnnforj=0:nnnif(i+j<=nnn)&(i+j>0)%满足条D={(u,v)
8、1<=u+v<=nnn,u,v=0,1,2}d(jc,1:3)=[i,j，1
9、]；%生成一个决策向量立刻扩充为三维；d(jc+1,1:3)=[-i,-j,-1];%同时生成他的负向量；jc=jc+2;%由于生成两个
