商人过河的数学模型及编程解决

14对商仆过河问题

题目

有14名商人各带一名仆人要过河，但船最多能载4人。商人已获得仆人的阴谋：在河的任意一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取货物。安排如何乘船的权利权利在商人手上，试为商人制定一个安全的过河方案。

一．摘要

n对商仆过河，一只船最多载m人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）。

二．问题提出：

有14对商仆乘船过河，一只船最多载4人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？

三．问题分析

商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。

四．模型假设与符号假设

（一）模型假设

商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。

（二）符号假设

设（x，y）是状态向量，表示任一岸的商人和仆人数，且x，y分别要大于等于0，小于等于M。

1.设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。

2.设用s表示所有的可取状态向量的集合。 3.设用d表示所有运载向量的集合。

4.设用 表示从此岸到彼岸，作减；用 表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（Sk属于s）；dk：表示第k步可取转移向量（dk属于d）；

五．模型的建立

我们以3名商人为例。

设第k次渡河前此岸的商人数为xk，随从数为yk，k=1，2，…，xk，yk =0，1，2，3，将二维向量Sk =（xk，yk）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为： S={（x，y）|x = 0或3，y = 0，1，2，3，x = y = 1，2} （1）

又设第k次渡船上的商人数为uk，随从数为vk，将二维向量 dk=（uk+ vk）定义为决策。则允许决策集合为：

D={（u，v）| u + v = 1，2} （2）

因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态Sk随着决策dk变化的规律即状态转移规律是：

Sk+1 = Sk +（- 1）k dk （3）

这样，制定安全渡河方案归结为如下的多步决策问题： 求决策dk ∈ D（k = 1，2，…，n），使状态Sk ∈ S按照规律（3），由初始状态S1=（3，3）经有限步（设为n）到达状态Sn+1=（0，0）。

六．模型的简化与求解

下面通过程序给出这个多步决策问题的一个解：

a[1]={0，0}；a[2]={0，1}；a[3]={0，2}；a[4]={0，3}； a[5]={3，0}；a[6]={3，1}；a[7]={3，2}；a[8]={3，3}； a[9]={1，1}；a[10]={2，2}； （*以上给出10个允许的状态*）

d[1]={0，2}；d[2]={2，0}；d[3]={1，1}；d[4]={0，1}； d[5]={1，0}； （*以上表示给出5个允许的决策*） i=1；j=1；k=1；s[0]=s[1]={3，3}； Print[″此岸————船上————对岸″]； Do[

Do[s[i+1]=s[i]+（-1）^i d[j]； t=0；

Do[If[s[i+1]= =a[k]，t=1]，{k，1，10}]； If[t= =0，Continue[ ]]；

（*以上是保证状态属于允许的状态*） l=Mod[i+1，2]；m=l；u=0； If[i+1> =3，

Do[If[s[i+1]= =s[m]，u=1，Break[ ]]，{m，l，i -1，2}] ]；

If[u= =0，c[i+1]=d[j]；Break[ ]] ，{j，1，5}]；

If[t= =0，Print[No，Result]；Break[ ]]； b[i+1]={3，3}-s[i+1]；

Print[s[i]，″- - - -″，c[i+1]，″- - - -″，b[i+1]]； If[s[i+1]= ={0，0}，Break[ ]] ，{i，1，12}] 程序运行结果如下：

此岸——————船上——————对岸 {3，3}——————{0，2}——————{0，2} {3，1}——————{0，1}——————{0，1} {3，2}——————{0，2}——————{0，3} {3，0}——————{0，1}——————{0，2} {3，1}——————{2，0}——————{2，2} {1，1}——————{1，1}——————{1，1}

{2，2}——————{2，0}——————{3，1} {0，2}——————{0，1}——————{3，0} {0，3}——————{0，2}——————{3，2} {0，1}——————{0，1}——————{3，1} {0，2}——————{0，2}——————{3，3}

可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。渡河的整个过程如下所示： 去2随从 回1随从 （3商人3随从）—————→（3商人1随从）—————→ 去2随从 回1随从 （3商人2随从）—————→（3商人0随从）—————→ 去2商人 回1商人1随从 （3商人1随从）—————→（1商人1随从）—————→ 去2商人 回1随从 （2商人2随从）—————→（0商人2随从）—————→ 去2随从 回1随从 （0商人3随从）—————→（0商人1随从）—————→ 去2随从

（0商人2随从）—————→（渡河成功）

七、结果分析与检验

八、模型的优缺点与改进方向

九、参考文献

【1】 茆诗松等 , 概率论与数理统计教程，北京：高等教育出版社,2004年。 【2】 赵静，但琦，数学建模与数学实验[3]，北京：高等教育出版社，2008年。

十、附录

（一）程序

//约束条件:岸上仆人不能多于商人数

#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 tail;

int n; //商仆的对数

int nB; //船最多的载人数目 Node *STEP; };

A::~A() {

free(STEP); }

A::A() {

cout<<\请输入商仆的对数:\ cin>>n;

cout<<\请输入船最多载人的数目:\ cin>>nB;

STEP = (Node *)malloc(sizeof(Node)*10000); memset(STEP,0,sizeof(Node)*10000);

head = tail = 0;

STEP[0].nMer = STEP[0].nSer = n; }

int main() {

A a;

a.Tspt();

return 0; }

void A::show(int s[],int p[][2],int &top,int &count,int a[]) {

if(top == -1) return ;

//已找到目标状态需，输出数据 if(top == STEP[head].length) {

cout<<\ \***********\

funshow(p,top + 1);

B: top--;

if(top == -1) return ; C: s[top]--;

if(STEP[(s[top])].length != top)//退过了 {

s[top] = a[top]; goto B; }

if(funLeft(STEP[(s[top])],p[top - 1][0],p[top - 1][1],top - 1) == false)

goto C;

p[top][0] = STEP[(s[top])].nMer; p[top][1] = STEP[(s[top])].nSer; show(s,p,top,count,a); return ; }

//在中间加入节点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 //不符合条件 {

E: s[top + 1]--;

if(STEP[(s[top + 1])].length == top)//退过了，到了下一层 {

本文来源：https://www.bwwdw.com/article/o9h2.html