0%

穷尽搜索

发表于 更新于
挑战程序设计竞赛(Programing Contest Challenge Book)

递归函数

1
2
3
4
int fact(int n){
    if (n == 0) return 1;
    return n * f(n - 1);
}

在编写一个递归函数的时候，函数的停止条件是必须存在的。

当n=0时，fact函数不在调用自身，而是返回1。如果没有这一条件，函数就会无限的递归下去。

1
2
3
4
int fib(int n){
	if(n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

这个函数在递归时，会指数级别地扩展。

1
2
3
4
5
6
7
int memo[MAX_N + 1];

int fib(n){
	if(n <= 1) return n;
    if(memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

DFS

部分和问题

给定整数a1,a2,……an判断是否可以从中选出若干数，使他们的和恰好为k。

n=4, a={1, 2 ,4, 7}, k=13

Yes (13 = 2 + 4 + 7)

n=4, a={1, 2 ,4, 7}, k=13

No

从a1开始按顺序决定加或不加，全部n个数都决定后再判断它们的和是不是k即可。因为状态数是$2^{n}$,所以，复杂度是$O(2^{n})$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[MAX_N];
int n, k;

bool dfs(int i, int sum){
	if(i == n) return sum == k;
    
    if(dfs(i + 1, sum + a[i])) return true;
    
    if(dfs(i + 1, sum)) return true;
    
    return false;
}

void solve(){
    if (dfs(0, 0)) printf("Yes\n");
    else printf("No\n");
}

深度优先搜索从最开始的状态出发，遍历所有可以到达的状态。由此可以对所有状态进行操作，或者列举所有状态。

八联通

***

*W*

***

(W表示积水)

从任意的W开始，不停地把邻接部分用’.’代替，1次DFS后与初始的这个W连接的所有W就都被替换成’.’知道途中不再存在W为止，总共进行的DFS次数就是答案。

8个方向对应了8种状态转移。每个格子作为DFS的参数至多被调用一次，复杂度$O(8 × N × M)$ = $O(N × M)$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int N, M;
char field[MAX_N][MAX_M];

void dfs(int x, int y){
    field[x][y] = '.';
    for(int dx = -1; dx <= 1; dx++)
        for(int dy = -1; dy <= 1; dy++){
            int nx = x + dx; ny = y + dy;
            if(0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') dfs(nx, ny);
        }
    return ;
}

void solve(){
    int res = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            if (field[i][j] == 'W'){
                res ++;
                dfs(i, j);
            }
    printf("res\n");        
}

BFS

BFS与DFS的不同之处在于搜索的顺序，宽度有限搜索总是先搜索距离初始状态近的状态。

也就是说，它是按照开始状态->只需1次转移就可以到达的状态->只需2次转移就可以到达的状态……这样的顺序进行搜索的。对于同一个状态，宽度优先搜索只经过一次，因此复杂度为$O(状态数 × 转移的方式)$

DFS(隐式地)利用了栈进行计算，而BFS则利用了队列。

搜索时首先将初始状态加入队列，此后从队列的最前端不断取出状态，把该状态可以转移到的状态中尚未访问过的部分加入队列，如此往复，直到队列被取空或者找到了问题的解。通过观察这个队列，我们就可以知道所有的状态都是按照初始状态由近及远的顺序被遍历的。

迷宫最短路径

给定一个大小为$N × M$ 的迷宫。迷宫由通道和墙壁组成，每一步都可以向邻接的上下左右四格通道移动，求起点到终点的最小步数。注意：本题假设从起点一定可以移动到终点

$N, M \leq 100$

宽度优先搜索从开始状态由近到远的顺序进行搜索，因此可以很容易地用来求最短路，最少操作等问题的答案。这个问题中，状态仅仅是目前所在的坐标，因此可以构造成pair或者编码成int来表达状态。转移的方式为四方向，状态数与迷宫的大小是相等的，所以复杂度$O(4 × N × M) = O(N × M)$

这个问题中由于要求最短距离，不妨用d[N][M]数组把最短距保存。初始时用充分大的常数INF来初始化它。

到达终点时就会停止搜索，可如果继续下去知道队列为空，就可以计算出到各个位置的最短距离。此外，如果搜索到最后，d依然为INF，便可得知这个位置就是无法从起点到达的位置。

若INF过大，会有溢出风险：INF = $2^{31} - 1$ 。如果想用d[nx][ny] = 

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
const int INF = 100000000;
typedef pair<int ,int> P;

char maze[MAX_N][MAX_M + 1];
int N, M;
int sx, sy;//起点坐标
int gx, gy;//终点坐标

int d[MAX_N][MAX_M];//起点到各个点的最短距离的数组
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};

int bfs(){
    queue <P> que;
    for( int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            d[i][j] = INF;
    que.push(P(sx, sy));
    d[sx][sy] = 0;
    
    while(que.size()){
		P p = queue.front(); que.pop();
        if(p.first == gx && p.second == gy) break;
        for (int i = 0; i < 4; i++){
			int nx = p.first + dx[i], ny = p.second + dy[i];
            if(0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            } 
        }
    }
    return d[gx][gy];  
}

void solve(){
	int res = bfs();
    printf("%d\n", res);
}

BFS和DFS一样，都可以生成所有能够遍历到的状态，因此需要对所有状态进行处理时使用BFS也是可以的。但递归函数可以简便地编写而且状态的管理也更简单，所以一般用DFS实现。反之，在求取最短路径时DFS需要反复经过同样的状态，此时用BFS好。

BFS会把状态逐个加入队列，因此通常需要与状态数成正比的内存空间。反之DFS是与最大递归深度相关的，与状态数相比，递归深度不会太大，所以可以认为DFS更节省内存。

此外，也有采用与BFS类似的状态转移顺序，并且注重节约内存占用的迭代加深DFS(IDDFS, Interactive Deepening Depth-First Search) IDDFS是一种在最开始将DFS的递归次数控制在1次，在找到解之前不不断增加递归深度的办法。

特殊状态的枚举

虽然生成可行解空间多数采用DFS，但在状态空间比较特殊时，可以简短地实现比如C++标准库中提供了next_permutation这一函数，可以把n个元素共n!中不同的排列生成出来。又或者，通过使用位运算，可以枚举从n个元素中选出K个的共$C_{n}^{k}$ 种状态获是某个集合种的全部子集等。

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
bool used[MAX_N];
int perm[MAX_N];
//生成{0, 1, 2, 3, 4 ... n - 1}的所有排列
void permutaion1(int pos, int n){
    if (pos == n){
        //print
        return;
    }
    for (int i = 0; i < n; i++){
        if(!used[i]){
            used[i] = true;
            perm[pos] = i;
            permutation(pos + 1, n);
            used[i] = false;
        }
    }
    return ;
}

#include <algorithm>

int perm2[MAX_N];

void permutation2(int n){
    for(int i = 0; i < n; i++){
        perm2[i] = i;
    }
    do {
        //todo
    } while(next_permutation(perm2, perm2 + n));
    return;
}

栈内存和堆内存

调用函数时，主调的函数所拥有的局部变量等信息需要存储在特定的内存区域，这个区域被称为栈内存区。另一方面，利用new或者malloc进行分配的内存区域被称为堆内存。

栈内存在程序分配时被同一分配，此后不再扩大。

由于这一区域大小有上限，所以函数的递归调用深度也有上限。虽然与局部变量有关，但C/C++还是可以进行上万次的递归调用。再JAVA中，执行程序时可以指定栈的大小。

全局变量被保存在堆内存区。有些时候需要开很大的数组，与其放在栈内存上，不如放在堆内存上以避免栈溢出的风险。