商仆过河问题

2018-06-17 23:54:14来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

1.问题的提出

3名商人各带1个随从乘船渡河,一只小船只能容纳2人,由他们自己划行。在河的任何一岸当随从的人数多于商人数时,商人就会有危险。但是如何乘船渡河的大权掌握在商人们手中,商人们怎样才能安全渡河呢?

这就是著名的商仆渡河问题,对于这类智力游戏经过一番逻辑思索是可以找出解决办法的。这里要求将问题推广至商仆对数任意、船只容量也任意的一般情况下,建立数学模型,并编程求解。

2.模型建立与符号说明

记商仆对数为m,船容量为c人。

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

将二维向量sk=(xk,yk)定义为状态,安全渡河条件下的状态集合定义为允许状态空间,记做S

clip_image001

不难验证,S对此岸和彼岸都是安全的。

记第k次渡船上的商人数为uk,随从数为vk,将二维向量dk=(uk,vk)定义为决策dk,允许决策集合记作D,由小船的容量可知

因为k为奇数时船从此岸驶向彼岸,k为偶数时船由彼岸驶回此岸,所以状态sk随决策dk变化的规律称状态转移律。

这样,制定安全渡河方案归结为如下的多步决策模型:

求决策

clip_image002clip_image003

使状态,按照转移律(3),由初始状态

clip_image004

经过有限步n到达终止状态

clip_image005

 

详细问题描述见下图:

 

 

这里采用BFS算法(广度优先搜索算法)编程求解商仆过河问题。BFS算法是最经典的图搜索算法之一,在本题中可以保证找到的解为最短路径,即所求方案过河总步数最少,其算法描述如下:

建立一个状态队列q,这是一个先进先出的队列。

(1)将起始状态即(n,n)点加入队列q,标记(n,n)点为已访问。

(2)将q的首节点出队,再将所有该节点可达的未被访问的允许状态加入队列q

(3)将所有新加入的状态标记为已访问,如果其中有终止状态(0,0),则问题有解,算法结束。

(4)如果队列q为空,则问题无解,算法结束。

(5)转至(2)执行

分析:

观察BFS算法的执行过程,算法首先将距离起始状态为1次状态转移的所有状态加入队列,如果其中没有终止状态,则继续将所有距离起始状态为2次状态转移的状态加入队列……

由于队列是先进先出的,可以始终保证所需状态转移步数最少的状态排在队列的最前部,并首先由他们扩展下一层状态。

所以加入队列的每个状态都是以最短路径(最少的状态转移步数)到达的,因为如果有更短的路径存在,则此路径上的状态一定会被更早扩展,更早加入状态队列(所需步数少的状态排在状态队列的前部)。

当终止状态加入队列时,到达终止状态的路径也是最短路径,即求得一个所需状态转移步数最少的过河方案。

若某时刻状态队列为空且始终未到达终止状态,则说明所有自起始状态可达的节点均已被访问,且其中没有终止状态,即终止状态不可达,问题无解。

该问题商仆对数和船容量之间的关系与问题是否有解的分析:

商仆对数

小船容量

123

2

45

3

6

4

代码:

#include <bits/stdc++.h>
#include "windows.h"
#define MAX_SIZE 1010
using namespace std;

struct CNode
{
    int x;//x坐标
    int y;//y坐标
    int flag;//是否可以行走的点
    int dir;//标记行船方向
    CNode *p;//父节点指针
};
CNode G[MAX_SIZE][MAX_SIZE][2];//状态空间 坐标,访问
int V[MAX_SIZE][MAX_SIZE][2]; //访问标记
deque <CNode> q;//搜索队列
int num;//商仆对数
int cap;//船容量
bool solve;//解标记
int steps;//步数

void Init();//初始化
void BFS();//BFS搜索
void Output(CNode *p);//输出

int main(){
    Init();//进行初始化
    while(!q.empty()&&!solve){//BFS搜索
        BFS();
    }
    if(!solve)
        cout<<"\n问题无解\n";
    else{
        cout<<"\n过河方案:\n";
        Output(&G[0][0][1]);//回朔法输出
        cout<<"最少需要"<<steps<<"步\n";
    }
    return 0;
}

void Init(){
    cout<<"共有商仆对数:";
    cin>>num;
    cout<<"船容量:";
    cin>>cap;
    int i,j;
    for(int i = 0 ; i <= num ; i++){
        for(int j = 0 ; j <= num ; j++){//初始化状态空间
            G[i][j][0].x = G[i][j][1].x = i;//坐标x
            G[i][j][0].y = G[i][j][1].y = j;//坐标y
            G[i][j][0].flag = G[i][j][1].flag = 0;//均初始化为不可行点为0
            G[i][j][0].p = G[i][j][1].p = NULL;//结点
            G[i][j][0].dir = -1;//行船方向左或者下
            G[i][j][1].dir = 1;//行船方向右或者上
            V[i][j][0] = V[i][j][1] = 0;//未访问
        }
    }
    for( i = 0 ; i <= num ; i++){//将可行点标记为1
        G[0][i][0].flag = G[num][i][0].flag = G[i][i][0].flag = 1;
        G[0][i][1].flag = G[num][i][1].flag = G[i][i][1].flag = 1;
    }
    G[num][num][0].flag = G[num][num][1].flag = 0 ;//右上角为初始状态设置为0
    solve = false;//标记问题有解与否
    q.push_back(G[num][num][0]);//初始点进人队列
    steps = 0;//记录下最少的渡河次数
}

void BFS(){
    int x,y;//队首所在坐标
    int dx,dy;//变化坐标
    int nx,ny;//行船后坐标
    int dir;//行船方向
    if(q.empty()||solve)//搜索队列为空或者有解,退出搜索
        return;
    x=q.front().x;//取出队首坐标
    y=q.front().y;
    dir=q.front().dir;
    q.pop_front();//队首出队

    for(dx = 0 ; dx <= cap ; dx++){
        for(dy = 0 ; dy <= cap - dx; dy++){//枚举所有可能的状态
            nx = x + dx * dir;
            ny = y + dy * dir;

            if(nx < 0 || nx > num || ny < 0 || ny > num )//坐标越界
                continue;
            if(G[nx][ny][0].flag == 0)//达到不可行点
                continue;
            if(dx == 0 && dy == 0)//坐标没变化
                continue;
            if(dir > 0 && V[nx][ny][1] == 1)//该点被访问过
                continue;
            if(dir < 0 && V[nx][ny][0] == 1)//该点被访问过
                continue;
            if(dir>0){//放入队列
                G[nx][ny][0].p = &G[x][y][1];
                q.push_back(G[nx][ny][0]);
            }
            else{//放入队列
                G[nx][ny][1].p = &G[x][y][0];
                q.push_back(G[nx][ny][1]);
            }
            if(dir>0)//标记被访问
                V[nx][ny][1] = 1;
            else
                V[nx][ny][0] = 1;
            if(nx == 0 && ny == 0){//达到终点
                solve = true;
                return;
            }
        }
    }
}

void Output(CNode *p){//回溯法输出遍历结果
    if(p -> p == NULL){
        cout<<"("<<p->x<<","<<p->y<<")\n";
        return;
    }
    Output(p->p);
    cout<<"("<<p->x<<","<<p->y<<")\n";
    steps++;
}

/*
- - - - - - - - - - - - - - - - - -
3对
*  *
** *
*  *
4对
*    *
*  * *
**   *
*    *
5对
*     *
*    **
*  *  *
**    *
*     *
6对
*      *
*     **
*    * *
*  *   *
**     *
*      *
n对 图形为 N
*/

运行截图:

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:POJ 3126 Prime Path 简单广搜(BFS)

下一篇:pixel art之 hqx 算法