POJ 3311 Hie With The Pie TSP 状压DP

缘起

继续水 状压DP 搞 tsp 的题目~ POJ 3311 Hie With The Pie

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给你一个有n+1(1<=n<=10)个点的有向完全图，用矩阵的形式给出任意两个不同点之间的距离。（其中从i到j的距
离不一定等于从j到i的距离）现在要你求出从0号点出发，走过0到n号点至少一次，然后再回到0号点所花的最小时
间。

输入：包含多组实例。每个实例第一个为n，然后是n+1行矩阵，每行矩阵有n+1个数字，第i行第j个数字表示从i-1到j-1号点的距离。当输入n=0时表示输入结束。

输出
对于每个测试用例，您应输出一个数字，表示交付所有比萨饼并返回比萨饼店的最短时间。

样本输入
3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

样本输出
8

限制
2s 64MB

本题和【2】的最大区别在于本题每个点经历的次数>=1就行了. 而【2】是<=2.

和【3】一个思路——还是状压DP. 

1
2
3
4
5
6
令dp[i][j] 是已经经过的（经历了就是1, 不管你经历几次, 没经历就是0）点集状态为i的情况下当前处于点j, 从这个状态开始计0, 要完成任务的最少花费.
首先, 要将0~n 提升为1~n+1, 不然数组下标不能为-1, 其次, 答案显然是dp[0][0].
因为打算使用记忆化搜索(空间复杂度给得起, 我DP个锤子~), 所以要考虑递归的出口.
dp[1<<n+1][1] = 0， 而dp[1<<n+1][i] = inf(对于n+1>=i>1) 这是因为本题是哈密顿回路而不是哈密顿路
径，本题最后是一定要回到1（比萨店）的~
ps: 本题貌似不需要处理不存在哈密顿回路的情况~

于是开始愉快的切代码了~

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
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LOCAL
const int inf = 0x3f3f3f3f;
int n, g[15][15], dp[1<<11][15],full;

int kk(int i, int j)
{
	if (~dp[i][j])
	{
		return dp[i][j];
	}
	if (i==full-1 && j == 1)
	{
		return dp[i][j] = 0;
	}
	int ans = inf;
	for (int k = 1,nxti;k<=n+1;k++)
	{
		if (k==j) // 不能原地踏步
		{
			continue;
		}
		nxti = 1<<k-1|i; // 状态转移了
		ans = min(ans, kk(nxti, k)+g[j][k]);
	}
	return dp[i][j] = ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d", &n), n)
	{
		for (int i = 1;i<=n+1;i++)
		{
			for (int j = 1;j<=n+1;j++)
			{
				scanf("%d", g[i]+j); // g[i][j] 是从i-1到j-1的距离
			}
		}
		memset(dp,-1,sizeof(dp));
		full = 1<<n+1;
		printf("%d\n", kk(0,0));
	}
	return 0;
}

他喵的~ StackOverflow掉了~ 其实写的时候就觉得不大对劲~ 尤其是转移的时候, 想想就会死循环! 因为状态转移的时候几乎不做任何限制~ 那就会出现 A->B->A 这种令人抓狂的情况.

肯定要剪枝~ 于是写了另外dfs的一版

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int inf = 0x3f3f3f3f;
int n, g[15][15],gg[15][15],full,best;

int dfs(int i, int j, int len) // len是迄今为止的长度
{
	if (len>best) // 剪枝
	{
		return inf;
	}
	if (i==full-1 && j == 1) // 形成了未必每个顶点恰好经历一次的哈密顿回路
	{
		printf("%d\n", best);
		best = len; // 优化best
		return 0;
	}
	int ans = inf;
	for (int k = 1,nxti;k<=n+1;k++)
	{
		if (k==j) // 不能原地踏步
		{
			continue;
		}
		nxti = 1<<k-1|i; // 状态转移了
		ans = min(ans, dfs(nxti, k, len+g[j][k])+g[j][k]);
	}
	return ans;
}

void floyd()
{
	for (int k = 1;k<=n+1;k++)
	{
		for (int i = 1;i<=n+1;i++)
		{
			for (int j = 1;j<=n+1;j++)
			{
				gg[i][j] = min(gg[i][j], gg[i][k]+gg[k][j]);
			}
		}
	}
}

void greedy() // 贪心初始化best,  贪心策略是从1出发, 每次都找距离当前点cur最近的且尚未访问过的点作为下一跳
{
	floyd(); // 先跑floyd, 将图中的距离全部变成最短距离, 有助于降低best
	best = 0;
	int state = full-1&~1, cur = 1;
	while(state)
	{
		int mmin = inf;
		for (int i = 0;i<=n;i++)
		{
			if (state>>i&1)
			{
				if (mmin>gg[cur][i+1])
				{
					mmin = gg[cur][i+1];
					cur = i+1;
				}
			}
		}
		best+=mmin;
		state &= ~(1<<cur-1);
	}
	best+=gg[cur][1]; // cur还要跳回1
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d", &n), n)
	{
		for (int i = 1;i<=n+1;i++)
		{
			for (int j = 1;j<=n+1;j++)
			{
				scanf("%d", g[i]+j); // g[i][j] 是从i-1到j-1的距离
			}
		}
		memcpy(gg,g, sizeof(g)); // 贪心在g的一个copy上贪心, 不要影响g本身
		full = 1<<n+1;
		greedy();
		dfs(0,1,0);
		printf("%d\n", best);
	}
	return 0;
}

可惜,被T掉了. 但是对拍过, 程序本身没有问题, 不会wa.

那上面慢在什么地方呢? 显然一般的, dfs如果慢的话, 那一定是搜索了太多无效状态. 但是剪枝也想不出什么更好的剪枝策略了. 怎么A掉此题呢? 我们换个视角.

首先使用floyd处理原图得到新图g,然后用【3】的办法处理（即跑tsp的板子）就行了. 论证如下

因为题目的特殊性，原图中一定存在哈密顿回路. 所以g中也一定存在哈密顿回路。所以如果g中找到的哈密顿代价最小的话（记g中哈密顿路径的集合为L）记最小代价为x, 则一定是原图中可能多次经过一个点, 但是保证每个点都至少经历一次的一条回路p（记原图中这种回路集合为K，则p属于K）。而且一定是K中代价最小的. 如果不是的话, 即存在代价严格更小的回路q: 0=a0->a1->…->an->a0=0, 则将q的每一段儿换成g中的路径, 则得到的也是L中的一条路径. 而且严格小于x, 这与x是L中最小代价矛盾! 所以我们就找到了本题求解的真正法门了——floyd预处理+tsp状压板子.

注意, g中的最短回路一定是哈密顿回路, 而不可能再是”有可能一个点经过多次”的回路. 因为floyd预处理已经保证了g中2点之间的直接距离就是两点之间的最短距离了.

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int inf = 0x3f3f3f3f;
int n,g[15][15], dp[1<<11][15],full; // dp[i][j] 是当前状态为i, 处于j顶点

int kk(int i,int j)
{
	if (~dp[i][j])
	{
		return dp[i][j];
	}
	if (i == full-1 && j == 1)
	{
		return dp[i][j] = 0;
	}
	int ans = inf;
	for (int x = 0,nxti;x<=n;x++)
	{
		if (j==x+1 || (i>>x&1) )
		{
			continue;
		}
		nxti = 1<<x|i;
		ans = min(ans, kk(nxti, x+1) + g[j][x+1]);
	}
	return dp[i][j] = ans;
}

void floyd()
{
	for (int k = 1;k<=n+1;k++)
	{
		for (int i = 1;i<=n+1;i++)
		{
			for (int j = 1;j<=n+1;j++)
			{
				g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while (scanf("%d", &n), n)
	{
		full = 1<<n+1;
		for (int i = 1;i<=n+1;i++)
		{
			for (int j =1;j<=n+1;j++)
			{
				scanf("%d", g[i]+j);
			}
		}
		floyd();
		memset(dp,-1,sizeof(dp));
		printf("%d\n", kk(0,1));
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 216kB
Length 1033
Lang C++
Submitted 2019-11-03 14:55:30
Shared
RemoteRunId 21017771

参考

【1】https://yfsyfs.github.io/2019/10/31/POJ-2288-Islands-and-Bridge-%E7%8A%B6%E5%8E%8BDP/

【2】https://yfsyfs.github.io/2019/10/31/HDU-3001-Traveling-%E7%8A%B6%E5%8E%8BDP/

【3】https://yfsyfs.github.io/2019/09/05/hdu-5067-Harry-And-Dig-Machine-tsp%E9%97%AE%E9%A2%98/