商人过河问题数学建模

问题描述

三名商人各带–个随从乘船渡河,一只小船只能容纳二人,由他们自己划行.随从们密约,在河的任一岸，一旦随从的人数比商人多,就杀人越货,商人们怎样才能安全渡河呢？

问题建模

考虑用深度优先搜索解决此问题，提前记录在船承载量为2时候，所有可行的移动状态，以及所有安全的商人和随从的数量情况，用变量同时在搜索的过程中记录答案，一旦找到左岸已经完全没有人的情况立刻结束搜索，输出方案

变量声明

Ans为记录步骤的数组

Move对于某次决策有哪些移动方法

Sav用于判断此时的状态是否安全

Boat 表示当前这一步船是过去还是回来

运行结果

    图片解释

共11步

• 1 两个随从过去
• 2 一个随从回来
• 3 再两个随从过去
• 4 一个随从回来
• 5 两个商人过去
• 6 一个随从和一个商人回来
• 7 两个商人过去
• 8 一个随从回来
• 9 两个随从过去
• 10 一个随从回来
• 11 最后两个随从过去

Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int Move[5][2]= {{0, 2}, {1, 1}, {2, 0}, {0, 1}, {1, 0}};//对于某次决策有哪些移动方法
 4 const bool Sav[4][4] = {{0, 0, 0, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 0, 0, 0}};//判断此时的状态是否安全
 5 int Ans[1001][2], step = 1;
 6 bool Boat[1001], flag;
 7 bool rep (int a, int b, bool flag) {//repeat函数，判断是否有重复状态 
 8     for(int i = 0; i < step; i ++) { 
 9         if(a == Ans[i][0] && b == Ans[i][1] && Boat[i] == flag) return 1;
10     }
11     return 0;
12 }
13 bool UnSave (int Tr, int Co, int flag) {
14     if (Tr < 0||Tr > 3||Co < 0||Co > 3|| Sav[Tr][Co] || rep(Tr, Co, flag)) return 1; 
15     return 0; 
16 }
17 //判断是否不安全的函数 
18 void dfs (int Trader, int Cortege) { //商人和随从 
19     if(!Trader && !Cortege) { //如果找到了方案立刻输出 
20         cout << step - 1 << endl; 
21         cout << "（左岸商人" << "," << "左岸随从)" <<" " << "（右岸商人" << "," << "右岸随从)" << endl; 
22         for (int i = 0;i < step; i++) { 
23             cout << "(" << Ans[i][0] << "," << Ans[i][1] << ") ";
24             cout << "(" << 3 - Ans[i][0] << "," << 3 - Ans[i][1] << ")" << endl;
25         }
26         exit(0); //找到答案，直接退出搜索 
27     }
28     else if (!flag) {
29         for (int i = 0; i <= 4; i ++) { 
30             Trader -= Move[i][0], Cortege -= Move[i][1];
31             if (UnSave(Trader, Cortege, flag)) { 
32                  Trader += Move[i][0], Cortege += Move[i][1]; 
33                 continue;
34             }
35             Ans[step][0] = Trader, Ans[step][1] = Cortege, Boat[step] = flag;
36             // 存储答案 
37             step ++, flag = (!flag);
38             dfs (Trader, Cortege);
39             flag = (!flag);
40             Trader += Move[i][0];
41             Cortege += Move[i][1];//回溯 
42             step --;
43         }         
44     }
45     //下面是划回去的状态，与上面同理 
46     else {
47         for (int i = 0;i <= 4;i ++) { 
48             Trader += Move[i][0];
49             Cortege += Move[i][1];
50             if (UnSave (Trader, Cortege, flag)) { 
51                 Trader -= Move[i][0], Cortege -= Move[i][1]; 
52                 continue;
53             }
54             Ans[step][0] = Trader, Ans[step][1] = Cortege, Boat[step] = flag;
55             step ++;
56             flag = (!flag);
57             dfs (Trader, Cortege);
58             flag = (!flag);
59             Trader -= Move[i][0];
60             Cortege -= Move[i][1];
61             step --;
62         }
63     }
64 }
65 int main() { 
66     Ans[0][0] = Ans[0][1] = 3, Boat[0] = 1;
67     dfs (3, 3);
68     return 0;
69 }