ACM笔记 – 搜索技术
|
309
|
0
|
ACM

3473 字
|
27 分钟

《算法竞赛入门到进阶》的该章节，主要介绍BFS和DFS，以及它们的优化技术，并介绍一些经典案例如排列组合、生成子集、八皇后、八数码、图遍历等。

递归和排序

问题

  1. 打印$n$个数的全排列，共$n!$个
  2. 打印$n$个数中任意$m$个数的全排列，共$\frac{n!}{(n-m)!}$个

解决方案

方案一、调用STL

先对这些数字进行排序，获得最小序列。然后使用之前提到的next_permutation()函数，不断获得下一个排列，直到函数返回false。

方案二、递归

思路：传入区间[begin, end], 将begin和begin+1的数字交换位置，然后递归调用函数，处理区间[begin+1, end]；当递归回到本层时，将begin+1和begin交换回来，然后将begin和begin+2交换位置。重复上述过程，直到begin+i抵达end为止。

#include <bits/stdc++.h>
using namespace std;

#define Swap(a, b); {int temp = a; a = b; b = temp;}
int a[] = { 1,2,3 };
int num = 0;

void Perm(int begin, int end) {
    if (begin == end) {
        for (int i = 0; i <= end; i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
        num++;
        return;
    }
    for (int i = 0; begin + i <= end; i++) {
        Swap(a[begin], a[begin + i]);
        Perm(begin + 1, end);
        Swap(a[begin], a[begin + i]);
    }
}

int main() {
    Perm(0, 2);
    cout << num;
}

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
6

上面的关键代码是for循环，我在这里出现了问题，以下是我最开始的for循环代码：

for (int i = 1; begin + i <= end; i++) {
    Swap(a[begin], a[begin + i]);
    Perm(begin + i, end);
    Swap(a[begin], a[begin + i]);
}

以上代码存在的问题：

  1. i的初值应为0，因为需要自己与自己交换一次，表示第一位数字还未和后面的数字交换时的排列。
  2. 递归应该是Perm(begin + 1, end)，算是粗心的问题。for循环是将第一个数字和后面的每个数字交换，然后将[begin + 1, end]拿去递归。

第二题只需要简单修改上述程序即可实现。

子集生成和组合问题

问题

打印$n$个数中任意$m$个数的组合，共$C_n^m=\frac{n!}{m!(n-m)!}$个

分析

求子集

求$n$个数中任意$m$个数的组合，即求$n$个数字的子集中，元素数目为$m$的子集。书上介绍了一种很有意思但也很容易理解的方法：以$n=2$的集合${a_0, a_1}$为例。因为$n=2$，因此设2个二进制位，每个位上的1代表一个元素。
表格展示：

子集 $\varnothing$ $a_0$ $a_1$ $a_0, a_1$
二进制数 0 0 0 1 1 0 1 1

这样，只要输出从0到1 << n的每一个数字中每个二进制位上0和1的分布，就可以得到所有的子集。

代码：

#include <bits/stdc++.h>
using namespace std;

void print_set(int n) {
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                cout << j << " ";
            }
        }
        cout << endl;
    }
}

int main() {
    int n;
    cin >> n;
    print_set(n);
}
为什么想到用二进制位？
因为n个元素的全部子集数量刚好为$2^n$个，若用1代表有，0代表无，子集即为不同二进制位上1和0的排列组合。

求有$m$个元素的子集

最容易想到的办法是逐位检查，每个数字检查n次，求得1的数量（即子集中元素个数），若1的数量为m，则满足条件，输出。

书上还介绍了一种很神奇的位运算求1的数量的方法，可以提高速度。
$$k=k\&(k-1)$$
该方法可以一次性消除二进制数的最后一个1，如下：
$$1011\&(1011-1)=1011\&1010=1010$$
$$1010\&(1010-1)=1010\&1001=1000$$
$$1000\&(1000-1)=1000\&0100=0000$$
因此只需要记录该操作执行的次数，就能获得该二进制数中1的个数。

glibc还内置了求二进制数的内部函数，直接返回二进制数中1的数量。

int __builtin_popcount(unsigned int x);

代码实现

#include <bits/stdc++.h>
using namespace std;

void print_set(int n, int m) {
    for (int i = 0; i < (1 << n); i++) {
        int k = i, num = 0;
        while (k) {
            k = k & (k - 1);
            num++;
        }
        if (num == m) {
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    cout << j << " ";
                }
            }
            cout << endl;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    print_set(n, m);
}

总结反思

该方法用到了位运算，而int型变量在一般情况下拥有32个位，所以上述代码理论上最多能计算30个数字的排列组合。因为int型变量只有32个位，且最高位是符号位，而在for循环的条件是i < (1 << n)，1 << 31 = -2147483648,1 << 32 = 0，因此只要$n>30$，那么for循环一次都不会执行。若要计算n值更大的排列组合，可以将变量定义拥有更多位的数据类型，如long long unsigned，但是注意同时要修改for循环中的1，1默认是32个位，应该用long long unsigned型的变量来储存这个1。

代码如下：

#include <bits/stdc++.h>
using namespace std;

#define LL long long unsigned

void print_set(LL n, LL m) {
    LL a = 1;
    for (LL i = 0; i < (a << n); i++) {
        LL k = i, num = 0;
        while (k) {
            k = k & (k - 1);
            num++;
        }
        if (num == m) {
            for (LL j = 0; j < n; j++) {
                if (i & (a << j)) {
                    cout << j << " ";
                }
            }
            cout << endl;
        }
    }
}

int main() {
    LL n, m;
    cin >> n >> m;
    print_set(n, m);
}

BFS

BFS和队列

具体编程时，一般用队列来具体实现BFS。

相关习题






八数码问题和状态图搜索

八数码问题可以表示BFS对“状态”的处理。

康托展开

康托展开Cantor()是一种特殊的哈希函数，在八数码问题中可以用于判重（判断某状态是否已经重复）。如何判断呢？设置一个大小为n!的数组，用哈希函数确定每一个状态对应的数组下标，标记访问过的状态对应的数组元素。每次即将操作某状态时，只需要检查该数组，就能确定是否已经访问过。

状态 012345678 012345687 ... 876543210
Cantor 0 1 ... 362880-1

第1行是0~8这九个数字的全排列，从小大大排序；第2行表示这个排列所对应的位置。

复杂度：$O(n!n^2)$
若直接暴力判重，则复杂度为$(n!n!)$

公式

$$X=a[n]\times(n-1)!+\dots+a[i]\times(i-1)!+a[1]\times0!$$

举例

例如，3 5 7 4 1 2 9 6 8 展开为 98884。因为X=28!+37!+46!+25!+04!+03!+22!+01!+00!=98884.
排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为28!
排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为37!
以此类推，直至00!

以上内容引自维基百科 康托展开

代码实现

我写的代码真的非常复杂丑陋，很不好意思把它贴上来……不过还是放这里吧，希望能督促我进步。

#include <bits/stdc++.h>
using namespace std;

#define MAX_LEN 362880
#define NUM 9
#define Swap(a, b) {int T = a; a = b; b = T;}

int ha[MAX_LEN] = { 0 };

typedef struct Node {
    int a[NUM]; // 九宫格
    int num;    // 九宫格代表的数字
    int zerop;  // 零的位置
    int move;   // 移动次数
}node;

// 没有重复则返回true
bool Cantor(node b) {
    int a = b.num;
    // 哈希
    int rec[10];    // 记录每个数字是否已经被前面的位用过
    for (int i = 0; i < 10; i++) {
        rec[i] = 1; // 初始化
    }
    int value = 0;  // 哈希值
    int times = 8 * 7 * 6 * 5 * 4 * 3 * 2;
    for (int i = 0; i < NUM - 1; i++) {
        int p = a % 10; // 获取到当前位
        a = a / 10;
        int num = 0;
        for (int i = 0; i < p; i++) {
            num += rec[i];  // 小于当前位且还未被用过的位数
        }
        value += num * times;   // 计算当前位小于当前排列的排列数量
        if (NUM - i - 1 > 0) {
            times /= (NUM - i - 1);     // 阶乘数-1
        }
        rec[p] = 0;             // 标记为使用过
    }
    // 判重
    if (ha[value]) {
        return false;
    }
    else {
        ha[value] = 1;
        return true;
    }
}

int main() {
    node start, des;
    start.move = 0;
    des.move = 0;
    start.num = 0;
    des.num = 0;
    // 九宫格的第九格代表的是个位数
    for (int i = 0; i < NUM; i++) {
        cin >> start.a[i];
        start.num = start.num * 10 + start.a[i];
        if (!start.a[i]) {
            start.zerop = i;    // 获取零在九宫格中的位置
        }
    }
    for (int i = 0; i < NUM; i++) {
        cin >> des.a[i];
        des.num = des.num * 10 + des.a[i];
        if (!des.a[i]) {
            des.zerop = i;  // 获取零在九宫格中的位置
        }
    }

    Cantor(start);  // 记录一下初始状态
    int move[] = { -3,-1,1,3 }; // 零在九宫格中的位移操作
    queue<node>a;
    a.push(start);
    bool found = false; // 记录是否已经找到目标
    while (!a.empty() && !found) {
        node p = a.front();
        for (int i = 0; i < 4; i++) {
            if (p.zerop + move[i] >= 0 && p.zerop + move[i] < NUM) {
                if ((p.zerop % 3 == 0 && move[i] == -1) || (p.zerop % 3 == 2 && move[i] == 1)) {
                    continue;
                }
                node en = p;    // 复制一个用来入队列的结点
                en.move = p.move + 1;   // 移动步数增加
                en.zerop = p.zerop + move[i];   // 改变zerop
                Swap(en.a[en.zerop], en.a[p.zerop]);    // 交换零的位置
                en.num = 0;
                for (int i = 0; i < NUM; i++) {
                    en.num = en.num * 10 + en.a[i];
                }
                if (en.num == des.num) {
                    found = true;   // 已经找到
                    cout << en.move;
                    break;
                }
                if (Cantor(en)) {
                    a.push(en); //入队列
                }
            }
        }
        a.pop();    // 弹出当前队头元素
    }
}

反思总结

《算法竞赛入门到进阶》P50 提到书上的代码“细节很多，请读者仔细体会，要求能独立写出来”。所以我就结合自己写的代码，好好体会一下书上的代码吧。

  1. Cantor()函数中会用到0-8的阶乘，我在代码是每次都去计算了这个阶乘，而示例代码中是直接用一个数组储存了这些值。这提示在程序中反复用到的需要运算的值，可以储存起来直接使用。
  2. 示例程序中把一维坐标先转换成三维坐标，处理后再转回一维坐标。以后在处理更为复杂的问题时或许需要这样的方法。
  3. 哈希过程中，需要计算当前元素排在还未出现过的元素中的第几个。我的处理方法是另设一个0-9的数组，用0表示已经处理过，1表示还未处理过。每一次都扫描一趟整个数组。这是十分低效且没有必要的。书上的思路是，每次依次比较该位和后面所有位上元素的大小，遇到一个比自己小的就+1，这样就能获取到当前位上比自己小的还未出现过的数字数目了（因为已经出现过的都在前面，我们只检查后面）。

哈希部分关键代码：

for(int i = 0; i < n; i++) {
    int num = 0;
    for(int j = i + 1; j < n; j++) {
        if(str[i] > str[j]){
            num++;
        }
    }
}

另外程序中还遇到了没见过的库函数：

memcpy(strDes, strA, strlen(strA) + 1);

参考：菜鸟教程

BFS与$A*$算法

A*算法是一种“启发式”搜索算法，是“BFS+贪心”。网页演示

曼哈顿距离：两个点在标准坐标系上的实际距离。
$$d(A, B)=\left| x_A-x_B\right|+\left|y_A-y_B\right|$$

$A*$算法的一般性描述

在搜索过程中，用一个评估函数对当前状况进行评估，得到最好的状态，从这个状态继续进行搜索，直到目标。设$x$是当前所在的状态，$f(x)$是对$x$的评估函数，有
$$f(x)=g(x)+h(x)$$
$g(x)$表示从初始状态到$x$的实际代价，他不体现$x$和终点的关系。若它等于0，则就是普通的BFS算法，没有启发函数的参与。
$h(x)$表示$x$到终点的最优路径的评估，它就是"启发式"信息，$h(x)$被称作启发函数。若它等于0，则就是贪心算法。单纯的贪心在走迷宫一类的问题中，可能会陷入局部最优解（走入死胡同）。

$A*$算法对八数码问题的优化

$h(x)$函数可以取：

  1. 以不在目标位置的数码个数作为估价函数。（？啥意思）
  2. 以不在目标位置的数码与目标位置的曼哈顿距离作为估价函数。
  3. 以逆序数作为估价函数（逆序数可以判断八数码是否有解）（？我线性代数学得很烂）

相关习题

双向广搜

从起点和终点互相向彼此靠拢。可以节省搜索空间。

相关习题：


DFS

DFS，深度优先搜索。

DFS和递归

DFS一般都是用递归程序实现的。

回溯和剪枝

在大部分情况下，很多路径是没有必要走到底的，可以在发现方向已经不对的时候立刻回头，这就是回溯思想。在回溯中用于减少子节点拓展的函数就是剪枝函数。

$N$皇后问题

我的思路

直接看了书，就是一行一行的放置皇后，每一行是一层递归。

代码实现

#include <bits/stdc++.h>
using namespace std;

#define NUM_QUEEN 8
#define inta int a[NUM_QUEEN]   // 用于记录某行皇后所在的列数

int num = 0;    // 记录情况总数

// 检查是否满足条件，满足返回true，否则返回false
bool isOK(inta, int line) {
    for (int i = 0; i < line; i++) {
        if (a[i] == a[line]) {
            return false;   // 同行，返回false
        }
        if (fabs(a[i] - a[line]) == fabs(i - line)) {
            return false;   // 同对角线，返回false
        }
    }
    return true;
}

void printTable(inta) {
    for (int i = 0; i < NUM_QUEEN; i++) {
        for (int j = 0; j < NUM_QUEEN; j++) {
            if (j == a[i]) {
                cout << 1 << " ";
            }
            else {
                cout << 0 << " ";
            }
        }
        cout << endl;
    }
    cout << endl;
}

void solve(inta, int line) {
    if (line == NUM_QUEEN) {
        num++;
        return;
    }
    for (int i = 0; i < NUM_QUEEN; i++) {
        a[line] = i;
        if (isOK(a, line)) {
            solve(a, line + 1);
        }
    }
}

int main() {
    inta = { 0 };
    solve(a, 0);
    cout << "共有" << num << "种情况";
}

上方的printTable()函数用于展示棋盘，需要的话可以在main()函数中调用。

反思总结

基本和书上的代码一模一样……不过学会了一种新的概念叫“打表”，先计算出1-10皇后问题的解存入数组，然后得到输入后立即输出，可以避免超时。这样看来，ACM计算时间是计算从数据输入到输出的间隔。

书上提到了算法的优化方式：数据结构：舞蹈链和 位运算。并提到N皇后问题是一个NP完全问题，不存在多项式时间的算法。以上几个概念我还未学习，待粗读完整本书行成大概的知识体系后再来研究。

相关习题






迭代加深搜索

某些搜索树深度极深，广度极广。若采用单纯DFS，会陷入递归无法返回；若采用单纯BFS，队列空间会爆炸。因此引入一种结合二者的思想，即迭代加深搜索(Iterative Deepening DFS, IDDFS)

操作方法

先设定搜索深度为1，用DFS搜索一层。若没找到，则设定搜索深度为2，用DFS搜索两层，以此类推。
实例 - 埃及分数问题

$IDA*$

是IDDFS的优化，可以看做$A*$算法在IDDFS中的应用，即在IDDFS中加入估价函数进行剪枝操作。

POJ 3134 Power Calculus

暂未学习

相关习题


ACMBFSDFS位运算八数码八皇后搜索
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
ACM笔记 – 动态规划DP

							
							

							
ACM笔记 – 高级数据结构

							
							

							
ACM笔记 – STL和基本数据结构