多对商人过河数学建模.doc

多对商仆过河问题12对商人过河（算法中多少对可以改变，此为N=12的时候，稍加修改便可以成为你需要的对数解决方案）摘要本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。对于本题而言，在12名商人、12名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用 dijkstra算法 ，并利用Microsoft Visual C+ 6.0软件，编译运行程序得到了一种商人安全渡河的方案。但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了dijkstra算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。我们通过对程序的改善，使可以运行比较多的将符合条件的情况列出来。1 问题重述十二名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。在河的任意一岸，一旦随从的人数比商人多，商人就有危险但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢？同时，推广到M名商人带M名随从又如何？2 问题分析安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。3 模型假设及符号说明3.1 模型假设（1）每个商人和随从都会划船；（2）只有一条船，且每条船上最多只能乘坐两个人；（3）所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象；（4）船在渡河的过程中不受外界环境的影响。3.2 符号说明 初始状态下，商人和随从所在的一岸； 初始状态下，商人和随从欲到达的一岸；S 商仆对数K 船最多载人的数目4 模型的建立与求解4.1 模型的建立根据题意，可以作出商人渡河初始状态的示意图：渡河目的：（选择岸为参考点）4.2 C+程序解决根据（1）（2）（3）式，通过利用matlab编写一段程序来求解多步决策问题是可行的，但是当商人和随从数都不多的情况下还可以用平面坐标法解此模型更为方便。接下来，我们先用平面坐标法求解此模型，最后再使用计算机仿真，对求解的结果进行验证，并给予推广。4.2.1 C+程序代码/约束条件:岸上仆人不能多于商人数#include using namespace std;struct Nodeint nMer;int nSer;int length;class Apublic:A();A();void Tspt();/过河的动作void doLeft(int nhead,int ntail,int nlength);private:bool islegal(int nm,int ns); /判断是否满足约束条件，满足为trueNode *funTspt(int nm,int ns,bool flag);/添加STEPhead可以向后延伸的节点bool noRepeat(int nm,int ns);/没有重复返回TRUEvoid funshow(int a2,int ntail);bool funLeft(Node nd,int b1,int b2,int n);void 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:A()coutn;if(n=1)nB=2; cout船最多载人的数目K=nB;else if(n=2) cout船最多载人的数目可以取:;for(int x=n;x=2*n;x+)coutx、;coutendl;coutnB;else if(n=3) cout船最多载人的数目可以取:;for(int x=n-1;x=2*n;x+)coutx、; coutendl;coutnB;else if(n=4) cout船最多载人的数目可以取:;for(int x=n-1;x=2*n;x+)coutx、; coutendl;coutnB;else if(n=5&n=100) cout船最多载人的数目可以取:;for(int x=4;x=2*n;x+)coutx、; coutendl;coutnB;else if(n100) cout本程序仅在S=(0100)以内保证其正确性endl; cout请重新输入商仆的对数S=;goto F;STEP = (Node *)malloc(sizeof(Node)*10000);memset(STEP,0,sizeof(Node)*10000);head = tail = 0;STEP0.nMer = STEP0.nSer = n;int main() cout问题描述： S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？endl;A a;a.Tspt();return 0;void A:show(int s,int p2,int &top,int &count,int a)if(top = -1)return ;/已找到目标状态需，输出数据if(top = STEPhead.length)cout* +count *endl;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);return ;/在中间加入节点STEP(stop + 1) if(funLeft(STEP(stop + 1),ptop0,ptop1,top) = true)/符合条件top+;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;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(top = 0)return ;if(funLeft(STEP(stop),ptop - 10,ptop - 11,top - 1) = false)goto D;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;if(funLeft(STEP(stop + 1),ptop0,ptop1,top) = false)goto E;top+;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);void A:doLeft(int nhead,int ntail,int nlength)int a1000;int a11000;int sp10002;bool flag = false;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; i head + 1; i+)a(STEPi.length) = i;a1(STEPi.length) = i;sp00 = sp01 = n;STEPhead.nMer = STEPhead.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 = nd.nMer & b2 = nd.nSer)return true;return false;void A:Tspt()Node *temp = new Node;temp = NULL;bool flag = false;while(head tail) cout此问题无解!nMer,temp-nSer,temp-length);/temp-nMer表示headdelete 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)/向此岸运输tM = n - STEPhead.nMer;tS = n - STEPhead.nSer;temp = -1;for(int i = 0; i tM + 1 & i nB + 1; i+)/i表示运输的商人数for(int j = 0; j tS + 1 & j length = STEPhead.length + 1;nd-nMer = head;nd-nSer = tail;return nd;tail+;STEPtail.length = STEPhead.length + 1;STEPtail.nMer = p;STEPtail.nSer = q;return nd;bool A:noRepeat(int nm,int ns)int j1 = 0;if(STEPhead.length%2 = 0)j1 = 1;for(int i = j1; i tail + 1; i+)if(STEPi.length%2 = j1 & nm = STEPi.nMer & ns = STEPi.nSer)return false;return true;bool A:islegal(int nm,int ns)/商人数少于仆人数或者商人数为0if(nm = 0) | (nm = n) | (nm = ns)return true;return false;void A:funshow(int a2,int ntail)coutendl;cout 商人数 仆人数endl;for(int i = 0; i ntail; i+)cout第i次 ai0 ai1endl;if(i != ntail - 1 & i%2 = 0)cout (abs(ai + 10 - ai0),abs(ai + 11 - ai1)endl;else if(i != ntail - 1 & i%2 = 1)cout - (abs(ai + 10 - ai0),abs(ai + 11 - ai1)endl;coutendl;4.2.2 运行结果显示图1：从图中看出当商仆对数为12时候，船的容量为2时，此问题无解，即这种情况无法安全渡河。图2：从图中可以看出，当商仆为12对，船的容量为4人时，有解，即可以安全过河。扩展情况：图3：从图中可以看出，商仆对数为3，容量为2,3,4,5,6的时候，均可以安全过河。当容量为2时并且有4种方式。通过计算机运行此c+程序，当题目中给定出任意数量的商人，随从，以及规定出任意船的容量，都可以判断出“商人们能否安全渡河？”以及解决“如果能，那么安全渡河的方案是什么？”的问题。从而使这个模型更具有一定的推广价值。5 模型的评价与改进5.1 模型的评价5.1.1 模型的优点（1）采用了较为成熟的数学理论建立模型，可行度比较高；（2）运用程序显示多个路径，比较直观；（3）模型的求解运用了强大的Microsoft Visual C+ 6.0软件，结果可信度高，便于推广；（4）通过C+程序，能判断出“当任意个商人任意个随从船的容量任意时，商人能否安全渡河？”及解决了“如果能，