0%

【算法编程】过河问题

发表于 更新于
本文字数： 5.6k 阅读时长 ≈ 8 分钟

今天偶尔想到了过河问题。记得读小学六年级的时候第一次接触到这个问题—六个老虎过河问题(百度上有详细介绍，本文解决的是一个简单的问题，下一篇文章中将讨论该问题)，当时都是从逻辑思维的方法得到正确的解决方法。本文介绍了普遍适用该类问题的方法以及该方法的改进方法，下一篇文章将介绍问题的变型及解法。

向量法（人、狗、鸡、米过河问题）

问题描述：某人带狗、鸡、米用船来过河，只有人会划船(好像是废话，后面问题我们还会假设动物也会划船),另外至多还能载一物，当人不在时，狗要吃鸡(有人可能会质疑：狗吃鸡？，但是我看到的是狗和猫都吃小鸡)，鸡吃米。问人、狗、鸡、米怎么过河？

我们用一个向量来表示人、狗、鸡、米所处的状态，例如：(1 1 1 1)表示人、狗、鸡、米都在左岸，则对应的(0 0 0 0)表示人、狗、鸡、米都在右岸。这些向量我们称为状态向量，但是由于问题的条件限制，有些状态是允许的，而有些状态是不允许的，例如(0 1 1 1)表示人不在左岸，显然是不允许的。我们可以穷举出所有允许的状态：

​ (1 1 1 1) (0 0 0 0)

​ (1 1 1 0) (0 0 0 1)

​ (1 1 0 1) (0 0 1 0)

​ (1 0 1 1) (0 1 0 0)

​ (1 0 1 0) (0 1 0 1)

从上面的允许状态中，我们可以发现规律如下：

当人在时（也就是第一位为1时），不能有相邻的0，例如(1 1 0 0)是不允许的

当人不在时(也就是第一个为0时)，不能有相邻的1 ，例如(0 1 1 0)是不允许的

我们将船的一次运载也用向量表示，例如(1 1 0 0)表示人和狗在船上。由于只有人会划船，则允许的运算向量为：

​ (1 1 0 0) (1 0 1 0) (1 0 0 1) (1 0 0 0)

因此我们可以将一次过河过程看成是一个状态向量与一个运算向量的异或运算（模2加运算：1+1=0 1+0=1 0+0=0）。根据上述的向量法的描述，我们可以将问题简化成：将状态(1 1 1 1)经过奇数次与运算向量运算，变成状态为(0 0 0 0)的状态转移过程。下面是过河的图解过程：

​ 开始状态 船上状态 结果状态

1 (1 1 1 1) ———> (1 0 1 0) ———> (0 1 0 1)

2 (0 1 0 1) ———> (1 0 0 0) ———> (1 1 0 1)

3 (1 1 0 1) ———> (1 0 0 1) ———> (0 1 0 0)

4 (0 1 0 0) ———> (1 0 1 0) ———> (1 1 1 0)

5 (1 1 1 0) ———> (1 1 0 0) ———> (0 0 1 0)

6 (0 0 1 0) ———> (1 0 0 0) ———> (1 0 1 0)

7 (1 0 1 0) ———> (1 0 1 0) ———> (0 0 0 0)

奇数次：去河对岸

偶数次：回河这边

注意事项：

在第3次过河时，开始状态为(1 1 0 1)，如果船上状态为(1 1 0 0),则结果状态为(0 0 0 1)，然后经过船上状态(1 0 0 1),结果状态为(1 0 0 0),然后经过船上状态(1 0 0 0)，就可以完成任务(总共5次过河)。但是这里存在问题：当开始状态为(0 0 0 1)，船上状态不可能为(1 0 0 1)。因为开始状态(0 0 0 1)表示只有米在左岸，船上状态(1 0 0 1)表示人和米在船上，这是不可能的！因此船上状态的选择是有限制的。奇数时，开始状态为1的位置，船上对应位置才可以为1；偶数时，开始状态为0的位置，船上对应的位置才可以为0.通俗的说：奇数时，是将有的东西运到河对岸，偶数时，是将河对岸的东西(河这边没有)运到河这边。这些数学的表述可能太麻烦，我举例说明：奇数时，当河这边只有人、狗、米，我们可以从选择人、狗上船或则人、米上船，而不能选择人、鸡上船（鸡在对岸）;当偶数次数时，河这边是狗、河对岸则是人、鸡、米，我们可以人、鸡或则人、米回到河这边，而不能选择人、狗过河。

算法实现：

上面的实现可用matlab或则c来实现。若用matlab来实现，则那些状态向量以及状态间的异或运算比较容易表示；若用c来实现，则用时较短。两者的难点在于注意事项中的船上变量的选取问题。因此这种方法不适合用计算机实现，在状态变量较少的情况下，我们可以直接用手工进行运算的方法来得到结果(大家可以试试)。

改进型算法—-图论法

算法思路：将10个状态向量用10个点表示，将这10个状态向量分别与可行的运算向量进行运算，如果结果向量仍为允许的状态向量，则两者间连一条线，从而构成了一个图的问题。我们的目标是找到一条可以从状态(1 1 1 1)到状态(0 0 0 0)的通路。下面是我运算得到的图:

图1

注意：图中的标号用于表示对应的状态

具体算法实现如下：

1、Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#define M 20//边数
#define N 10//顶点数
#define MAX 10000
void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) ;
int flag[N]={0};
int flag1=0;
int flag2=0;
typedef struct
{
    int startvex;
    int endvex;
    int length;
}edge;//边的结构体
edge T[M];
void main()
{
    int dist[N][N]={{0,MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX},//图的邻接矩阵
                    {MAX,0,MAX,MAX,MAX,MAX,1,1,MAX,MAX},
                    {MAX,MAX,0,MAX,MAX,1,1,MAX,1,MAX},
                    {MAX,MAX,MAX,0,MAX,MAX,MAX,1,1,MAX},
                    {MAX,MAX,MAX,MAX,0,MAX,MAX,1,MAX,1},
                    {1,MAX,1,MAX,MAX,0,MAX,MAX,MAX,MAX},
                    {MAX,1,1,MAX,MAX,MAX,0,MAX,MAX,MAX},
                    {MAX,1,MAX,1,1,MAX,MAX,0,MAX,MAX},
                    {MAX,MAX,1,1,MAX,MAX,MAX,MAX,0,MAX},
                    {MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX,0}
    };
    int D[N]={0};
    int p[N]={0};
    int s[N]={0};
    int num=0;
    Dijkstra(0,dist,D, p,s) ;//0表示从状态(1111)开始
}
 void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) 
 {     int i, j, k, v1, min, max=10000, pre;     /* Max中的值用以表示dist矩阵中的值*/
    v1=v; 
    for( i=0; i<N; i++)              /* 各数组进行初始化*/
    {    D[i]=dist[v1][i]; 
        if( D[i] != MAX )  p[i]= v1+1; 
        else p[i]=0; 
        s[i]=0; 
    }
    s[v1]=1;                          /* 将源点送U */
      for( i=0; i<N-1; i++)      /* 求源点到其余顶点的最短距离*/
    {    min=10001;    /* min>max, 以保证值为的顶点也能加入U */
        for( j=0; j<N-1; j++)
              if ( ( !s[j] )&&(D[j]<min) ) /* 找出到源点具有最短距离的边*/
                  {min=D[j]; 
                        k=j; 
                     }
                s[k]=1;  /* 将找到的顶点k送入U */    
    for(j=0; j<N; j++)
     if ( (!s[j])&&(D[j]>D[k]+dist[k][j]) ) /* 调整V－U中各顶点的距离值*/
        {D[j]=D[k]+dist[k][j]; 
        p[j]=k+1;                      /* k是j的前趋*/
                }
            }                               /*  所有顶点已扩充到U中*/
            for( i=0; i<N; i++)
            {
                printf(" %d : %d ", D[i], i);
                pre=p[i]; 
            while ((pre!=0)&&(pre!=v+1))
            {    printf ("<- %d ", pre-1); 
                pre=p[pre-1]; 
            }
            printf("<-%d \n", v); 
        }
}

结果显示如下：

图2

从上图的第七行可知，从标号为1的状态到标号为10的状态所要经过的过程为(数组下标是从0开始的)：

1—-6—-3—-7—-2—-8—-5—-10

2、通过每对顶点之间的最短路径算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h>
#define N 10 //顶点个数
#define MAX 10000
void Floyd(int dist[N][N],int A[N][N],int path[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
            {
                /*if(A[i][j]>(A[i][k]+dist[k][j]))//方法一：计算每一次矩阵
                {
                    A[i][j]=(A[i][k]+dist[k][j]);
                    path[i][j]=path[k][j];
                }*/
                if(A[i][j]>(A[i][k]+A[k][j]))//方法二:计算的幂次矩阵
                {
                    A[i][j]=(A[i][k]+A[k][j]);
                    path[i][j]=path[k][j];
                }
            }
}
void main()
{
    int dist[N][N]={{0,MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX},//图的邻接矩阵
                    {MAX,0,MAX,MAX,MAX,MAX,1,1,MAX,MAX},
                    {MAX,MAX,0,MAX,MAX,1,1,MAX,1,MAX},
                    {MAX,MAX,MAX,0,MAX,MAX,MAX,1,1,MAX},
                    {MAX,MAX,MAX,MAX,0,MAX,MAX,1,MAX,1},
                    {1,MAX,1,MAX,MAX,0,MAX,MAX,MAX,MAX},
                    {MAX,1,1,MAX,MAX,MAX,0,MAX,MAX,MAX},
                    {MAX,1,MAX,1,1,MAX,MAX,0,MAX,MAX},
                    {MAX,MAX,1,1,MAX,MAX,MAX,MAX,0,MAX},
                    {MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX,0}
    };
    int A[N][N];
    int path[N][N]={0};//给出两顶点间的路径
    int pre=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            A[i][j]=dist[i][j];
            if(dist[i][j]!=MAX)
                path[i][j]=i+1;
            else
                path[i][j]=0;
        }
    
    for(int k=0;k<7;k++)//若用方法一，需循环N-3次，若用方法二，需要循环lg(N-1)次
        Floyd(dist,A,path);
    printf("每对顶点间的最短路径矩阵为：\n");
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
            printf("%d ",A[i][j]);
        printf("\n");
    }
    printf("\n每对顶点的具体最短路径为：\n");
    
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            printf("%d: %d ",A[i][j],j+1);
        pre=path[i][j];
        while((pre!=0)&&(pre!=i+1))
        {
            printf("<- %d ",pre);
            pre=path[i][pre-1];
        }
        printf(" <- %d\n",i+1);
        }
    }
}

结果显示如下：

图3

从上图的最短路径矩阵的第一行第10列可知，从状态1到状态10需要7步，从具体最短路径的第10行可知，所要经过的过程为：

1—-6—-3—-7—-2—-8—-5—-10

两种方法求得的结果相同，我们可以用图形象的表示如下：

图4

通过对比可以发现，图论法实质是在向量法的基础上进行改进的算法，无论是在手动计算还是计算机实现上都比向量法更好。

坚持原创技术分享，您的支持将鼓励我继续创作！