商人过河问题.ppt

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