穷举搜索
对于一些困难的问题，我们只能穷举(brut force)搜索，是的，我们知道“穷举搜索”这个词，可是，具体怎么穷举呢？
很多问题可以归结到图的搜索，对于图的搜索，大家应该都知道 DFS 和 BFS，然而可能没有多少人知道如何对图做穷举搜索。我先举一个最简单的例子：哈米尔顿环(hamilton cycle)，不知道的，可以去维基百科上去查。
|
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 |
#include <assert.h> #include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> using namespace std; int start = 0; int N; vector<vector<int> > G; vector<int> P; // current path/stack vector<int> D; // vertex depth in stack, -1 indicate not yet discovered // so D also serve as Mark array of DFS void printham() { printf("found hamilton cycle: "); for (int i = 0; i < N; ++i) printf("%d ", P[i]); printf("n"); } void hamilton(int x, int k) { if (k == N) { assert(0); // never goes here } else { D[x] = k; // mark x P[k] = x; // put x into the path for (int j = 0, c = G[x].size(); j < c; ++j) { int y = G[x][j]; // Edge(x to y) if (D[y] != -1) { // found a cycle // (1 + k - D[y]) is the cycle length // so the condition is also (D[y] == 0 && k == N-1) if (y == start && k == N-1) printham(); // this is a hamilton cycle } else // not yet discovered hamilton(y, k+1); } D[x] = -1; // un-mark } } int main(int argc, char* argv[]) { int lineno = 1; while (!feof(stdin)) { int x, y; int fields = scanf("%d %dn", &x, &y); if (fields == 2) { if (min(x, y) < 0) { fprintf(stderr, "invalid vertex number at line %dn", lineno); return 3; } if (G.size() < (size_t)max(x, y) + 1) G.resize(max(x, y) + 1); G[x].push_back(y); } else { fprintf(stderr, "bad record at line %dn", lineno); return 3; } lineno++; } N = G.size(); P.resize(N); D.resize(N, -1); if (argc >= 2) start = atoi(argv[1]); else start = 0; hamilton(start, 0); return 0; } |
为了突出递归的逻辑，这个程序把所有（每次递归都相同的）函数参数换成了全局变量，从软件工程角度讲这是有问题的，但是作为示例，逻辑上更清楚一些。
这个程序从 stdin 读取一个图，这个图共 N 个结点，结点编号是 0~N-1。每行是一条边 src dest，中间用空白分隔。
从代码效率上讲，这个程序也也不够高效，一个在数据结构上（how to optimize vector<vector<int> > G ?）和程序逻辑(非递归) 上充分优化的版本，大约比这个要快10倍。
这个程序也接受一个参数 start ，表示搜索的起始结点，start 的默认值是 0。
下面是一个图的示例（g1.txt）：
0 1
1 2
3 5
2 4
5 1
0 2
2 3
3 4
5 0
4 5
运行 hamilton 3 < g1.txt
输出结果是：found hamilton cycle: 3 4 5 0 1 2
穷举的一般代码框架是：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
bruteforce(x, depth) { if (depth == max_depth) { // .... } else { mark[x] = true; for (y : x.children) { if (mark[x]) // ... else bruteforce(y, depth+1); } mark[x] = false; // this is the only diff with DFS } } |
这个就是dfs吧。
标准的dfs节点会做3个标记：
1、未访问的，白色；
2、已访问，未回溯的，灰色；
3、已回溯的，黑色。
lz所说的区别就相当于区分了黑色和白色而已。
标记不一定非得照搬教科书, 我这个 hamilton 环搜索中, 如果 D 数组中 D[i] != -1, 就是灰色. 某个结点 finish 之后又马上设置成-1(相当于白色). 在我这个例子中实际上是没有黑色的!