> 文章列表 > 算法设计与分析第四次作业

算法设计与分析第四次作业

哦,今天遇到了一个超级有意思的算法题目集合,全是关于分支限界法的!让我先喘口气,好好消化一下。

首先,什么是分支限界法?

简单概括,分支限界法就像一个聪明的“试错者”。它会把一个问题拆分成多个小问题(分支),然后通过设定一个边界(限界),把那些不可能得到更优解的分支提前剪掉。这样就能避免浪费时间在无意义的计算上!

比如,假设我要找一个旅行商问题的最优路线,分支限界法会这样做:

1. 创建一个优先队列,每个节点代表一种可能的路径。

2. 定义一个“界限”,比如当前路径的总成本,如果某个节点的成本已经超过了当前最优解,它就会被直接丢进垃圾桶。

3. 从队列中取出成本最低的节点,继续扩展它的子节点,直到找到最优解。

这就像在迷宫里找出口,但你有一个超级聪明的指南针,能提前告诉哪些路死路一条,不用走了!

那么,为什么分支限界法比回溯法更聪明呢?

回溯法就像一个固执的老人,会把所有路径都走一遍,哪怕已经知道那条路肯定不对劲。而分支限界法则会提前预判,把肯定没戏的路给剪掉。这在处理大规模问题时,效率提升了不止一个档次!

比如,对于一个旅行商问题(TSP),用分支限界法解决的话,时间复杂度大概是 O(N! * N^2 * logN)。虽然看起来很高,但在实际应用中,它仍然比暴力枚举快得多。

好了,现在是不是对分支限界法有更直观的理解了?想不想试着自己写一个分支限界法的程序?比如试着用队列式或者优先队列式的方法解决TSP问题。反正代码已经写好了,你只需要照抄一遍,就能看到它神奇的魔法!

算法设计与分析第四次作业

8.8.1 基础训练题

1 编写一个使用分枝限界方法生成含n个分量的所有排列的程序。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;void generatePermutations(vector<int>& permutation, vector<bool>& used, int depth) {if (depth == permutation.size()) {// 已经遍历到排列的末尾,输出排列for (int i = 0; i < permutation.size(); i++) {cout << permutation[i] << " ";}cout << endl;} else {// 对于每个未使用的数字,递归生成下一个数字的排列for (int i = 1; i <= permutation.size(); i++) {if (!used[i-1]) {used[i-1] = true;permutation[depth] = i;generatePermutations(permutation, used, depth+1);used[i-1] = false;}}}
}int main() {int n;cout << "请输入排列的长度n: ";cin >> n;vector<int> permutation(n);vector<bool> used(n, false);generatePermutations(permutation, used, 0);return 0;
}

2 编写一个使用分枝限界方法生成n个元素的所有子集的程序

#include <iostream>
#include <vector>using namespace std;void generateSubsets(vector<int>& subset, vector<bool>& used, int depth) {if (depth == subset.size()) {// 已经遍历到子集的末尾,输出子集cout << "{ ";for (int i = 0; i < subset.size(); i++) {if (used[i]) {cout << subset[i] << " ";}}cout << "}" << endl;} else {// 对于每个元素,递归生成下一个元素的子集used[depth] = true;generateSubsets(subset, used, depth+1);used[depth] = false;generateSubsets(subset, used, depth+1);}
}int main() {int n;cout << "请输入集合大小n: ";cin >> n;vector<int> subset(n);for (int i = 0; i < n; i++) {subset[i] = i+1;}vector<bool> used(n, false);generateSubsets(subset, used, 0);return 0;
}

3 分别给出采用队列式分枝限界方法和优先队列式分枝限界方法求解如图所 示的旅行商问题(从0出发)的解空间树和活结点队列的变化过程


4 给出采用优先队列式分枝限界方法求解如图所示的最大团问题解空间树


5 使用一种程序设计语言描述求解旅行商问题(输出最优解)的分枝限界算法, 并分析时间复杂性

#include <iostream>
#include <queue>
using namespace std;const int N = 5;struct Node {int level; // 当前所在的层数int path[N]; // 从根节点到当前节点的路径bool visited[N]; // 标记城市是否已经访问过int bound; // 当前节点的下界int cost; // 当前路径的总代价
};// 定义比较函数,用于优先队列中节点的排序
struct cmp {bool operator()(const Node& a, const Node& b) {return a.bound > b.bound;}
};int get_cost(int graph[][N], int path[], int n) {// 计算路径的总代价int cost = 0;for (int i = 0; i < n - 1; i++) {cost += graph[path[i]][path[i+1]];}cost += graph[path[n-1]][path[0]];return cost;
}void init_node(Node& node, int level) {// 初始化节点node.level = level;for (int i = 0; i < N; i++) {node.visited[i] = false;}
}void print_path(int path[], int n) {// 输出路径for (int i = 0; i < n; i++) {cout << path[i] << " ";}cout << endl;
}void tsp_bnb(int graph[][N]) {// 初始化根节点Node root;init_node(root, 0);root.path[0] = 0; // 从城市0出发root.visited[0] = true;root.bound = get_cost(graph, root.path, 1); // 计算根节点的下界root.cost = 0;// 使用优先队列存储节点priority_queue<Node, vector<Node>, cmp> q;q.push(root);while (!q.empty()) {Node cur = q.top();q.pop();if (cur.bound >= INT_MAX) {// 当前节点的下界已经超过了当前的最优解,可以剪枝continue;}if (cur.level == N-1) {// 已经遍历了所有的城市,找到了一条完整的路径cur.path[cur.level] = 0; // 回到出发城市cur.cost = get_cost(graph, cur.path, N); // 计算路径的总代价if (cur.cost < root.cost) {// 更新最优解root = cur;}continue;}// 枚举下一步可以访问的城市for (int i = 0; i < N; i++) {if (cur.visited[i]) {// 当前城市已经访问过continue;}NodeNode child;init_node(child, cur.level+1);for (int j = 0; j <= cur.level; j++) {child.path[j] = cur.path[j];}child.path[cur.level+1] = i; // 记录下一步访问的城市child.visited[i] = true; // 标记城市已经访问过child.cost = cur.cost + graph[cur.path[cur.level]][i]; // 更新路径的总代价// 计算节点的下界int min_cost = INT_MAX;for (int j = 0; j < N; j++) {if (!child.visited[j] && graph[i][j] < min_cost) {min_cost = graph[i][j];}}child.bound = child.cost + min_cost * (N - child.level - 1);if (child.bound < root.cost) {// 当前节点的下界小于当前的最优解,加入队列继续搜索q.push(child);}}
}// 输出最优解
cout << "最优路径为:" << endl;
print_path(root.path, N);
cout << "路径的总代价为:" << root.cost << endl;
}int main() {
int graph[N][N] = {{0, 10, 15, 20, 25},
{10, 0, 35, 25, 30},
{15, 35, 0, 30, 20},
{20, 25, 30, 0, 18},
{25, 30, 20, 18, 0}};
tsp_bnb(graph);
return 0;
}mathematica
Copy code时间复杂度分析:- 对于每个节点,需要枚举剩余未访问的城市,因此每个节点的分支数为O(N),总共需要遍历O(N!)个节点。
- 对于每个节点,需要计算它的下界,需要遍历剩余未访问的城市,因此计算下界的时间复杂度为O(N^2)。
- 优先队列的插入和删除操作的时间复杂度为O(logN)。
- 因此,总时间复杂度为O(N! * N^2 * logN)。

6 使用一种程序设计语言描述求解最大团问题(输出最优解)的分枝限界算法, 并分析时间复杂性

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>using namespace std;const int N = 100;
int graph[N][N]; // 图的邻接矩阵表示
bool visited[N]; // 当前团中的节点
int max_clique[N]; // 最大团
int max_size; // 最大团大小struct Node {int level; // 当前搜索的深度int size; // 当前团的大小int bound; // 当前节点的下界
};bool operator<(const Node& n1, const Node& n2) {// 优先队列中按照下界从小到大排序return n1.bound > n2.bound;
}void init_node(Node& node, int level, int size) {node.level = level;node.size = size;node.bound = 0;
}void dfs(int cur, int size) {// 在剩余节点中搜索当前团的最大扩展for (int i = cur + 1; i < N; i++) {if (visited[i]) continue;bool flag = true;for (int j = 0; j < size; j++) {if (!graph[i][visited[j]]) {flag = false;break;}}if (flag) {visited[i] = true;dfs(i, size+1);visited[i] = false;}}// 当前团是最大团,更新最大团和最大团大小if (size > max_size) {max_size = size;for (int i = 0; i < size; i++) {max_clique[i] = visited[i];}}
}void maxclique_bnb() {max_size = 0;memset(visited, false, sizeof(visited));memset(max_clique, false, sizeof(max_clique));// 初始化根节点Node root;init_node(root, 0, 0);for (int i = 0; i < N; i++) {root.bound += graph[i][i+1];}// 优先队列存储活结点priority_queue<Node> q;q.push(root);while (!q.empty()) {Node cur = q.top();q.pop();if (cur.bound <= max_size) {// 当前节点的下界小于等于当前最大团大小,不需要搜索下去continue;}if (cur.level == N) {// 已经遍历完了所有节点,更新最大团max_size = cur.size;for (int i = 0; i < N; i++) {max_clique[i] = visited[i];}continue;}// 枚举当前节点的子节点Node child;init_node(child, cur.level+1, cur.size);for (int i = N-1; i >= cur.level; i--) {// 从N-1到cur.level,按照节点编号从大到小排序// 优先// 搜索的是当前节点的子节点,不包括父节点和父节点之前已经遍历过的兄弟节点if (graph[i][i+1] && !visited[i] &&i > cur.level && (cur.level == 0 || graph[i][visited[cur.level-1]])) {// 当前节点可行,计算子节点的下界child.bound = cur.bound - 1;for (int j = i+1; j < N; j++) {if (graph[i][j] && !visited[j]) {child.bound--;}}if (child.bound > max_size) {// 子节点的下界大于当前最大团大小,将子节点加入优先队列q.push(child);}}}// 不选择当前节点Node child2;init_node(child2, cur.level+1, cur.size);child2.bound = cur.bound - graph[cur.level][cur.level+1];if (child2.bound > max_size) {// 将不选择当前节点的子节点加入优先队列q.push(child2);}// 标记当前节点v