商人过河
摘要
本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。
对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。
但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用图解法和算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。
最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。
关键词渡河问题状态集合决策集合平面坐标 图解法 算法
一、问题提出
问题：三名商人各带一个随从过河，一只小船只能容纳两个人，随从们约定，只要在河的任何一岸，一旦随从人数多于商人人数就杀人越货，但是商人们知道了他们的约定，并且如何过河的大权掌握在商人们手中，商人们该采取怎样的策略才能安全过河呢？
二、问题分析
这个问题已经理想化了，所以我们无需对模型进行假设，该问题可以看作一个多步决策问题。
每一步，船由此岸划到彼岸或者由彼岸划回此岸，都要对船上的人员进行决策（此次渡河船上可以有几名商人和几名随从），在保证安全（两岸的随从都不比商人多）的前提下，在有限次的决策中使得所有人都到对岸去。
因此，我们要做的就是要确定每一步的决策，达到渡河的目标。
三、模型假设与建立
记第次过河前此岸的商人数为xk, 随从数为yk,k?1,2,?,m，xk,yk?0,1,2,3定义状态：将二维向量Sk?(xk,yk)定义为状态，将安全渡河状态下的状态集合定义为允许状态集合，记为
S?（|x?0,3; y?0, 1, 2, 3或x?1;y?0, 1或x?2;y?0, 1,2? ?x,y）记第次渡河船上的商人数为uk，随从数为vk.定义决策：将二维向量
dk?(uk,vk)定义为决策；允许决策集合记作：D??(u,v)|u+v?1,2?
因为小船容量为2，所以船上人员不能超过2，而且至少要有一个人划船，由此得到上式。
由我们定义的状态sk和决策dk，我们可以发现它们之间是存在联系的： 为奇数是表示船由此岸划向彼岸，为偶数时表示船由彼岸划回此岸 状态sk是随着决策dk变化的，规律为：Sk?1?Sk?(?1)kdk
我们把上式称为状态转移律，因此渡河方案可以抽象为如下的多步决策模型： 求决策dk?D(k?1,2,?,m), 使状态Sk?S按照转移率，初始状态S1??3,3?经有限m步后到达状态Sm?1?(0,0)。到这里，整个数学模型就已经非常清晰了，接
下来要做的就是求解模型得出结果。
四、模型求解
在这个模型的求解中，我将会使用两种方法，一种是数学图解法，用于解决和当前题目一样的规模比较小的问题，优点是比较简便，但是对于规模比较大的
问题就无能为力了，比如说有50个商人携带50个随从过河，第二种方法是通过计算机编程，使用程序来解决该问题，即使问题规模增大，我们也可以利用计算机强大的计算能力来解决。
4.1数学图解法
我们首先在 xoy平面坐标系中画出如下方格，方格中的点表示状态
s??x,y?
起始状态（下图绿色点）s1??3,3? , 终止状态（下图红色点）sn?1??0,0?