商人过河问题.ppt

摘要,本文就商人们如何能够安全过河问题, 采用多步决策建立了数学模型，求解得到商人们安全过河的方案将经典的商人过河问题进行了更广的讨论，在此基础上着重分析了安全渡河的状态空间，建立了满足问题需求的规则，从而得出了要求解问题的方案 　　　模型主要通过穷举的方法对各种过河的方案进行一一列举，然后根据小船的容量和商人们要安全渡河为前提对各种方案进行层层筛选最终，得到商人安全渡河的方案　　　最后本文就此问题进行推广，当有m名商人m名随从且小船的容量为k时，将会得到几种解决方案给出了说明关键词：穷举法 多步决策 图解法 商人过河 状态空间,问题的提出,三名商人各带一个随从乘船渡河现此岸有一小船只能容纳两人，由他们自己划行若在河的任一岸随从人数比商人多，他们就可能抢劫财物不过如何乘船渡河的大权由商人们掌握商人们怎样才能安全过河呢?,分 析,此类智力问题当然可以通过一番思考，拼凑出一个可行方案来    但是，我们现在希望能找到求解这类问题的规律性、建立数学模型，用以解决更为广泛的问题问题重述,三名商人各带一名随从过河，随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.但乘船渡河的方案由商人决定. 　　　现在需要解决的问题如下：　 1. 3名商人在不被随从谋杀和小船最多能容 2人的情况下，商人们将如何安全过河? 2.如果有m名商人n名随从，小船的容量为k时，商人们又将如何安全过河？,模型的假设,1. 假设过河的过程中不会发生意外事故。

　　　2. 假设当随从人数多过商人时，不会改变杀 人越货计划　　　3. 假设所有人最终都必须到达河对岸符号说明,M:表示商人的数量　　　N:表示随从的数量　　　Z:表示河的此岸和彼岸　　　K:表示小船的容量　　　m:表示此岸的商人数量　　　n:表示此岸随从的数量　　　u:表示彼岸的商人数量　　　v:表示彼岸的随从数量,模型分析,本题针对商人们能否安全过河问题，需要选择一种合理的过河方案对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对允许的状态量的层层筛选，从而得到过河的目标模型的建立,根据题意，可以作出商人渡河初始状态的示意图：,本题为多步决策模型，每一次过河都是状态量的转移过程可以用三维向量表示（m,n,Z）m的取值范围:{0,1,2,3}n的取值范围:{0,1,2,3}那么允许状态量（即两岸同时必须满足（m>=n））可以表示为当m=0或3, n={0,1,2,3}，当m=1或2,m=n或用三维向量表示允许状态量如下表格1：,,,,,,,,,,,,,,,,,,,,,,,,x,y,O,1,2,3,1,2,3,仆,仆,仆,商,商,商,d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,模型的求解,模型的要求从（3,3,1）开始经过对每次过河的安全状态量的选择最终安全到达（0,0,0）。

根据题意状态转移必须满足以下规则;（1）Z从1变0或0变1交替进行2）Z从1变为0即从河的此岸到彼岸，此案的人数减少1或2；即(m,n,1) → (u,v,0)时，两岸的人数满足m>=n且u>=v，且m+n-1=u+v 或m+n-2=u+v3） Z从0变为1时，即从河的彼岸到此案，则此案的人数增加1或2；即(u,v,0) → (m,n,1)时，两岸的人数满足m>=n ， u>=v ，m+n+1=u+v或m+n+2=u+v4）对重复出现过的状态不计入安全状态，如（3,3,1）→（3,2,0）→（3,3,1）,,,,,,按照以上规则，求解过程如下：,从(3，2，0)只能到达(3，3，1)/*不必考虑*/,从(3,3,1)出发,,,,(3,2,0),(3,1,0)如右图,(2,2,0),,,,,(3,3,1),(3,2,0),(3,1,0),(2,2,0),从(3,1,0)出发,,,(3,3,1) /*不必考虑*/,(3,2,1)/*可取*/,从(2,2,0)出发,,,(3,3,1) /*不必考虑*/,(3,2,1)/*可取*/,,,,最终我们得到商人们安全渡河的方案有四种如下第一种方案第二种方案第三种方案第四种方案,,此岸,彼岸,思考问题,?,,四名商人各带一个仆人乘船渡河，一只小船只能容纳二人，由他们自己划行。

仆人们密谋，在河的任意岸，一旦仆人的人数比商人多，就杀人越货商人们能否安全渡河呢,m名商人m个随从(m≥4)无法安全渡河,如m=4时的图(如下图)，当我们按照以下步骤进行到d7时就无法作不重复的转移，所以当m=4时商人无法安全过河模型的评价及优缺点,1.优点：（1）模型简单，切合实际，易于理解；（2）建立了合理、科学的状态转移的模型；（3）结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性；（4）使用图文结合的方法，使解题过程更加的清楚明了；（5）多步决策不会出现遗漏可能的过河方式，可以将其全部得出来且看起来直观易懂2.缺点： 复杂繁琐，且只能解决过河的人少时的过河方案，如果人多的话，这种方法显然不适合。