tsp学习

https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A
假设起点是0

dfs

$state$是一个$bitboard$，比如$0011$表示访问过第$0,1$个节点
$dp[state][u]$表示已经访问过了$state$中的节点，现在在$u$点，访问剩下所有的节点，最后到0所需要的代价
显然转移方程 d p [ s t a t e ] [ v ] = min ⁡ ( d p [ s t a t e ∪ { u } ] [ u ] + d i s t [ v ] [ u ] ∣ u ∉ s t a t e ) dp[state][v]=\min\left(dp[state\cup\left\{u\right\}][u]+dist[v][u]|u\notin state\right) dp[state][v]=min(dp[state∪{u}][u]+dist[v][u]∣u∈/state)

#include
#include
const int N = 15, INF = 0x3f3f3f3f;
//dp[state][u]访问过state中所有的节点,现在在u,访问剩下所有的节点，最后到0所需要的代价
int dp[1 << N][N], dist[N][N], n;
int tsp(int state, int v) {
	if (dp[state][v] != -1) {
		return dp[state][v];
	}
	if (state + 1 == (1 << n)) {
		if (0 == v) {
			dp[state][v] = 0;
		}
		else {
			dp[state][v] = INF;
		}
		return dp[state][v];
	}
	int res = INF;
	for (int u = 0; u < n; ++u) {
		if (0 == ((state >> u) & 1)) {//u not in  state
			//dp[state][v]=min(dp[state∪u][u]+dist[j][u])
			int temp = tsp(state | (1 << u), u) + dist[v][u];
			if (temp < res) {
				res = temp;
			}
		}
	}
	dp[state][v] = res;
	return res;
}
int main() {
	int e;
	scanf("%d%d", &n, &e);
	memset(dist, INF, sizeof(dist));
	memset(dp, -1, sizeof(dp));
	while (e--) {
		int s, t, d;
		scanf("%d%d%d", &s, &t, &d);
		dist[s][t] = d;
	}
	int res = tsp(0, 0);
	if (res == INF)res = -1;
	printf("%d\n", res);
	return 0;
}
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

dp

倒序

$state$是一个$bitboard$，比如$0011$表示访问过第$0,1$个节点
$dp[state][u]$表示已经访问过了$state$中的节点，现在在$u$点，访问剩下所有的节点，最后到0所需要的代价
显然转移方程 d p [ s t a t e ] [ v ] = min ⁡ ( d p [ s t a t e ∪ { u } ] [ u ] + d i s t [ v ] [ u ] ∣ u ∉ s t a t e ) dp[state][v]=\min\left(dp[state\cup\left\{u\right\}][u]+dist[v][u]|u\notin state\right) dp[state][v]=min(dp[state∪{u}][u]+dist[v][u]∣u∈/state)

简单来说就是把dfs改成递推的形式

#include
#include
const int N = 15, INF = 0x3f3f3f3f;
//dp[state][u]访问过state中所有的节点,现在在u,访问剩下所有的节点，最后到0所需要的代价
int dp[1 << N][N], dist[N][N], n;
int tsp() {
	dp[(1 << n) - 1][0] = 0;
	for (int state = (1 << n) - 2; state >= 1; --state) {
		for (int v = 1; v < n; ++v) {
			if (0 == ((state >> v) & 1))continue;//v not in state
			for (int u = 0; u < n; ++u) {
				if (0 == ((state >> u) & 1)) {//u not in state
					int temp = dp[state | (1 << u)][u] + dist[v][u];
					if (temp < dp[state][v]) {
						dp[state][v] = temp;
					}
				}
			}
		}
	}
	for (int u = 1; u < n; ++u) {
		int temp = dp[1 << u][u] + dist[0][u];
		if (temp < dp[0][0]) {
			dp[0][0] = temp;
		}
	}
	if (dp[0][0] == INF)return -1;
	return dp[0][0];
}
int main() {
	int e;
	scanf("%d%d", &n, &e);
	memset(dist, INF, sizeof(dist));
	memset(dp, INF, sizeof(dp));
	while (e--) {
		int s, t, d;
		scanf("%d%d%d", &s, &t, &d);
		dist[s][t] = d;
	}
	printf("%d\n", tsp());
	return 0;
}
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

另一种写法

#include
#include
const int N = 15, INF = 0x3f3f3f3f;
//dp[state][u]访问过state中所有的节点,现在在u,访问剩下所有的节点，最后到0所需要的代价
int dp[1 << N][N], dist[N][N], n;
int tsp() {
	dp[(1 << n) - 1][0] = 0;
	for (int state = (1 << n) - 2; state >= 0; --state) {
		for (int v = 0; v < n; ++v) {
			//if (0 == ((state >> v) & 1))continue;//v not in state
			for (int u = 0; u < n; ++u) {
				if (0 == ((state >> u) & 1)) {//u not in state
					int temp = dp[state | (1 << u)][u] + dist[v][u];
					if (temp < dp[state][v]) {
						dp[state][v] = temp;
					}
				}
			}
		}
	}
	if (dp[0][0] == INF)return -1;
	return dp[0][0];
}
int main() {
	int e;
	scanf("%d%d", &n, &e);
	memset(dist, INF, sizeof(dist));
	memset(dp, INF, sizeof(dp));
	//for (int i = 0; i < n; ++i) {
	//	dist[i][i] = 0;
	//}
	while (e--) {
		int s, t, d;
		scanf("%d%d%d", &s, &t, &d);
		dist[s][t] = d;
	}
	printf("%d\n", tsp());
	return 0;
}
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

正序

$state$是一个$bitboard$，比如$0011$表示访问过第$1,2$个节点（注意这里0是不在state里的）
$dp[state][u]$访问$state$中所有的节点,且现在在u,所需要的代价
显然转移方程 d p [ s t a t e ] [ v ] = min ⁡ ( d p [ s t a t e \ { v } ] [ u ] + d i s t [ u ] [ v ] ∣ u ∈ s t a t e ) ( v ∈ s t a t e ) dp[state][v]=\min\left(dp[state\backslash\left\{v\right\}][u]+dist[u][v]|u\in state\right)(v\in state) dp[state][v]=min(dp[state\{v}][u]+dist[u][v]∣u∈state)(v∈state)

#include
#include
const int N = 15, INF = 0x3f3f3f3f;
//dp[state][u]访问state中所有的节点,且现在在u,所需要的代价
int dp[1 << N][N], dist[N][N], n;
int tsp() {
	for (int state = 1; state < (1 << (n - 1)); ++state) {
		for (int v = 1; v < n; ++v) {
			if (0 == ((state >> (v - 1)) & 1))continue;//v not in state
			if ((1 << (v - 1)) == state) {//0->v
				dp[state][v] = dist[0][v];
			}
			else {
				dp[state][v] = INF;
				for (int u = 1; u < n; ++u) {
					if (0 == ((state >> (u - 1)) & 1))continue;//u not in state
					int temp = dp[state ^ (1 << (v - 1))][u] + dist[u][v];
					if (temp < dp[state][v]) {
						dp[state][v] = temp;
					}
				}
			}
		}
	}
	int ans = INF;
	for (int u = 1; u < n; ++u) {
		int temp = dp[(1 << (n - 1)) - 1][u] + dist[u][0];
		if (temp < ans) {
			ans = temp;
		}
	}
	if (INF == ans) {
		return -1;
	}
	return ans;
}
int main() {
	int e;
	scanf("%d%d", &n, &e);
	memset(dist, INF, sizeof(dist));
	while (e--) {
		int s, t, d;
		scanf("%d%d%d", &s, &t, &d);
		dist[s][t] = d;
	}
	printf("%d\n", tsp());
	return 0;
}
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

https://mp.weixin.qq.com/s?__biz=MzA4NzkxNzM3Nw==&mid=2457480484&idx=1&sn=bf45afaa2bd987747c34a03b9176e89f&chksm=87bc9b0ab0cb121c311299dbf16a55fe76b2b60d6d9e073f37deec49e28766ca416860a7659c&scene=21#wechat_redirect
https://blog.csdn.net/Code92007/article/details/86422273