《商人过河问题.ppt

按照以上规则，求解过程如下： 思考问题 m名商人m个随从(m≥4)无法安全渡河,如m=4时的图(如下图)，当我们按照以下步骤进行到d7时就无法作不重复的转移，所以当m=4时商人无法安全过河。 商人过河问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 摘要 　　　本文就商人们如何能够安全过河问题, 采用多步决策建立了数学模型，求解得到商人们安全过河的方案。将经典的商人过河问题进行了更广的讨论，在此基础上着重分析了安全渡河的状态空间，建立了满足问题需求的规则，从而得出了要求解问题的方案。 　　　模型主要通过穷举的方法对各种过河的方案进行一一列举，然后根据小船的容量和商人们要安全渡河为前提对各种方案进行层层筛选。最终，得到商人安全渡河的方案。 　　　最后本文就此问题进行推广，当有m名商人m名随从且小船的容量为k时，将会得到几种解决方案给出了说明。 关键词：穷举法 多步决策 图解法 商人过河 状态空间 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 问题的提出 三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人，由他们自己划行。若在河的任一岸随从人数比商人多，他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能安全过河呢? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 分 析 此类智力问题当然可以通过一番思考，拼凑出一个可行方案来。????但是，我们现在希望能找到求解这类问题的规律性、建立数学模型，用以解决更为广泛的问题。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 问题重述 　　　 三名商人各带一名随从过河，随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.但乘船渡河的方案由商人决定. 　　　现在需要解决的问题如下： 　 1. 3名商人在不被随从谋杀和小船最多能容 2人的情况下，商人们将如何安全过河? 2.如果有m名商人n名随从，小船的容量为k时，商人们又将如何安全过河？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 模型的假设 　　　1. 假设过河的过程中不会发生意外事故。 　　　2. 假设当随从人数多过商人时，不会改变杀 人越货计划。 　　　3. 假设所有人最终都必须到达河对岸。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 符号说明 　　 M:表示商人的数量 　　　N:表示随从的数量 　　　Z:表示河的此岸和彼岸 　　　K:表示小船的容量 　　　m:表示此岸的商人数量 　　　n:表示此岸随从的数量 　　　u:表示彼岸的商人数量 　　　v:表示彼岸的随从数量 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 模型分析 　　　本题针对商人们能否安全过河问题，需要选择一种合理的过河方案。对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案。对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对