数据结构与算法学习笔记（3）——搜索

发表于   |   分类于   |  

本章讲一讲比较重要的搜索算法。

本文仅供个人记录和复习，不用于其他用途

问题引入

小学的时候我们可能做过这样一个题目：给你1-9的自然数，将它们组成三个三位数，使得其中两个数相加等于另外一个数，自然数可以重复使用。如果现在让我们编程实现这个问题，我们应该怎么做呢？不要急，让我们一步步地解决这个问题。

深度优先搜索

我们先来看看这样一个问题：写出123的全排列。什么是全排列？其实就是将各个位置的数进行交换，得到的所有可能的数。比如123的全排列就是123、132、213、231、312、321。那么，让我们用代码来实现这个全排列：

1
2
3
4
5
for(a = 1; a <= 3; a++)
    for(b = 1; b <= 3; b++)
        for(c = 1; c <= 3; c++)
            if(a != b && a != c && b != c)
                printf("%d%d%d\n", a, b, c);

至于1234的全排列，无非就是多加一层循环，再修改一下判断条件即可。不过呢，这样一来代码就显得较为臃肿。递归一章提到，所有的循环都可以用递归来表达，那么显然我们可以用递归来简化代码。

现在假设有3个盒子，代表着全排列中对应的百位、十位、个位，我们要做的就是将1、2、3放入三个盒子中。首先我们按照顺序，将1放入1号盒子，2放入2号盒子，3放入3号盒子，形成了123这个数。产生排列之后，我们将3取走，并且尝试着向3号盒子放入其他的数。当然，我们手中只有3，并没有其他的数，所以我们只能退回到2号盒子。来到2号盒子前，我们取回2，并且尝试着放入其他的数。很显然，我们可以放入3。放入3后，我们来到3号盒子，我们可以放入2，形成排列132。

按照刚刚的步骤进行模拟，就可以得到所有的排列，下面是这个过程的代码实现：

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
#include <stdio.h>
int sum = 1;
int n;
int book[10] = {0};  // 表示纸牌，0为没有打出，1为已经打出
int a[10] = {0};     // 表示盒子
void DepthFirstSearch(int step)
{
    int i;
    if(step == n + 1)  // 盒子越界
    {
        printf("第%d种排列：", sum++);
        for(i = 1; i <= n; i++)
            printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for(i = 1; i <= n; i++)  // 循环遍历每一张牌，尝试每一种可能
    {
        if(book[i] == 0)     // 表示第i张牌还没有打出去
        {
            a[step] = i;               // 将第i张牌放入第step个盒子
            book[i] = 1;               // 表示第i张牌已经打出去
            DepthFirstSearch(step + 1);  // 在这个排列的基础上进行下一个盒子的排列
            book[i] = 0;               // 在一种排列结束后需要马上将牌收回来
        }
    }
    return;
}
int main()
{
    printf("输入1-9的整数：");
    scanf("%d", &n);
    DepthFirstSearch(1);  // 从第一个盒子开始
}

比较关键的是数组a和b，a表示盒子中有没有数，b表示1-9这9个数有没有被使用。当达到第十个盒子时，我们就形成了一种全排列。八皇后问题和这个过程类似，将一层层的循环写进递归之中，简化了代码量。深度优先搜索之所以冠以深度的名字，那是因为这个算法讲究的是先往下探索，一直深入到无法深入后，再回退一步，探索这个深度的其他可能。然后一直回退，最后回到第一层。

广度优先搜索

现在有一位探险家降落在一个海岛上，他携带了一张地图，地图上标识了他的位置为(6, 8)。但是呢，他并不知道这个海岛的面积有多大。那么，如果让你来引导这位探险家，你会用什么样的方式来探索出海岛的面积？

这里就不得不介绍一下广度优先搜索。所谓的广度优先，指的是将同一深度探索完成后，才进入下一深度，与深度优先那种直达最深层的方式有所区别。我们的探险家降落在(6, 8)的位置，他能够走的方向有上下左右四个方向，因此，(6, 9)、(6, 7)、(5, 8)、(7, 8)就是属于同一深度，我们就先探索这四个位置。然后呢，这四个位置同样可以往四个方向移动，不过(6, 8)已经走过了，所以我们将它标记一下，以免重复探索，所以我们下一步要探索的一共有8个位置（记住，探索过的位置一定要标记）。如下图：

示例图

红色的为起始位置，黄色的是第一深度，绿色的是第二深度。广度优先搜索就是像这样展开，一直到碰到海水时结束。这样，我们就能够将整个海岛的面积计算出来。

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
#include <stdio.h>
struct note
{
    int x;
    int y;
};
int main()
{
    struct note que[2501];
    int head,tail;
    int i, j, k, n, m, startx, starty, p, q, sum, max=0, tx, ty;
    int a[51][51] = {0}, book[51][51] = {0};
    int next[4][2] = {
        {0,1},  // 向右走
        {1,0},
        {0,-1},
        {-1,0}
    };
    printf("输入长和宽：");
    scanf("%d%d", &n, &m);
    printf("输入地图：\n");
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    printf("输入起始位置：");
    scanf("%d%d", &startx, &starty);
    head = 1, tail = 1;
    que[tail].x = startx;
    que[tail].y = starty;
    sum = 1;
    tail++;
    book[startx][starty] = 1;
    while(head < tail)
    {
        for(k = 0; k <= 3; k++)
        {
            tx = que[head].x + next[k][0];
            ty = que[head].y + next[k][1];
            if(tx < 1 || tx > n || ty < 1 || ty > m)
                continue;
            if(a[tx][ty] > 0 && book[tx][ty] == 0)
            {
                book[tx][ty] = 1;
                que[tail].x = tx;
                que[tail].y = ty;
                tail++;
                sum++;
            }
        }
        head++;
    }
    printf("面积为%d", sum);
}

这里我们创建了一个结构体来存储坐标，另外呢，我们创建了一个结构体数组，代表一个队列，来存放需要搜索的位置。还需要注意的是，这里使用的next数组用于指示所走的方向。那么呢，我们按照顺时针的探索方式，先从右开始搜索。

下面这组数据可以用于验证代码正确与否，0代表海洋，1-9代表陆地：

1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

如果你的答案是38，那么证明你的代码是正确的。

深度优先与广度优先的区别

示例图

看看上面这个图，如果是深度优先的话，探索的顺序应该是1-2-4-5-3-6。如果是广度优先的话，探索的顺序应该是1-2-3-4-5-6。注意，这里规定左边优先探索。深度优先时，我们优先探索纵深，而广度优先时应该优先探索同一层。示例图所表示的是一种名为“树”的数据结构，我们之后会学习到。