GroupBlog

问题描述

三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由于他们自己划行，随从密约，在和的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何安排乘船的大权安排在商人们的手中，商人们怎样才能安全渡河？

模型假设

我们需要对问题做一些假设：
1. 每个商人和随从都会划船
2. 只有一条船，且每条船上最多只能乘坐两个人
3. 所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象
4. 船在渡河的过程中不受外界环境的影响

模型构造

记第 k 次过河前此岸的商人数为 xk , 随从数为 yk , k = 1, 2, 3…, xk ,yk = 0, 1, 2, 3

定义状态：将二维向量 sk = ( xk , yk ) 定义为状态

将安全渡河状态下的状态集合定义为允许状态集合，记为

S = {(x,y) | x=0,y=0,1,2,3; x=y=1; x=y=2; x=3,y=0,1,2,3}
记第 k 次渡河船上的商人数为 uk ，随从数为 vk

定义决策：将二维向量 dk = (uk , vk) 定义为决策

允许决策集合记作

D = {(u,v) | 1 ≤ u+v ≤ 2, u,v = 0,1,2}
因为小船容量为2，所以船上人员不能超过2，而且至少要有一个人划船，由此得到上式。

由我们定义的状态 sk 和决策 dk ，我们可以发现它们之间是存在联系的：

k 为奇数是表示船由此岸划向彼岸，k 为偶数时表示船由彼岸划回此岸

状态 sk 是随着决策 dk 变化的，规律为：

sk+1 = sk + (-1)kdk
我们把上式称为状态转移律，因此渡河方案可以抽象为如下的多步决策模型：

求决策 dk ∈ D(k = 1,2,…,n) , 使状态 sk ∈ S 按照转移率，初始状态 s1 = (3,3) 经有限步 n 到达状态 sn+1 = (0,0)

到这里，整个数学模型就已经非常清晰了，接下来要做的就是求解模型得出结果。

模型求解

使用dfs就可以，网上找的大牛的C++代码，感觉自己水平还是太菜的
https://www.bbsmax.com/A/Gkz1XLbNdR/

#include <cstdio>
#define maxn 101
int num;//number of bus or fol
int graph[maxn*maxn][maxn*maxn];
int state[maxn][maxn];

//when cross river
int c_bus[5] = {2, 1, 0, 1, 0};
int c_fol[5] = {0, 1, 2, 0, 1};
int b_step[maxn*maxn];
int f_step[maxn*maxn];

bool flag = false;
void DFS(int bus, int fol, int step, int dir)
{
    b_step[step] = bus, f_step[step] = fol;
    if(bus == 0 && fol == 0)
    {
        for(int i = 0; i <= step; i++)
        {
            printf("(%d,%d)", b_step[i], f_step[i]);
            if(i != step )
                printf(" -> ");
        }
        printf("\n");
        flag = true;
    }
    int fa = bus * ( num + 1 ) + fol;
    for(int i = 0; i < 5; i++)
    {
        if(dir)
        {
            int b_next = bus - c_bus[i], f_next = fol - c_fol[i];
            if(b_next >= 0 && b_next < num+1 && f_next >= 0 && f_next < num + 1 && state[b_next][f_next])
            {
                int son = b_next * ( num + 1 ) + f_next;
                if(!graph[fa][son] && !graph[son][fa])
                {
                    graph[fa][son] = 1;
                    graph[son][fa] = 1;
                    DFS(b_next, f_next, step + 1, !dir);
                    graph[fa][son] = 0;
                    graph[fa][son] = 0;
                }
            }
        }
        else
        {
            int b_next = bus + c_bus[i], f_next = fol + c_fol[i];
            if(b_next >= 0 && b_next < num + 1 && f_next >= 0 && f_next < num + 1 && state[b_next][f_next])
            {
                int son = b_next * ( num + 1) + f_next;
                if(!graph[fa][son] && !graph[son][fa])
                {
                    graph[fa][son] = 1;
                    graph[son][fa] = 1;
                    DFS(b_next, f_next, step + 1, !dir);
                    graph[fa][son] = 0;
                    graph[fa][son] = 0;
                }
            }
        }
    }
}
int main()
{
    printf("Please input the number of the businessman: ");
    scanf("%d",&num);
    for(int i = 0; i < num + 1; i++)
    {
        state[i][0] = 1;
        state[i][num] = 1;
        state[i][i] = 1;
    }
    DFS(num, num, 0, 1);
    if(!flag)
        printf("they can't cross the river.");
}