Czj's Blog

算法设计与分析-第六章

发表于 更新于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

推销员问题（简化版）

售货员的难题

货郎担问题（TSP）

题目大意

货郎担问题要求找到一条最短路径，让旅行者遍历所有城市后回到起点。针对不同的问题规模，分别采用不同的算法。

解法描述

朴素分支限界法（BFS）

  1. 算法思想

    借助队列实现广度优先搜索（BFS），每个节点存储当前路径和已访问的城市集合信息。在搜索过程中，维护一个bestl变量记录当前找到的最短路径长度，利用限界函数剪枝，即若当前节点路径长度加上到达下一个城市的成本大于bestl，则停止探索该节点，以此提高搜索效率。

  2. 实现方式

    定义结构体node，包含当前路径长度cl、当前处理的城市编号id以及记录已访问城市的bitset。从起点城市 1 开始，创建初始节点并入队。在队列非空时，取出队首节点。若当前路径长度大于等于bestl，则进行剪枝；若已访问城市数量达到总城市数量（本题不要求形成环路），则更新bestl；否则，遍历所有城市，若城市未被访问、与当前城市可达且新路径长度小于bestl，则创建新节点并入队。

  3. 复杂度分析

    • 时间复杂度：理论时间复杂度为\(O(n!)\) ，源于 BFS 遍历排列树的特性，但实际执行中，由于限界条件的作用，时间复杂度会有所降低
    • 空间复杂度：空间复杂度为\(O(n!)\) ，因为在最坏情况下，队列需要存储整个解空间的排列树。
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
#include <bits/stdc++.h>
using namespace std;
const int  INF = 0x3f3f3f3f;

int m[12][12];
int bestl, n;

// 排列树的节点定义
struct node {
	int cl; // 当前走过的路径长度
	int id; // 处理的第几个城市
	bitset<11> visited; // 集合记录已经访问过的城市

	//无参构造
	node() {}
	//构造函数
	node(int cl_, int id_) : cl(cl_), id(id_) {}
};

void bfs() {
	// 选用最小堆
	queue<node> q;
	// 创建一个节点，从该节点开始，因为1是固定位，其实是从1开始探索
	node temp(0, 1);
	temp.visited.set(1);
	q.push(temp);

	while (!q.empty()) {
		auto cur = q.front();// 当前节点，也就是活节点
		q.pop();
		int  t = cur.id;
		// 大于等于最优路径，没必要继续探索了，从下一个节点开始
		if (cur.cl >= bestl)
			continue;

		// 用bitset全1来判断是不是处理到最后一个城市
		if ((int)cur.visited.count() == n) {
			//本题不用形成环路
			bestl = min(bestl, cur.cl);
			continue;
		}

		// 从当前节点开始探索
		for (int  j = 1; j <= n; ++j) {
			// 满足约束条件和限界条件
			if (!cur.visited.test(j) && m[t][j] != INF && cur.cl + m[t][j] < bestl)
				//未探索，可联通，可能更优
			{
//				cout << cur.cl << endl;
				temp = node(cur.cl + m[t][j], j);
				temp.visited = cur.visited;
				temp.visited.set(j);
				q.push(temp);
			}
		}
	}
}

int main() {
	cin >> n;
	bestl = INF;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int temp;
			cin >> temp;
			if (temp == -1)m[i][j] = INF;
			else m[i][j] = temp;
		}
	}

	bfs();
	cout << bestl;

	return 0;
}

Bellman-Held-Karp（动态规划）

  1. 算法思想

    利用状态压缩动态规划策略，将问题状态表示为当前访问的城市集合。其核心在于通过逐步添加新城市到当前集合，依据状态转移方程更新到达新城市的最小成本，最终从所有可能的回路中找出成本最小的路径。

  2. 实现方式

    使用二维数组dp[idx][t]记录状态，idx是用二进制表示的城市集合，t表示当前到达的城市，dp的值代表在该状态下抵达城市t的消耗。先将dp数组初始化为极大值，设置dp[1][0] = 0，表示从起点 0 出发到达自身成本为 0。通过三层循环进行状态转移，外层循环遍历所有可能的城市集合（从 1 到 \((1<<n)-1\) ），中层循环遍历集合内的城市u，内层循环遍历不在集合中的城市v，执行dp[i|(1<<v)][v]=min(dp[i|(1<<v)][v], dp[i][u]+g[u][v])更新状态。最后，通过ans = min(ans, dp[(1<<n)-1][i]+g[i][0]) 寻找最优边以构成最终回路，得出最小成本路径。

  3. 复杂度分析

    • 时间复杂度：时间复杂度为 \(O(n^2\times2^n)\) ，这是因为存在三层循环，其中两层与城市集合相关（复杂度为\(O(2^n)\) ），一层与城市数量相关（复杂度为\(O(n)\) ）
    • 空间复杂度：空间复杂度是\(O(n\times2^n)\) ，主要用于存储动态规划表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
#include <bits/stdc++.h>
using namespace std;
//只有最多20个城市，可以采用状态压缩表示所有可能的回路，n个比特位，最多(2^n)-1种可能
const int N = 20;
int g[N][N], n, dp[1 << N][N], ans = 0x3f3f3f3f;

//dp[idx][t]的第一维是idx表示方案的编号，第二维是该方案的到达了点t，dp的值就是在这个方案下抵达城市t的消耗
void Bellman_Held_Karp() {

	for (int i = 1; i < (1 << n); i++) {
		//进行(2^n)-1次循环，检查所有的可能，每一个i都代表的一个方案
		for (int u = 0; u < n; u++) {
			//遍历所有点，找到那些已经在集合中的点
			if (i & (1 << u)) {
				//如果第u个点与上i是1，那说明这个点在本方案中，需要操作它
				for (int v = 0 ; v < n; v++) {
					//以点u为当前集合的外延点，检查其余的点，看能不能加入集合
					if (!(i & (1 << v))) {
						//如果v不在当前集合中，不会形成回路，可以用来更新dp数组
						dp[i | (1 << v)][v] = min(dp[i | (1 << v)][v], dp[i][u] + g[u][v]);//最小化消耗
						//i|(1<<v)表示含有v的那个方案
					}
				}
			}
		}
	}

	//上述代码形成了一个非回路解，下面需要寻找最优边来组合成最终回路

	int t = (1 << n) - 1; //以这个值为第一维下标的dp表示经过了所有城市的解
	for (int i = 0; i < n; i++) {
		//检查最后一个dp中的所有值，以各个点为回环点，最小化答案
		ans = min(ans, dp[t][i] + g[i][0]); //起点是0
	}
}
int main() {
	cin >> n;
	//初始化
	memset(dp, 0x3f, sizeof dp);//初始化为最大值
	dp[1][0] = 0;//起点是0号城市，此时消耗为0
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> g[i][j];
		}
	}
	Bellman_Held_Karp();
	cout << ans;
	return 0;
}