商仆过河问题--数学建模
商仆过河问题
作者：*学院 **班 *** ********** **号
2014年12月4日
摘要：为了求解3个商人和3个随从的过河问题，用数学分析方法，建立
数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机编程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。
关键词：多步决策 计算机求解 状态转移律 图解法 MATLAB程序
一、问题的提出
S 个商人各带一个随从乘船过河，一只小船只能容纳K 人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？
二、问题的关键
解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。
三、问题的分析
在安全的前提下(两岸的随从数不比商人多), 经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
四、 模型假设
记第k 次过河前A 岸的商人数为X K ，随从数为Y K k=1，2，⋯ X K ,Y K =0，1，2，3，将二维向量S K =(XK ，Y K ) 定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S 。则
S={(XK ,Y K )|(XK =0,YK =0,1,2,3),(XK =3,YK =0,1,2,3),(XK =YK =1)(XK =YK =2)} 记第k 次过河船上的商人数为U K ，随从数为V K
将二维向量D K =(UK ,V K ) 定义为决策．由小船的容量可知允许决策集合（记作D) 为 D={(UK ,V K )|UK +VK =l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}
五、模型建立：
动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
用动态规划法分析三名商人的过河问题。可得如下的递归树：
（转下页）
（注解：当K 为奇数时，船在B 岸；当K 为偶数时，船在A 岸。）
通过分析该递归树，知道求解关键在于正确地写出基本的状态转移关系式和恰当的边界条件。
因为k 为奇数时，船是从A 岸驶向B 岸，k 为偶数时。船是由B 岸驶回A 岸。所以状态S K 随决策D K 变化的规律是
S K+1=SK +(-1)K D K ，k=l，2，⋯，
称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题： 每一步，船由A 岸驶向B 岸或B 岸驶回A 岸，都要对船上的人员(商人U K ，随从V K 各几人) 作出决策，在保证安全的前提下即两岸的商人数X K 都不比随从数Y K 少，用有限步使人员全部过河．用状态(变量)S K 表示某一岸的人员状况，决策(变量)D K 表示船上的人员状况，可以找出状态S K 随决策D K 变化的规律．这样安全过河问题就转化为：
求决策D K ∈D(k=1,2，……，n) ，使得状态S K ∈S ，按照状态转移律，由初始状态S 1=(3，3) ，经有限步n 到达状态S K+1=(O,O)。
模型建立：
SK+1=SK+(-1)KDK，k=l,2，3，其中DK ∈D={(UK ,VK)|UK +VK=l，2}，{其中SK ∈(XK ,YK)|(XK=0，YK =1，2，3) ；(XK =3，YK=0,1,2,3);(XK =YK =1,2)},Sn+1 =(0,0)
这就是三个商人的过河问题模型。
六、模型求解：
穷举法：计算机编程（见附）
先建立编程的基本过程，然后考虑模型，再编写程序。 然后就可以得出结果了。
主程序流程图
图解法：状态s=(x,y) 16个格点
允许状态 10个●点
允许决策 移动1或2格; k奇, 左下移;
k 偶, 右上移.
1
n +1
总共需要11步
可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。
八、 模型的检验
用2名商人和2名随从的过河问题的解决思路，检验3名商人和3名随从的过河问题。
九、 模型的拓展和延伸
通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计m 名商人和n 名随从的过河问题。
十、总结
这是通过数学分析的方法解决实用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n 个商人的问题。
学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题，很多都需要数学。沉浸在数学的世界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。
参考文献：
（1）傅清祥．《数据结构与算法》．王晓东．北京：电子工业出版社 1998． （2）姜启瑟．《数学建模》(第二版) ．北京：高等教育出版社，2000．
（3）运筹学教材编写组．《运筹学》(修订版) ．北京：清华大学出版社。2001．
附：商仆过河的C 程序及运行截屏:
#include using namespace std; struct Node { int nMer; int nSer; int length; };
class A {
public: A(); ~A(); void 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);//添加STEP[head]可以向后延伸的节点 bool noRepeat(int nm,int ns);//没有重复返回TRUE void funshow(int a[][2],int ntail); bool funLeft(Node nd,int b1,int b2,int n); void show(int s[],int p[][2],int &top,int &count,int a[]); int head;
int n; //商仆的对数 int nB; //船最多的载人数目 Node *STEP; };
A::~A() { free(STEP); }
A::A() { cout>n; if(n==1) { nB=2;
cout>nB; } else if(n==3) { cout
cout>nB; } else if(n==4) { cout
cout
cout>nB; } else if(n>=5&&n
cout>nB; } else if(n100) { cout
int main() {
cout
void A::show(int s[],int p[][2],int &top,int &count,int a[]) { if(top == -1)
B: C: E: D:
return ;
//已找到目标状态需，输出数据 if(top == STEP[head].length) { cout
//在中间加入节点STEP[(s[top + 1])]
if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == true)//符合条件 { top++; p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; } else //不符合条件 { s[top + 1]--; if(STEP[(s[top + 1])].length == top)//退过了，到了下一层 { s[top + 1] = a[top + 1]; s[top]--; if(STEP[(s[top])].length != top)//退过了，到了下一层 {
for(int i = top; i
s[i] = a[i];
top--;
if(top == -1)
return ;
goto D;
}
if(top == 0)
return ;
if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false) goto D;
p[top][0] = STEP[(s[top])].nMer;
p[top][1] = STEP[(s[top])].nSer;
show(s,p,top,count,a);
return ;
}
if(funLeft(STEP[(s[top + 1])],p[top][0],p[top][1],top) == false)
goto E;
top++;
p[top][0] = STEP[(s[top])].nMer;
p[top][1] = STEP[(s[top])].nSer;
show(s,p,top,count,a);
}
}
void A::doLeft(int nhead,int ntail,int nlength)
{
int a[1000];
int a1[1000];
int sp[1000][2];
bool flag = false;
memset(a,0xff,4000);
memset(a1,0xff,4000);
memset(sp,0xff,8000);
if(STEP[head].length%2 == 0)
flag = true;
while(STEP[head].length == nlength - 1)
{
funTspt(STEP[head].nMer,STEP[head].nSer,flag);
head++;
}
for(int i = 0; i
{
a[(STEP[i].length)] = i;
a1[(STEP[i].length)] = i;
}
sp[0][0] = sp[0][1] = n;
STEP[head].nMer = STEP[head].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)
&& 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
return true;
return false;
}
void A::Tspt()
{
Node *temp = new Node;
temp = NULL;
bool flag = false;
while(head
{
if(STEP[head].length%2 == 0)
flag = true;
else
flag = false;
temp = funTspt(STEP[head].nMer,STEP[head].nSer,flag);
if(NULL != temp)
break;
head++;
}
if(head > tail)
{
cout
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 = STEP[head].nMer; //可供运输的商人数
int tS = STEP[head].nSer; //可供运输的仆人数
if(flag == false) //向此岸运输
{
tM = n - STEP[head].nMer;
tS = n - STEP[head].nSer;
temp = -1;
}
for(int i = 0; i
{
for(int j = 0; j
if(i + j == 0)
continue;
int p = STEP[head].nMer - temp*i;
int q = STEP[head].nSer - temp*j;
if(islegal(p,q) == true && noRepeat(p,q) == true)
{
if(p == 0 && q == 0)
{
tail++;
STEP[tail].length = STEP[head].length + 1;
STEP[tail].nMer = p;
STEP[tail].nSer = q;
nd = (Node*)malloc(sizeof(Node));
nd->length = STEP[head].length + 1;
nd->nMer = head;
nd->nSer = tail;
return nd;
}
tail++;
STEP[tail].length = STEP[head].length + 1;
STEP[tail].nMer = p;
STEP[tail].nSer = q;
}
}
}
return nd;
}
bool A::noRepeat(int nm,int ns)
{
int j1 = 0;
if(STEP[head].length%2 == 0)
j1 = 1;
for(int i = j1; i
{
if(STEP[i].length%2 == j1 && nm == STEP[i].nMer && ns == STEP[i].nSer) return false;
}
return true;
}
bool A::islegal(int nm,int ns)
{ //商人数少于仆人数或者商人数为0
if((nm == 0) || (nm == n) || (nm == ns))
return true;
return false;
}
void A::funshow(int a[][2],int ntail)
{
cout
}cout