0%

7.24夏令营总结

今天,我们有初步学习到了一种新的动态规划,那就是状态压缩的集合动态规划。而且,我们还复习了一些二进制的位运算。

二进制的位运算:

平常我们表示一个数是,经常用int型。其实,他还有一个用途,那就是表示一个32位的布尔集合。换句话讲,就是讲一个int型的数,转化成一个二进制数,再进行位运算。

例如,我们用一个数s表示一个32位的布尔集合,如[01001101000101110110101110100011],是其中一个状态:。

① 假如我们需要取出集合中的第k位,那么就是s & (1<<k)

② 假如我们需要将集合的第k位变成1,那么就是s + (1<<k)

③ 假如我们需要将集合的第k位变成0,那么就是s - (1<<k)。

状态压缩:

通常,我们表示一个状态时,由于状态数实在太多,放不下,特别是动态规划,怎么办呢?

刚刚我们讲到,可以用一个int型表示一个32位的布尔集合,如果用int型,需要4字节;如果用数组表示,需要32字节,整整省了8倍的空间。而且,用位运算,可以解决绝大部分的操作。同样可以表示这么多状态,,空间上却可以节省8倍。

例题:最短路径问题

【问题】给定一个图,包括边的长度,从任意一点出发,要求走遍所有点,问最短路径?

【输入】

5 6

0 4 2

0 3 3

1 4 3

1 3 1

1 2 2

2 3 4

【输出】

dfs:10

【分析dfs】假如这一道题,使用搜索左,我们应该怎么找子问题呢?

按照我们平时的思路,应该是开一个布尔集合,实时记录当前的那些点用了,那些点没用,然后记录当前搜索到的点,记录当前长度,当每一个点都搜到了就退出。

然而,如果这么编的话,是失败的。因为,我们无法进行记忆化搜索,也就是找不到子问题。

那么,子问题是什么呢?如图:

他不见了。

首先,假如我们搜到了点v,那么与之相连的点有p1,p2,p3,p4,那么,子问题就是,把点v加进集合s后(表示点v已经走过),从点pi出发最短路径问题(不包括集合s内的点)。这里有一个限制条件,就是,如果点pi在集合s内(即点pi已经走过),那么,我们就无需计算从点pi出发的子问题。

如果集合内,表示只有一个点还可以走,那么,我们就可以结束了,返回0即可。因为从该点出发,已经不能走到别的点了,因为别的点都已经走过了。

这样,我们就可以用记忆化了。用F[s][v]表示s这一状态的集合,从v点出发的最短路径,这样,就可以记忆化了。

关于布尔集合,我们已经知道可以用一个int型表示。我们用1表示还可以用,0表示已经用了,点的序号从0到N-1,那么搜索开始时就应该为((1<<N)-1),1<<N,那么集合为1000…000,再减1,就变成[1111…1111](N-1个1)。

还有一点,那就是由于要走遍所有点,因此,从哪一点出发都没有问题,因此,我们为了方便,就从点0出发。

【分析dp】关于dp有一点说明,那就就是做dp题目的时候,都有两种方向,一种就是大问题调用小问题,还有一种是小问题改进大问题。

首先是大问题调用小问题。与搜索的记忆化类似,用用G[s][p]表示p这一状态的集合,从v点出发的最短路径,那么

他不见了。

我们枚举s和p,q是与p相连的点。从点q出发的最短路径问题是子问题,那么从点q出发的子问题,表示就是G[s-(1<<p)][q],其中,s-(1<<p)是指点p已经走过了,要删去。

注意的是,枚举点p和点q时,要注意点p和点q在集合s中是尚未走过的。

而小问题改进大问题则差别不大,主要在于状态转移方程,为

他不见了。

同样是枚举s,p,q,不过点q有些不同,在于点q一定要已经走过了。小问题就是G[s][p],而大问题就是G[s+(1<<q)][q],如图。其中,s+(1<<q)是指向前推,搜索到点q,因此集合s要表示点q尚未走过。

他不见了。

【程序】说明:dfs正确,dp有错,但思想正确。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("setdp.in");
ofstream fout("setdp.out");

#define maxn 20
#define oo 100000000

vector <int> adj[maxn];//储存相连的点
int dist[maxn][maxn]; //储存边长的长度
int F[1<<maxn][maxn], G[1<<maxn][maxn];
int N, M;

int empty_() {
for (int i=0; i<=(1<<N); ++i)
for (int j=0; j<=N; ++j)
F[i][j] = G[i][j] = oo;
}

int in_() {
fin >> N >> M;
for (int i=0; i!=M; ++i) {
int a, b, c;
fin >> a >> b >> c;

adj[a].push_back(b);
adj[b].push_back(a);
dist[a][b] = dist[b][a] = c;
}

empty_();//清空数组
}

int chk(int Q) {
int sum=0;
for (int i=0; i!=N; ++i)
if (Q & (1<<i)) sum++;

return sum;
}

int dfs(int s, int v) {
if (chk(s)==1) return 0;//检查边界

if (F[s][v]!=oo) return F[s][v];//记忆化

int minn=oo;
s -= (1<<v);//v已经走过了

for (int i=0; i!=adj[v].size(); ++i) {//枚举每一个与v相连的点
int p=adj[v][i];

if (s & (1<<p))//点p在集合s内(即点p尚未走过)
minn <?= dfs(s,p)+dist[v][p];
}

return F[s][v] = minn;//记忆化、返回
}

int dp1() {
empty_();

G[1][0] = 0;
for (int s=1; s!=(1<<N); s++)
for (int p=1; p!=N; ++p)
if (s & (1<<p))//点p尚未走过
for (int j=0; j!=adj[p].size(); ++j) {
int q=adj[p][j];// 枚举每一个与p相连的点

if (s &(1<<q)) //点q尚未走过
G[s][p] <?= G[s-(1<<p)][q]+dist[p][q];//状态转移方程
}

return G[(1<<N)-1][0];
}

int dp2() {
empty_();

G[1][0] = 0;
for (int s=1; s!=(1<<N); s++)
for (int p=0; p!=N; ++p)
if (s & (1<<p)) //点p尚未走过
for (int j=0; j!=adj[p].size(); ++j) {// 枚举每一个与p相连的点

int q=adj[p][j];
if ( !(s & (1<<q) ) //点q已经走过

G[s+(1<<q)][q] <?= G[s][p]+dist[p][q]; //状态转移方程
}

return G[(1<<N)-1][0];
}

int main() {
in_();//读入

fout << "dfs:" << dfs((1<<N)-1,0) << endl;
fout << "dp1:" << dp1() << endl;
fout << "dp2:" << dp2() << endl;
return 0;
}
Thank you so much.