算法设计与分析第四次作业
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);}// 标记当前节点visited[cur.level] = true;dfs(cur.level, cur.size+1);visited[cur.level] = false;
}
int main() {
// 构造图的邻接矩阵表示
memset(graph, 0, sizeof(graph));
graph[0][1] = graph[1][0] = 1;
graph[0][2] = graph[2][0] = 1;
graph[0][3] = graph[3][0] = 1;
graph[0][4] = graph[4][0] = 1;
graph[1][2] = graph[2][1] = 1;
graph[1][3] = graph[3][1] = 1;
graph[1][4] = graph[4][1] = 1;
graph[2][3] = graph[3][2] = 1;
graph[2][4] = graph[4][2] = 1;
graph[3][4] = graph[4][3] = 1;maxclique_bnb();cout << "Max clique size: " << max_size << endl;
cout << "Max clique nodes: ";
for (int i = 0; i < N; i++) {if (max_clique[i]) {cout << i << " ";}
}
cout << endl;return 0;
时间复杂度分析：对于最大团问题的分枝限界算法，每次搜索时可以通过剪枝减少大量的搜索空间，因此时间复杂度不会很高，但仍然是指数级别的。具体来说，如果使用深度优先搜索，时间复杂度为 $O(2^n)$，其中 $n$ 为节点数量，因为每个节点都有选或不选两种情况。如果使用优先队列优化的分枝限界算法，时间复杂度可以得到一定程度的优化。假设优先队列
7 使用一种程序设计语言描述求解子集和问题（输出所有解）的分枝限界算法， 并分析时间复杂性
#include <iostream>
#include <vector>
using namespace std;void printSolution(const vector<int>& sol) {for (int i = 0; i < sol.size(); i++) {if (sol[i] == 1) {cout << i + 1 << " ";}}cout << endl;
}void subsetSum(vector<int>& nums, int targetSum, vector<int>& path, int depth, int remainingSum) {if (remainingSum < 0) {return;}if (depth == nums.size()) {if (remainingSum == 0) {printSolution(path);}return;}// include current elementpath.push_back(1);subsetSum(nums, targetSum, path, depth + 1, remainingSum - nums[depth]);path.pop_back();// exclude current elementpath.push_back(0);subsetSum(nums, targetSum, path, depth + 1, remainingSum);path.pop_back();
}int main() {vector<int> nums = {10, 7, 5, 18, 12, 20, 15};int targetSum = 35;vector<int> path;int remainingSum = 0;for (int num : nums) {remainingSum += num;}subsetSum(nums, targetSum, path, 0, remainingSum);return 0;
}
8.8.2 实验题
1 使用一种程序设计语言描述求解Hamilton回路问题（输出所有Hamilton回 路）的分枝限界算法，并分析时间复杂性
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 20;int n; // 图中顶点的数量
int graph[MAXN][MAXN]; // 图的邻接矩阵
vector<int> path; // 当前的解
bool visited[MAXN]; // 记录每个顶点是否被访问过void printSolution(const vector<int>& sol) {for (int i = 0; i < sol.size(); i++) {cout << sol[i] << " ";}cout << endl;
}bool isValid(int vertex, int pos) {// 如果当前顶点已经在解中出现过，则不合法if (visited[vertex]) {return false;}// 如果当前顶点和上一个顶点之间没有边相连，则不合法if (pos > 0 && graph[path[pos - 1]][vertex] == 0) {return false;}// 如果当前顶点是起点，但是还没有遍历完所有的顶点，则不合法if (pos == n - 1 && graph[vertex][path[0]] == 0) {return false;}return true;
}void hamiltonianCircuit(int pos) {if (pos == n) {if (graph[path[pos - 1]][path[0]] == 1) {printSolution(path);}return;}for (int vertex = 1; vertex < n; vertex++) {if (isValid(vertex, pos)) {path.push_back(vertex);visited[vertex] = true;hamiltonianCircuit(pos + 1);path.pop_back();visited[vertex] = false;}}
}int main() {// 初始化图的邻接矩阵memset(graph, 0, sizeof(graph));graph[0][1] = graph[1][0] = 1;graph[0][2] = graph[2][0] = 1;graph[1][2] = graph[2][1] = 1;graph[1][3] = graph[3][1] = 1;graph[2][3] = graph[3][2] = 1;graph[2][4] = graph[4][2] = 1;graph[3][4] = graph[4][3] = 1;graph[3][5] = graph[5][3] = 1;graph[4][5] = graph[5][4] = 1;n = 6;path.push_back(0);visited[0] = true;hamiltonianCircuit(1);return 0;
}
在这个算法中，我们使用回溯法实现了分枝限界算法。我们首先将起点加入到解中，并将起点标记为已访问。在搜索的过程中，我们维护一个 path 数组，表示当前的解。对于每个顶点，我们都有多个选择：将其包含在解中或不包含在解中。因此，我们可以使用回溯法来递归地搜索所有可能的解。在递归的过程中，我们可以使用剪枝技巧来提高搜索的效率。具体来说，如果当前的解已经包含了所有的顶点，则可以检查最后一个顶点是否和起点相邻，如果相邻，则找到一个 Hamilton 回路。如果当前的解已经超过了所有的顶点，则可以直接返回。如果当前的解已经不可能找到一个 Hamilton 回路，则可以剪枝回溯。时间复杂性分析：Hamilton 回路问题是一个 NP 完全问题，因此不存在多项式时间算法可以解决该问题。分枝限界算法的时间复杂度取决于搜索树的大小。在最坏情况下，搜索树的大小为 n!，因此时间复杂度为 O(n!)。但是，在实际情况中，使用剪枝技巧可以将搜索树的大小大大减小，从而提高搜索效率。因此，分枝限界算法的时间复杂度是具有一定不确定性的。
2 使用分枝限界方法求解Hamilton回路问题，要求只输出一条Hamilton回路， 或报告不存在Hamilton回路
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 20;int n; // 图中顶点的数量
int graph[MAXN][MAXN]; // 图的邻接矩阵
vector<int> path; // 当前的解
bool visited[MAXN]; // 记录每个顶点是否被访问过void printSolution(const vector<int>& sol) {for (int i = 0; i < sol.size(); i++) {cout << sol[i] << " ";}cout << endl;
}bool isValid(int vertex, int pos) {// 如果当前顶点已经在解中出现过，则不合法if (visited[vertex]) {return false;}// 如果当前顶点和上一个顶点之间没有边相连，则不合法if (pos > 0 && graph[path[pos - 1]][vertex] == 0) {return false;}// 如果当前顶点是起点，但是还没有遍历完所有的顶点，则不合法if (pos == n - 1 && graph[vertex][path[0]] == 0) {return false;}return true;
}void hamiltonianCircuit(int pos) {if (pos == n) {if (graph[path[pos - 1]][path[0]] == 1) {printSolution(path);}return;}for (int vertex = 1; vertex < n; vertex++) {if (isValid(vertex, pos)) {path.push_back(vertex);visited[vertex] = true;hamiltonianCircuit(pos + 1);path.pop_back();visited[vertex] = false;}}
}int main() {// 初始化图的邻接矩阵memset(graph, 0, sizeof(graph));graph[0][1] = graph[1][0] = 1;graph[0][2] = graph[2][0] = 1;graph[1][2] = graph[2][1] = 1;graph[1][3] = graph[3][1] = 1;graph[2][3] = graph[3][2] = 1;graph[2][4] = graph[4][2] = 1;graph[3][4] = graph[4][3] = 1;graph[3][5] = graph[5][3] = 1;graph[4][5] = graph[5][4] = 1;n = 6;path.push_back(0);visited[0] = true;hamiltonianCircuit(1);return 0;
}
3 使用一种程序设计语言描述求解0/1背包问题（输出最优解）的分枝限界算 法，并分析时间复杂性
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct Item {int weight; // 物品的重量int value; // 物品的价值
};bool compareByRatio(const Item& a, const Item& b) {double ratio_a = (double)a.value / (double)a.weight;double ratio_b = (double)b.value / (double)b.weight;return ratio_a > ratio_b;
}int knapsack(int capacity, const vector<Item>& items) {int n = items.size();// 根据单位价值排序vector<Item> sorted_items = items;sort(sorted_items.begin(), sorted_items.end(), compareByRatio);// 初始化最优解int best_value = 0;vector<bool> best_solution(n, false);// 初始化当前解int current_value = 0;int current_weight = 0;vector<bool> current_solution(n, false);// 初始化堆栈vector<int> stack;stack.push_back(-1);while (!stack.empty()) {int last_item_index = stack.back();stack.pop_back();// 遍历下一个物品int next_item_index = last_item_index + 1;if (next_item_index == n) {// 检查当前解是否是最优解if (current_value > best_value) {best_value = current_value;best_solution = current_solution;}continue;}// 不选下一个物品stack.push_back(next_item_index);// 选下一个物品if (current_weight + sorted_items[next_item_index].weight <= capacity) {current_weight += sorted_items[next_item_index].weight;current_value += sorted_items[next_item_index].value;current_solution[next_item_index] = true;double upper_bound = current_value;int remaining_capacity = capacity - current_weight;for (int i = next_item_index + 1; i < n; i++) {if (sorted_items[i].weight <= remaining_capacity) {remaining_capacity -= sorted_items[i].weight;upper_bound += sorted_items[i].value;} else {upper_bound += (double)remaining_capacity / (double)sorted_items[i].weight * sorted_items[i].value;break;}}if (upper_bound > best_value) {stack.push_back(next_item_index);}current_weight -= sorted_items[next_item_index].weight;current_value -= sorted_items[next_item_index].value;current_solution[next_item_index] = false;}}// 输出最优解for (int i = 0; i < n; i++) {if (best_solution[i]) {cout << i << " ";}}cout << endl;return best_value;
}int main() {int capacity = 10;vector<Item> items = {{2, 6},{2, 10},{3, 12},{4, 14},{5, 18}};int value = knapsack(capacity, items);cout << "max value: " << value << endl;return 0;
}
4 使用分枝限界方法求解子集和问题，要求只输出一个满足条件的子集，或报 告不存在满足条件的子集
#include <iostream>
#include <vector>
using namespace std;bool subsetSum(const vector<int>& nums, int target, vector<int>& solution) {int n = nums.size();// 初始化堆栈vector<int> stack;stack.push_back(-1);while (!stack.empty()) {int last_index = stack.back();stack.pop_back();// 遍历下一个元素int next_index = last_index + 1;if (next_index == n) {// 检查当前解是否符合条件int sum = 0;for (int i = 0; i < n; i++) {if (solution[i] == 1) {sum += nums[i];}}if (sum == target) {return true;}continue;}// 不选下一个元素stack.push_back(next_index);// 选下一个元素solution[next_index] = 1;stack.push_back(next_index);// 回溯solution[next_index] = 0;}return false;
}int main() {vector<int> nums = {3, 1, 2, 8, 7, 5};int target = 14;vector<int> solution(nums.size(), 0);bool found = subsetSum(nums, target, solution);if (found) {cout << "subset found: ";for (int i = 0; i < nums.size(); i++) {if (solution[i] == 1) {cout << nums[i] << " ";}}cout << endl;} else {cout << "no subset found" << endl;}return 0;
}
5 请使用分枝限界方法为一个需要着色的无向图选取一种颜色数目最少的着 色方案
请使用分枝限界方法为一个需要着色的无向图选取一种颜色数目最少的着色方案
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;// 无向图结构体
struct Graph {int V; // 顶点数vector<unordered_set<int>> adj; // 邻接表Graph(int V) : V(V), adj(V) {}void addEdge(int u, int v) {adj[u].insert(v);adj[v].insert(u);}
};// 检查当前节点的颜色是否与相邻节点的颜色冲突
bool isSafe(const Graph& g, const vector<int>& colors, int node, int color) {for (int neighbor : g.adj[node]) {if (colors[neighbor] == color) {return false;}}return true;
}// 使用分枝限界法为无向图着色
void colorGraph(const Graph& g, vector<int>& colors, int& minColors) {int n = g.V;// 初始化堆栈vector<pair<int, int>> stack; // (node, color)stack.push_back(make_pair(-1, 0));while (!stack.empty()) {pair<int, int> last_node_color = stack.back();stack.pop_back();// 遍历下一个节点int next_node = last_node_color.first + 1;if (next_node == n) {// 检查当前解是否符合条件int max_color = 0;for (int i = 0; i < n; i++) {max_color = max(max_color, colors[i]);}if (max_color < minColors) {minColors = max_color;}continue;}// 尝试每种颜色for (int color = 1; color <= n; color++) {if (isSafe(g, colors, next_node, color)) {colors[next_node] = color;stack.push_back(make_pair(next_node, color));colors[next_node] = 0;}}}
}int main() {Graph g(5);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(2, 3);g.addEdge(3, 4);vector<int> colors(g.V, 0);int minColors = g.V + 1;colorGraph(g, colors, minColors);cout << "Minimum number of colors required: " << minColors << endl;return 0;
}
9.6.1
1 用随机方法改写快速排序程序和基于划分的选择程序
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;// 交换两个元素
void swap(int& a, int& b) {int temp = a;a = b;b = temp;
}// 选取基准元素并将其放在正确的位置上
int partition(int arr[], int low, int high) {// 选取随机位置上的元素作为基准元素int randomIndex = low + rand() % (high - low + 1);swap(arr[randomIndex], arr[high]);int pivot = arr[high];int i = low - 1;for (int j = low; j <= high - 1; j++) {if (arr[j] <= pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return i + 1;
}// 随机化快速排序
void quicksort(int arr[], int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quicksort(arr, low, pivot - 1);quicksort(arr, pivot + 1, high);}
}int main() {srand(time(NULL));int arr[] = {3, 5, 1, 7, 2, 8, 4, 6};int n = sizeof(arr) / sizeof(arr[0]);quicksort(arr, 0, n - 1);for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return 0;
}#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;// 交换两个元素
void swap(int& a, int& b) {int temp = a;a = b;b = temp;
}// 选取基准元素并将其放在正确的位置上
int partition(int arr[], int low, int high) {// 选取随机位置上的元素作为基准元素int randomIndex = low + rand() % (high - low + 1);swap(arr[randomIndex], arr[high]);int pivot = arr[high];int i = low - 1;for (int j = low; j <= high - 1; j++) {if (arr[j] <= pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[high]);return i + 1;
}// 基于划分的选择算法
int select(int arr[], int low, int high, int k) {if (low == high) {return arr[low];}int pivot = partition(arr, low, high);int rank = pivot - low + 1;if (k == rank) {return arr[pivot];} else if (k < rank) {return select(arr, low, pivot - 1, k);} else {return select(arr, pivot + 1, high, k - rank);}
}int main() {srand(time(NULL));int arr[] = {3, 5, 1, 7, 2, 8, 4, 6};int n = sizeof(arr) / sizeof(arr[0]);int k = 3;int kthSmallest = select(arr, 0, n - 1, k);cout << k << "-th smallest element is " << kthSmallest << endl;return 0;
}
2 请写出随机洗牌算法的程序
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;void shuffle(vector<int>& cards) {int n = cards.size();for (int i = n - 1; i > 0; i--) {int j = rand() % (i + 1);swap(cards[i], cards[j]);}
}int main() {srand(time(NULL));vector<int> cards = {1, 2, 3, 4, 5};shuffle(cards);for (int card : cards) {cout << card << " ";}cout << endl;return 0;
}
3 请为旅行商问题（是否存在耗费不超过t的旅行）设计一个拉斯维加斯算法
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;const int INF = 1e9;// 生成随机解
vector<int> randomSolution(int n) {vector<int> solution(n);for (int i = 0; i < n; i++) {solution[i] = i;}random_shuffle(solution.begin(), solution.end());return solution;
}// 计算路径长度
int calculateDistance(const vector<vector<int>>& graph, const vector<int>& solution) {int distance = 0;int n = solution.size();for (int i = 0; i < n - 1; i++) {distance += graph[solution[i]][solution[i + 1]];}distance += graph[solution[n - 1]][solution[0]];return distance;
}// 拉斯维加斯算法
vector<int> tspLasVegas(const vector<vector<int>>& graph, int t) {int n = graph.size();vector<int> bestSolution;int bestDistance = INF;int startTime = time(NULL);while (time(NULL) - startTime < t) {vector<int> solution = randomSolution(n);int distance = calculateDistance(graph, solution);if (distance < bestDistance) {bestDistance = distance;bestSolution = solution;}}return bestSolution;
}int main() {srand(time(NULL));// 构造一个5个城市的图vector<vector<int>> graph = {{0, 2, 9, 10, 5},{2, 0, 6, 4, 8},{9, 6, 0, 7, 1},{10, 4, 7, 0, 3},{5, 8, 1, 3, 0}};int t = 1; // 时间限制为1秒vector<int> solution = tspLasVegas(graph, t);int distance = calculateDistance(graph, solution);cout << "Best solution: ";for (int city : solution) {cout << city << " ";}cout << endl;cout << "Distance: " << distance << endl;return 0;
}
4 请为0/1背包问题（是否存在效益和不少于t的装包方式）设计一个拉斯维加 斯算法
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;const int INF = 1e9;// 生成随机解
vector<int> randomSolution(int n) {vector<int> solution(n);for (int i = 0; i < n; i++) {solution[i] = rand() % 2;}return solution;
}// 背包问题的价值函数
int knapsackValue(const vector<int>& weights, const vector<int>& values, const vector<int>& solution, int capacity) {int n = weights.size();int value = 0;for (int i = 0; i < n; i++) {if (solution[i] == 1) {capacity -= weights[i];if (capacity < 0) {return -INF;}value += values[i];}}return value;
}// 拉斯维加斯算法
vector<int> knapsackLasVegas(const vector<int>& weights, const vector<int>& values, int capacity, int t) {int n = weights.size();vector<int> bestSolution;int bestValue = -INF;int startTime = time(NULL);while (time(NULL) - startTime < t) {vector<int> solution = randomSolution(n);int value = knapsackValue(weights, values, solution, capacity);if (value > bestValue) {bestValue = value;bestSolution = solution;}}return bestSolution;
}int main() {srand(time(NULL));// 构造一个5个物品的背包问题vector<int> weights = {2, 3, 4, 5, 6};vector<int> values = {3, 4, 5, 6, 7};int capacity = 10; // 背包容量为10int t = 1; // 时间限制为1秒vector<int> solution = knapsackLasVegas(weights, values, capacity,
5 请利用费马小定理构造素数测试的概率算法。
费马小定理是一个用于判断一个数是否为素数的方法。其基本思想是，对于任意一个素数p和整数a，a^p mod p等于a。也就是说，如果对于一个数n，随机选取一个整数a，如果a^(n-1) mod n不等于1，则n一定不是素数；如果a^(n-1) mod n等于1，则n可能是素数，但不一定是素数。
基于这个思想，可以构造一个概率算法，称为费马-米勒素数测试（Fermat-Miller Primality Test）。该算法的基本思路如下：
- 随机选取一个整数a，使得1 < a < n-1。
- 计算a^(n-1) mod n的值。
- 如果a^(n-1) mod n不等于1，则n一定不是素数，可以直接返回结果。
- 如果a^(n-1) mod n等于1，则需要进行进一步的测试。
- 选取一个整数k，使得n-1可以表示为2^r * k的形式，其中r和k都是正整数，且k为奇数。
- 对于i从1到r，计算a(2(i-1) * k) mod n的值。
- 如果存在一个i使得a(2(i-1) * k) mod n等于n-1，则n可能是素数，但不一定是素数。
- 如果对于所有的i，a(2(i-1) * k) mod n都不等于n-1，则n一定不是素数。
该算法的正确性基于费马小定理和欧拉定理。该算法的时间复杂度为O(k * log^3(n))，其中k是测试次数。一般来说，k的值取15到20即可满足要求。
以下是C++代码实现：
#include <iostream>
#include <cstdlib>
#include <cmath>using namespace std;int power(int x, int y, int p)
{int res = 1;x = x % p;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;
}bool isPrime(int n, int k)
{if (n <= 1 || n == 4) return false;if (n <= 3) return true;while (k > 0){int a = 2 + rand()%(n-4);if (power(a, n-1, n) != 1)return false;int d = n-1;while (d % 2 == 0)d /= 2;int x = power(a, d, n);if (x == 1 || x == n-1)continue;for (int i = 0; i < d-1; i++){x = (x*x) % n;if (x == 1)return false;if (x == n-1)break;}if (x != n-1)return false;k--;}return true;
}int main()
{int n = 23;int k = 15;if (isPrime(n, k))cout << n << " is prime" << endl;elsecout << n << " is not prime" << endl;return 0;
}
在上面的代码中，isPrime函数用于判断一个数是否为素数，n是待判断的数，k是测试次数。函数中先判断了一些特殊情况，然后随机选取整数a，使用费马小定理判断n是否为素数。如果不是素数，则直接返回结果。如果是素数，则进行进一步的测试，即检查a(2(i-1) * k) mod n是否等于n-1。如果存在一个i使得a(2(i-1) * k) mod n等于n-1，则n可能是素数，但不一定是素数。如果对于所有的i，a(2(i-1) * k) mod n都不等于n-1，则n一定不是素数。
9.6.2
实验题
1 请为Hamilton回路问题（是否有Hamilton回路）设计一个拉斯维加斯算法
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>using namespace std;const int MAXN = 20; // 最大顶点数
int n; // 顶点数
int g[MAXN][MAXN]; // 邻接矩阵// 随机生成一个顶点序列
vector<int> random_permutation() {vector<int> perm(n);for (int i = 0; i < n; i++) {perm[i] = i;}shuffle(perm.begin(), perm.end(), default_random_engine());return perm;
}// 检查是否存在Hamilton回路
bool check_hamilton_loop(const vector<int>& perm) {for (int i = 0; i < n - 1; i++) {if (g[perm[i]][perm[i+1]] == 0) {return false;}}if (g[perm[n-1]][perm[0]] == 0) {return false;}return true;
}// 拉斯维加斯算法
bool hamilton_loop() {// 随机生成多个顶点序列进行检查const int MAX_ITERATIONS = 1000;for (int i = 0; i < MAX_ITERATIONS; i++) {vector<int> perm = random_permutation();if (check_hamilton_loop(perm)) {return true;}}return false;
}int main() {// 读入图的邻接矩阵cin >> n;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> g[i][j];}}// 检查是否存在Hamilton回路if (hamilton_loop()) {cout << "存在Hamilton回路" << endl;} else {cout << "不存在Hamilton回路" << endl;}return 0;
}
2 请为皇后问题（是否有解）设计一个拉斯维加斯算法
#include <iostream>
#include <vector>
#include <random>using namespace std;const int MAXN = 100; // 最大皇后数
int n; // 皇后数
int column[MAXN]; // 每行皇后所在的列// 检查是否存在冲突
bool conflict(int row, int col) {for (int i = 0; i < row; i++) {if (column[i] == col || row - i == abs(col - column[i])) {return true;}}return false;
}// 随机生成一个初始解
void random_initialization() {for (int i = 0; i < n; i++) {column[i] = rand() % n;}
}// 拉斯维加斯算法
bool queens() {const int MAX_ITERATIONS = 1000;for (int i = 0; i < MAX_ITERATIONS; i++) {random_initialization();bool is_valid = true;for (int j = 0; j < n; j++) {// 随机选择一列进行移动int col = rand() % n;if (!conflict(j, col)) {column[j] = col;} else {is_valid = false;break;}}if (is_valid) {return true;}}return false;
}int main() {// 读入皇后数cin >> n;// 检查是否存在解if (queens()) {cout << "存在皇后放置方案" << endl;} else {cout << "不存在皇后放置方案" << endl;}return 0;
}
3 请为子集和问题（是否存在和为t的子集）设计一个拉斯维加斯算法
#include <iostream>
#include <vector>
#include <random>using namespace std;const int MAXN = 100; // 最大元素数
int n; // 元素数
int a[MAXN]; // 元素值
int t; // 目标和// 检查是否存在和为t的子集
bool check_subset_sum() {// 随机生成一个01序列，用于表示当前的子集vector<int> subset(n);for (int i = 0; i < n; i++) {subset[i] = rand() % 2;}// 检查当前子集的和是否为tint sum = 0;for (int i = 0; i < n; i++) {if (subset[i] == 1) {sum += a[i];}}return sum == t;
}// 拉斯维加斯算法
bool subset_sum() {const int MAX_ITERATIONS = 1000;for (int i = 0; i < MAX_ITERATIONS; i++) {if (check_subset_sum()) {return true;}}return false;
}int main() {// 读入元素数和目标和cin >> n >> t;// 读入元素值for (int i = 0; i < n; i++) {cin >> a[i];}// 检查是否存在和为t的子集if (subset_sum()) {cout << "存在和为" << t << "的子集" << endl;} else {cout << "不存在和为" << t << "的子集" << endl;}return 0;
}
4 请为团问题（是否存在顶点数不小于k的团）设计一个拉斯维加斯算法
#include <iostream>
#include <vector>
#include <random>using namespace std;const int MAXN = 100; // 最大顶点数
int n; // 顶点数
int g[MAXN][MAXN]; // 图的邻接矩阵
int k; // 团的大小下限// 检查是否存在顶点数不小于k的团
bool check_clique() {// 随机选择一个顶点作为团的起点int start = rand() % n;// 初始化团vector<int> clique;clique.push_back(start);// 逐步扩展团for (int i = 0; i < n; i++) {if (i == start) {continue;}bool is_clique = true;for (int v : clique) {if (g[v][i] == 0) {is_clique = false;break;}}if (is_clique) {clique.push_back(i);if (clique.size() >= k) {return true;}}}return false;
}// 拉斯维加斯算法
bool clique() {const int MAX_ITERATIONS = 1000;for (int i = 0; i < MAX_ITERATIONS; i++) {if (check_clique()) {return true;}}return false;
}int main() {// 读入顶点数和团的大小下限cin >> n >> k;// 读入图的邻接矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> g[i][j];}}// 检查是否存在顶点数不小于k的团if (clique()) {cout << "存在顶点数不小于" << k << "的团" << endl;} else {cout << "不存在顶点数不小于" << k << "的团" << endl;}return 0;
}
5 请使用概率方法设计一个判断一个给定的整数函数f(x)是否恒等于0的蒙特 卡洛算法，并使用一种程序设计语言描述该算法，其C/C++的函数原型为“bool iszero(int f(int), int n);”，其中n表示最多进行n次比较后给出答案
#include <iostream>
#include <random>using namespace std;// 判断函数f是否恒等于0，最多进行n次比较
bool iszero(int (*f)(int), int n) {// 随机生成n个整数，作为函数的参数random_device rd;mt19937 gen(rd());uniform_int_distribution<> dis(-1000, 1000);for (int i = 0; i < n; i++) {int x = dis(gen);if (f(x) != 0) {return false;}}return true;
}// 测试函数，判断一个整数是否为偶数
int is_even(int x) {return x % 2;
}int main() {// 测试is_even函数是否恒等于0if (iszero(is_even, 1000)) {cout << "is_even函数恒等于0" << endl;} else {cout << "is_even函数不恒等于0" << endl;}return 0;
}
在上述代码中，我们首先随机生成n个整数，作为函数f的参数。然后对于每个参数，计算f(x)的值。如果存在一个参数使得f(x)不等于0，则说明函数f不恒等于0，返回false。如果所有参数都满足f(x)等于0，则说明函数f恒等于0，返回true。重复的次数n可以根据实际情况进行调整。
这个算法的随机性主要体现在随机生成函数的参数的过程中。每次生成的参数都是随机的，因此每次算法运行的结果都有可能不同。这种随机性可以增加算法的全局搜索能力，从而减少算法陷入局部最优解的风险。