摘 要

商人过河问题是一个历史悠久的问题，问题起源于公元8世纪，随着时间的推移，渐渐的演变出许多不同的版本，如传教士和食人族难题，人狼羊菜问题，人狗鸡米过河问题等。把商人渡河问题看作一个多步决策的过程,每一次船由此岸驶向彼岸或者由彼岸驶回此岸 ,都要对船上的人员( 商人 ,随从各几人) 作出决策 ,对商人过河问题进行建模，通过建模过程将商人过河问题分解成一个多步决策的问题，对模型进行求解。

在求解过程中，我们运用不同的方法，例如图解法，试探回溯法，也可以用所学的图论的知识对于状态点进行赋权求解。在不同的方法中，有各自的特点，就像图想法的优点是清晰明确，而缺点同样也很明显，那就是只能求解简单的问题，一旦条件变复杂之后，用图解法进行求解非常的困难；图论所学的知识进行求解时，需要与矩阵的相关知识相融合，融合之后会使得工作量变小，减轻人力负担。

对问题进行建模求解，这个过程不仅可以对锻炼我们运用数学知识解决实际问题的能力，而且也可以对不同求解方法的优劣性有个更加明确的认知，最后分析一下商人过河问题在我们现实生活中的运用。

关键词：多步决策； 商人过河； 图解法；图论

Abstract

Businessmen crossing problem is a problem with a long history, originated in the 8th century AD.With the passage of time,it gradually evolved out of many different 

versions, such as the missionaries , cannibals problem, werewolf sheep food problem and dog chicken rice crossing problem. Businessmen crossing problem is regarded as a multistep decision process. When every ship by the shore toward the shore or from 

the other shore driving back to the shore, the ship's personnel (businessman, 

entourage, a few)make decisions modeling for merchants to cross the river, by the 

process of modeling the business people crossing  problem is decomposed into a 

multistep decision problem. Then,we can solve the  problem.

In the process of solving, we can use different methods, such as graphical method, heuristic backtracking method.At the same time ,the knowledge of graph theory can be used to solve the problem of the state point. In different ways, They have their own characteristics .For example the advantages of graphical method is clear,while the disadvantages are also obvious, which only can solve simple problems once the conditions are complicated. Graph theory need knowledge of matrix to solve graphical method, reducing the burden of human.

To modeling and solving the problem, this process can not only to exercise us 

using mathematical knowledge to solve practical problems, but also can have a more 

clear cognition in the advantages and disadvantages of different methods. Finally,we 

analyze the application of businessmen crossing problem in our real life.

Key words:Multi-step decision-making, Merchants across the river, Graphic method,Graph theory

目 录

摘要 I

Abstract II

1. 绪论 1

1.1 研究的目的和意义 1

1.2 国内外研究现状 1

1.3 主要研究内容 2

2. 多步决策问题 3

2.1 多步决策概述 3

2.2 一般多步决策问题 3

2.2.1 分配问题 3

2.2.2 生产与存储问题 4

2.2.3 排序问题 5

2.3 小结 7

3. 商人渡河问题 9

3.1 问题的提出 9

3.2 模型假设 9

3.3 符号说明 9

3.4 问题分析 9

3.5 问题求解 10

3.5.1 图解法求解商人过河问题 10

3.5.2 试探回溯法求解商人过河问题 13

3.5.3 图论法解决商人过河问题 14

3.6 n，m，k商人过河问题及matlab求解 16

3.7 小结 19

4. 总结和展望 21

参考文献 23

附 录 25

致 谢 29

1. 绪论

1.1 研究的目的和意义

商人过河问题最初是指三名商人各带一名随从乘船渡河，小船一个可以容纳两人，由他们划行，其中随从们密约，在河的任何一岸，一旦随从人数比商人人数多，那么他们就杀人越货，而如何渡河的分配权掌握在商人们手中，问商人们如何制定渡河方案，可以使他们自己安全渡河，而研究商人过河这个问题就是为了能够以此为突破点，找到解决这一类问题的方法，起到以点破面的效果。

商人渡河问题可以作为多步决策解决的生产生活问题的典范，在运筹学，智能算法，离散数学以及数学模型中都提到了商人过河问题，是非常好的建模题例，它的方法和建模思想既给我们提供了有效解决一般问题的转换方法，又提供给我们从现实对象转换为数学模型的过程。在日常生活中人们普遍遇到需要进行选择方案的行为，这也就是需要做出决策，一个复杂的决策问题一般同时包含有不止一个的矛盾目标，在多个相互矛盾目标中如何能够快速准确的做出最正确的决策，商人渡河问题的解决可以为做决策提供一种思路，在有多个矛盾目标时怎么进行选择。在以后面对这种问题时，可以轻松的进行求解，获得结果，减少运算量和决策所用的时间，让决策者花更少的时间，得到更大的经济效益。

1.2 国内外研究现状

在求解商人渡河问题提上，许多人都有不同的看法，下面整理了一部分人的求解方法，对于求解商人渡河问题储理才提出了一种方法，当有m名商人每人都带着自己的一名随从过河，过河的工具只有小船，小船至多容纳n人，其它条件和要求与前面所提到的一样不发生变化，建立多步决策问题模型同时给出了用数学软件MATHEMATICA进行计算决策的源代码，同时给出部分计算结果可以让我们进行总结，同时也可以顺着他的思路进行进一步的研究。Dehaene,S和Sigman.M将人们大脑做一个决定的过程转化为一个多步决策问题，从而构造了人的思维过程，对商人过河进行求解。对普通商人过河进行泛化讨论由张念发，张宪新和刘长征实现的，他们在原来的基础上重点分析了状态空间，在状态空间中给出满足要求的渡河规则，对于控制策略也做了与问题相关的研究，最后得到寻找最佳路径的搜索规则以及如何寻找最佳路径的搜索策略，提出基于状态空间搜索法的求解方案。林志鹏用递归树分析法，将十分抽象的应用步骤用动态规划法进行展示，然后利用丰富的计算机编程知识，进行了求解，并给出了程序，最终获得过河的完整过程。

1.3 主要研究内容

1. 对于什么是多步决策问题进行了解释，然后列举了一些一般性的多步决策问题，比如资源分配问题，实现资源利用最优化；生产和存储问题，实现经济效益效益最大化；背包问题，实现空间利用最大化，对于这些一般的多步决策问题的解决方案是利用动态规划法进行建模和求解。
2. 商人渡河问题同样也是多步决策问题，对于简单的商人渡河问题（3，3，2）即3名商人带3名随从，小船容量为2的渡河问题，进行详细的建模，然后运用直观清晰的图解法来进行求解，同时运用探索回溯法和图论的知识进行求解，并用matlab程序实现了求解过程。
3. 对商人渡河问题的条件做出了调整，变为（4，4，2）即4名商人带4名随从小船容量为2渡河时我们发现这个问题无解，那么我们再做出调整，将小船的容量由2变为3，然后我们发现问题有多种解，也就是有多种方法可以使商人安全的渡河。
4. 根据多次实验数据发现，当小船的容量为4及其以上时，在符合条件的情况下无论商人数和随从数怎么变化，最终商人都可以安全的过河，这一结论暂无能力证明。

2. 多步决策问题

2.1 多步决策概述

多步决策是指决策过程不能一次完成，而要逐步分化，对每一个阶段进行最优决策，最后获得一个全局最优方案的决策方法。在我们生活中，有许多问题都需要进行多步决策，大到工厂的生产调度，小到日常的出行，都要进行多步决策，只是我们平时没有注意到而已。生产调度问题主要是针对企业管理部门的，管理部门提出生产调度方案，而一个合格的调度方案应该是可以为企业带来最大的经济效益的，也就是说以经济效益为目标函数，通过多步决策，可以使的经济效益这个目标函数最优；我们的日常出行，要去几家在不同街道的商店，先去哪一家，然后去哪一家，这个顺序的抉择同样也是一个多步决策过程，前面选的一家商店会影响到后面你的选择，符合多步决策的条件，我们以花费时间最少为目标函数，通过多步决策，得出使我们费时最少的方案。

2.2 一般多步决策问题

2.2.1 分配问题

分配问题就是需要合理的给多个使用者分配有限的一种资源或者多种资源，使用者能够使用这些资源创造出最大的经济效益或者生产出最多的有效产品，总之是可以使目标函数达到最优。