1、根据题意，可以作出商人渡河初始状态的示意图：AB渡河目的：（选择岸为参考点）4.2 C+程序解决根据（1）（2）（3）式，通过利用matlab编写一段程序来求解多步决策问题是可行的，但是当商人和仆人数都不多的情况下还可以用平面坐标法解此模型更为方便。接下来，我们先用平面坐标法求解此模型，最后再使用计算机仿真，对求解的结果进行验证，并给予推广。4.2.1 C+程序代码/约束条件:岸上仆人数不能多于商人数#include using namespace std;struct Node int nMer; int nSer; int length;class Apublic: A（）; A（）; v
2、oid Tspt（）; /过河的动作 void doLeft（int nhead,int ntail,int nlength）;private: bool islegal（int nm,int ns）; /判断是否满足约束条件，满足为true Node *funTspt（int nm,int ns,bool flag）;/添加STEPhead可以向后延伸的节点 bool noRepeat（int nm,int ns）;/没有重复返回TRUE void funshow（int a2,int ntail）; bool funLeft（Node nd,int b1,int b2,int n）; vo
3、id show（int s,int p2,int &top,int &count,int a）; int head; int tail; int n; /商仆的对数 int nB; /船最多的载人数目 Node *STEP;A:A（） free（STEP）;A（） coutn; if（n=1） nB=2;船最多载人的数目K=nB; else if（n=2） cout船最多载人的数目可以取: for（int x=n;x=2*n;x+） cout=5&n=100） for（int x=4; else if（n100） 本程序仅在S=（0100）以内保证其正确性请重新输入商仆的对数S= goto F
4、; STEP = （Node *）malloc（sizeof（Node）*10000）; memset（STEP,0,sizeof（Node）*10000）; head = tail = 0; STEP0.nMer = STEP0.nSer = n;int main（）问题描述：13对商仆乘船渡河，在河的任意一岸，一旦仆人数多于商人数，商人就有危险船一次载多少人商人们才可以安全渡河 A a; a.Tspt（）; return 0;void A:show（int s,int p2,int &count,int a） if（top = -1） return ; /已找到目标状态需，输出数据 if（
5、top = STEPhead.length）* +count * funshow（p,top + 1）; B: top-; if（top = -1） return ;C: stop-; if（STEP（stop）.length != top）/退过了 stop = atop; goto B; if（funLeft（STEP（stop）,ptop - 10,ptop - 11,top - 1） = false） goto C; ptop0 = STEP（stop）.nMer; ptop1 = STEP（stop）.nSer; show（s,p,top,count,a）; /在中间加入节点STEP
6、（stop + 1） if（funLeft（STEP（stop + 1）,ptop0,ptop1,top） = true）/符合条件 top+; else /不符合条件E: stop + 1-; if（STEP（stop + 1）.length = top）/退过了，到了下一层 stop + 1 = atop + 1;D: stop-; if（STEP（stop）.length != top）/退过了，到了下一层 for（int i = top; i = STEPhead.length; i+） si = ai; top-; if（top = -1） return ; goto D; if（t
7、op = 0） return ; if（funLeft（STEP（stop）,ptop - 10,ptop - 11,top - 1） = false） ptop0 = STEP（stop）.nMer; ptop1 = STEP（stop）.nSer; show（s,p,top,count,a）; if（funLeft（STEP（stop + 1）,ptop0,ptop1,top） = false） goto E; doLeft（int nhead,int ntail,int nlength） int a1000; int a11000; int sp10002; bool flag = fa
8、lse; memset（a,0xff,4000）; memset（a1,0xff,4000）; memset（sp,0xff,8000）; if（STEPhead.length%2 = 0） flag = true; while（STEPhead.length = nlength - 1） funTspt（STEPhead.nMer,STEPhead.nSer,flag）; head+; for（int i = 0; head + 1; a（STEPi.length） = i; a1（STEPi.length） = i; sp00 = sp01 = n; STEPhead.nMer = STE
9、Phead.nSer = 0; int top = 0; int count = 0; show（a1,sp,top,count,a）;bool A:funLeft（Node nd,int b1,int b2,int n） bool flag = abs（nd.nMer - b1） + abs（nd.nSer - b2） 0; if（flag = false） return false; if（n%2 = 0 & b1 = nd.nMer & b2 = nd.nSer） return true; if（n%2 = 1 & b1 b2 return false;Tspt（） Node *temp
10、 = new Node; temp = NULL; while（head tail）此问题无解! exit（1）; doLeft（temp-nMer,temp-nSer,temp-length）;/temp-nMer表示head delete temp;Node* A:funTspt（int nm,int ns,bool flag）/flag = true 向对岸运输 Node *nd = NULL; int temp = 1; int tM = STEPhead.nMer; /可供运输的商人数 int tS = STEPhead.nSer; /可供运输的仆人数 if（flag = false
11、） /向此岸运输 tM = n - STEPhead.nMer; tS = n - STEPhead.nSer; temp = -1; tM + 1 & nB + 1; i+）/i表示运输的商人数 for（int j = 0; j length = STEPhead.length + 1;nMer = head;nSer = tail; return nd; tail+; STEPtail.length = STEPhead.length + 1; STEPtail.nMer = p; STEPtail.nSer = q; return nd;noRepeat（int nm,int ns） i
12、nt j1 = 0; j1 = 1; for（int i = j1; tail + 1; if（STEPi.length%2 = j1 & nm = STEPi.nMer & ns = STEPi.nSer） return false; return true;islegal（int nm,int ns） /商人数少于仆人数或者商人数为0 if（nm = 0） | （nm = n） | （nm = ns） funshow（int a2,int ntail） 商人数 仆人数 ntail;第i次 ai0 ai1 （abs（ai + 10 - ai0）, abs（ai + 11 - ai1） els
13、e if（i ! i%2 = 1） - （图1：4.2.2 运行结果显示图2：图3：从图中看出当商仆对数为13时候，船的容量为2时，此问题无解，即这种情况无法安全渡河。图4：从图中可以看出，当商仆为13对，船的容量为4人时，有解，即可以安全过河。图5：图6：图7：从图中可以看出，商仆对数为13，容量为426人的时候，均可以安全过河。当容量为4时并且有361种方式。通过计算机运行此c+程序，当题目中给定出任意数量的商人，仆人，以及规定出任意船的容量，都可以判断出“商人们能否安全渡河？”以及解决“如果能，那么安全渡河的方案是什么？”的问题。从而使这个模型更具有一定的推广价值。5 模型的评价与改进5
14、.1 模型的评价5.1.1 模型的优点（1）采用了较为成熟的数学理论建立模型，可行度比较高；（2）运用程序显示多个路径，比较直观；（3）模型的求解运用了强大的Microsoft Visual C+ 6.0软件，结果可信度高，便于推广；（4）通过C+程序，能判断出“当任意个商人任意个仆人船的容量任意时，商人能否安全渡河？”及解决了“如果能，那么渡河方案又是什么？”的问题，使得所建模型更加全面。5.1.2 模型的缺点（1）没有找到商人数仆人数及船的容量之间的数量关系；（2）没有考虑到实际生活中，在安全渡河的前提下，商人过河的优先级应高于随仆人。5.2 模型的改进基于以上求解模型用到的方法，我们明显
15、意识到了结果考虑到的不够全面。为此，我们编写的C+算法程序，通过相应程序求解前面模型得到最短路径的最优解。但同时当有多个解决方案时，能够将所有符合条件的情况逐一列出。综合以上的努力，我们与致力于研究出一套方案：即给出任意个商人与任意个仆人以及船的容量任意的时候，都可以给出安全渡河的方案；并且在给出商人数、仆人数、船的容量中任意两者，并要使其能够安全渡河情况下的第三者的取值范围，以及得到最优的渡河方案。由于水平有限，我们只能提出这个美好的想法，用某种方法能把在所有安全状态集合和决策集合中，搜索出所有可能的解，从而从其中找出最优的解。6 模型的推广“商人渡河”模型适合于解决很多问题，如“传教士与野蛮人渡河”，“印度夫妻渡河”等。这些问题本质上都是相同或相似的，由此可见这个趣味问题流传的广泛性。另外还有所谓“人狗鸡米过河”问题，也是颇有趣味的，人、狗、鸡、米均要过河，船需人划，而船上至多还可载一物，但若人不在时，狗会吃鸡，鸡会吃米，问如何设计安全过河方案。我们完全可以仿照商人渡河问题建立一个多步决策模型，将上述算法稍作修改，就可以得到它的解。这里就不再赘述了。另外，用一定容积的若干油瓶倒出一定量的油的问题也属此类问题。
