目录1.a.对于本节中做到一半的4皇后问题继续使用回溯查找以求得该问题的第二个解。b.请解释一下如何利用棋盘的对称性求得4皇后问题的第二个解。2.a. 5皇后问题的哪一个解是回溯算法求得的最后一个解。b.利用棋盘的对称性至少再求出该问题的4个解。3.a.任选一种语言实现n皇后问题的回溯算法。对一系列n值运行该程序以得到该算法的状态空间树中的节点数。拿这些值和该问题的穷举查找算法所生成的候选解的数量进行比较(参见习题3.4的第9题)。b.对于a中调用程序的每一个n值用12.1节描述的方法估计状态空间树的规模并且拿这些估计值和实际获得的值做比较。4.对于任意n≥4设计一个可以在线性时间内求解n皇后问题的算法。5.用回溯法对下图求哈密顿回路问题。6.对图12.3(a)应用回溯法求解3色问题。7.用回溯法生成{1,2,3,4}的所有排列。8.a.应用回溯法对“子集和”问题的下面实例求解 A{1,3,4,5}, d11。b.如果我们只使用两个不等式中的一个来判定没有希望的节点这个回溯算法能够正确工作吗9.本节给出的回溯算法的通用模板只有在没有一个解是另一个解的前缀的情况下才能正常工作。修改这个伪代码使它在无此约束的情况下也能正确工作。10.对于下面的问题写一个程序实现它的回溯算法a.哈密顿回路问题。b. m色问题。11.插棒游戏 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始的时候如下图所示除了一个孔所有孔都插上了插棒。一个插棒可以跳过它的直接邻居移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法求解该谜题的下列版本a.已知空孔的位置求出消去13个插棒的最短步骤对剩下的插棒的最终位置不限。b.已知空孔的位置求出消去13个插棒的最短步骤剩下的插棒最终要落在最初的空孔上。1.a.对于本节中做到一半的4皇后问题继续使用回溯查找以求得该问题的第二个解。继续回溯的步骤就是-4,4回滚3,1回滚2,4回滚1,2回滚 第一行选择3第二行选择1第三行选择4第四行选择2b.请解释一下如何利用棋盘的对称性求得4皇后问题的第二个解。通过中垂线反射对称取位置2.a. 5皇后问题的哪一个解是回溯算法求得的最后一个解。从最后一行向上向左回溯得到的第一个解就是正常的最后一个解b.利用棋盘的对称性至少再求出该问题的4个解。对第3行进行反射对第3列进行反射从主对角线反射副对角线反射一共四个解3.a.任选一种语言实现n皇后问题的回溯算法。对一系列n值运行该程序以得到该算法的状态空间树中的节点数。拿这些值和该问题的穷举查找算法所生成的候选解的数量进行比较(参见习题3.4的第9题)。#include stdio.h #include stdlib.h #include math.h int nodeCount 0; // 状态空间树节点总数 int n; // 皇后数量 int *cols; // 记录每一行皇后所在列 // 检查在 row 行 col 列放皇后是否合法 int isSafe(int row, int col) { for (int i 0; i row; i) { if (cols[i] col || abs(i - row) abs(cols[i] - col)) { return 0; } } return 1; } // 回溯算法 void backtrack(int row) { if (row n) { return; } for (int col 0; col n; col) { nodeCount; // 每尝试一个位置 一个节点 if (isSafe(row, col)) { cols[row] col; backtrack(row 1); } } } // 计算 n^n穷举法候选解数量 long long bruteForce(int n) { long long res 1; for (int i 0; i n; i) { res * n; } return res; } int main() { printf(n\t回溯节点数\t穷举候选解数(n^n)\n); printf(----------------------------------------\n); // 测试 n4 ~ n8 for (n 4; n 8; n) { nodeCount 0; cols (int*)malloc(n * sizeof(int)); backtrack(0); long long brute bruteForce(n); printf(%d\t%d\t\t%lld\n, n, nodeCount, brute); free(cols); } return 0; }b.对于a中调用程序的每一个n值用12.1节描述的方法估计状态空间树的规模并且拿这些估计值和实际获得的值做比较。估计值≈n*(n-2)*(n-4)*...实际上n实际节点数教材 12.1 估计值4161855360615217075516108205622404.对于任意n≥4设计一个可以在线性时间内求解n皇后问题的算法。我们把数字分成偶数和奇数两类情况 1n 是偶数且n ≠ 6k2如 n4,8,10,14...规则先放偶数列2,4,6,...,n再放奇数列1,3,5,...,n-1例子n8列顺序2,4,6,8,1,3,5,7情况 2n 是偶数且n 6k2如 n2,6,14... 只需要 n≥4 → n6,14...规则放n/2, n/22, ..., n放2,4,...,n/2-2放n/23, n/25,...,n-1放1,3,...,n/21例子n6列顺序3,5,1,4,6,2情况 3n 是奇数n≥5把 n 变成n-1偶数按偶数规则放最后一行放第 n 列。这样就只需要一次循环生成列号O(n)线性时间5.用回溯法对下图求哈密顿回路问题。以a为起点开始遍历假设按字典序选择下一个点再从b开始选d、f、c发现不通开始回溯到f点选择g、e再次回溯到d先遍历g但是会再次失败直到从e开始遍历最终得到结果6.对图12.3(a)应用回溯法求解3色问题。7.用回溯法生成{1,2,3,4}的所有排列。8.a.应用回溯法对“子集和”问题的下面实例求解 A{1,3,4,5}, d11。也就是无解b.如果我们只使用两个不等式中的一个来判定没有希望的节点这个回溯算法能够正确工作吗算法仍然可以正确工作但状态空间树将包含比必要更多的节点。9.本节给出的回溯算法的通用模板只有在没有一个解是另一个解的前缀的情况下才能正常工作。修改这个伪代码使它在无此约束的情况下也能正确工作。算法 Backtrack(X[1..i]) //输入X[1..i]确定了一个解的前面i个有希望的分量 //输出代表问题的解的所有元组 if X[1..i]是一个解 write X[1..i] for 和X[1..i]以及约束相容的每一个元素 x∈S_(i1) do X[i1]←x Backtrack(X[1..i1])10.对于下面的问题写一个程序实现它的回溯算法a.哈密顿回路问题。#include stdio.h #define MAX 10 int n; // 顶点数 int graph[MAX][MAX]; // 邻接矩阵 int path[MAX]; // 保存回路 // 检查顶点 v 是否能加入路径 int isSafe(int v, int pos, int path[]) { // 相邻 if (graph[path[pos-1]][v] 0) return 0; // 是否已经在路径里 for (int i 0; i pos; i) if (path[i] v) return 0; return 1; } // 回溯 int hamCycle(int pos) { // 所有顶点都加入了 if (pos n) { // 最后一个点和起点相连 if (graph[path[pos-1]][path[0]] 1) return 1; else return 0; } // 尝试所有顶点 for (int v 1; v n; v) { if (isSafe(v, pos, path)) { path[pos] v; if (hamCycle(pos1) 1) return 1; path[pos] -1; // 回溯 } } return 0; } void printPath() { printf(哈密顿回路); for (int i 0; i n; i) printf(%d , path[i]); printf(%d\n, path[0]); } int main() { // 示例 n 5; int g[5][5] { {0,1,0,1,0}, {1,0,1,1,1}, {0,1,0,0,1}, {1,1,0,0,1}, {0,1,1,1,0} }; for (int i0; in; i) for (int j0; jn; j) graph[i][j] g[i][j]; path[0] 0; if (hamCycle(1) 1) printPath(); else printf(无哈密顿回路\n); return 0; }b. m色问题。#include stdio.h #define MAX 10 int n, m; int graph[MAX][MAX]; int color[MAX]; // 检查顶点 v 能否涂 c 色 int isSafe(int v, int c) { for (int i 0; i n; i) if (graph[v][i] c color[i]) return 0; return 1; } // 回溯着色 int mColoring(int v) { // 全部着色完成 if (v n) return 1; // 尝试所有颜色 for (int c 1; c m; c) { if (isSafe(v, c)) { color[v] c; if (mColoring(v1) 1) return 1; color[v] 0; // 回溯 } } return 0; } void printColors() { printf(着色方案); for (int i 0; i n; i) printf(%d , color[i]); printf(\n); } int main() { // 示例图 n 4; m 3; int g[4][4] { {0,1,1,1}, {1,0,1,0}, {1,1,0,1}, {1,0,1,0} }; for (int i0; in; i) for (int j0; jn; j) graph[i][j] g[i][j]; if (mColoring(0) 1) printColors(); else printf(无法用 %d 种颜色着色\n, m); return 0; }11.插棒游戏 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始的时候如下图所示除了一个孔所有孔都插上了插棒。一个插棒可以跳过它的直接邻居移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法求解该谜题的下列版本a.已知空孔的位置求出消去13个插棒的最短步骤对剩下的插棒的最终位置不限。backtrack(board, count, steps): if count 2: 更新最小步数 return if steps minSteps: return for 每一个位置 i 0..14: if board[i] 1: for 每一个 i 能跳的方向 (i→j→k): if board[j]1 且 board[k]0: // 做移动 board[i] 0 board[j] 0 board[k] 1 backtrack(board, count-1, steps1) // 回溯 board[i] 1 board[j] 1 board[k] 0b.已知空孔的位置求出消去13个插棒的最短步骤剩下的插棒最终要落在最初的空孔上。// 15个位置 int board[15]; // 每个点能跳的方向{from, over, to} int moves[][3] { {0,1,3}, {0,2,5}, {1,3,6}, {1,4,8}, // ... 所有合法跳跃方向 }; int minSteps 999; void backtrack(int count, int steps) { // a 问结束条件 if (count 2) { if (steps minSteps) minSteps steps; return; } // b 问结束条件 // if (count 2 board[emptyPos] 1) { ... } if (steps minSteps) return; // 遍历所有可能移动 for (each move) { int i move[0], jmove[1], kmove[2]; if (board[i]1 board[j]1 board[k]0) { // 跳 board[i]0; board[j]0; board[k]1; backtrack(count-1, steps1); // 回溯 board[i]1; board[j]1; board[k]0; } } }
算法设计与分析-习题12.1
目录1.a.对于本节中做到一半的4皇后问题继续使用回溯查找以求得该问题的第二个解。b.请解释一下如何利用棋盘的对称性求得4皇后问题的第二个解。2.a. 5皇后问题的哪一个解是回溯算法求得的最后一个解。b.利用棋盘的对称性至少再求出该问题的4个解。3.a.任选一种语言实现n皇后问题的回溯算法。对一系列n值运行该程序以得到该算法的状态空间树中的节点数。拿这些值和该问题的穷举查找算法所生成的候选解的数量进行比较(参见习题3.4的第9题)。b.对于a中调用程序的每一个n值用12.1节描述的方法估计状态空间树的规模并且拿这些估计值和实际获得的值做比较。4.对于任意n≥4设计一个可以在线性时间内求解n皇后问题的算法。5.用回溯法对下图求哈密顿回路问题。6.对图12.3(a)应用回溯法求解3色问题。7.用回溯法生成{1,2,3,4}的所有排列。8.a.应用回溯法对“子集和”问题的下面实例求解 A{1,3,4,5}, d11。b.如果我们只使用两个不等式中的一个来判定没有希望的节点这个回溯算法能够正确工作吗9.本节给出的回溯算法的通用模板只有在没有一个解是另一个解的前缀的情况下才能正常工作。修改这个伪代码使它在无此约束的情况下也能正确工作。10.对于下面的问题写一个程序实现它的回溯算法a.哈密顿回路问题。b. m色问题。11.插棒游戏 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始的时候如下图所示除了一个孔所有孔都插上了插棒。一个插棒可以跳过它的直接邻居移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法求解该谜题的下列版本a.已知空孔的位置求出消去13个插棒的最短步骤对剩下的插棒的最终位置不限。b.已知空孔的位置求出消去13个插棒的最短步骤剩下的插棒最终要落在最初的空孔上。1.a.对于本节中做到一半的4皇后问题继续使用回溯查找以求得该问题的第二个解。继续回溯的步骤就是-4,4回滚3,1回滚2,4回滚1,2回滚 第一行选择3第二行选择1第三行选择4第四行选择2b.请解释一下如何利用棋盘的对称性求得4皇后问题的第二个解。通过中垂线反射对称取位置2.a. 5皇后问题的哪一个解是回溯算法求得的最后一个解。从最后一行向上向左回溯得到的第一个解就是正常的最后一个解b.利用棋盘的对称性至少再求出该问题的4个解。对第3行进行反射对第3列进行反射从主对角线反射副对角线反射一共四个解3.a.任选一种语言实现n皇后问题的回溯算法。对一系列n值运行该程序以得到该算法的状态空间树中的节点数。拿这些值和该问题的穷举查找算法所生成的候选解的数量进行比较(参见习题3.4的第9题)。#include stdio.h #include stdlib.h #include math.h int nodeCount 0; // 状态空间树节点总数 int n; // 皇后数量 int *cols; // 记录每一行皇后所在列 // 检查在 row 行 col 列放皇后是否合法 int isSafe(int row, int col) { for (int i 0; i row; i) { if (cols[i] col || abs(i - row) abs(cols[i] - col)) { return 0; } } return 1; } // 回溯算法 void backtrack(int row) { if (row n) { return; } for (int col 0; col n; col) { nodeCount; // 每尝试一个位置 一个节点 if (isSafe(row, col)) { cols[row] col; backtrack(row 1); } } } // 计算 n^n穷举法候选解数量 long long bruteForce(int n) { long long res 1; for (int i 0; i n; i) { res * n; } return res; } int main() { printf(n\t回溯节点数\t穷举候选解数(n^n)\n); printf(----------------------------------------\n); // 测试 n4 ~ n8 for (n 4; n 8; n) { nodeCount 0; cols (int*)malloc(n * sizeof(int)); backtrack(0); long long brute bruteForce(n); printf(%d\t%d\t\t%lld\n, n, nodeCount, brute); free(cols); } return 0; }b.对于a中调用程序的每一个n值用12.1节描述的方法估计状态空间树的规模并且拿这些估计值和实际获得的值做比较。估计值≈n*(n-2)*(n-4)*...实际上n实际节点数教材 12.1 估计值4161855360615217075516108205622404.对于任意n≥4设计一个可以在线性时间内求解n皇后问题的算法。我们把数字分成偶数和奇数两类情况 1n 是偶数且n ≠ 6k2如 n4,8,10,14...规则先放偶数列2,4,6,...,n再放奇数列1,3,5,...,n-1例子n8列顺序2,4,6,8,1,3,5,7情况 2n 是偶数且n 6k2如 n2,6,14... 只需要 n≥4 → n6,14...规则放n/2, n/22, ..., n放2,4,...,n/2-2放n/23, n/25,...,n-1放1,3,...,n/21例子n6列顺序3,5,1,4,6,2情况 3n 是奇数n≥5把 n 变成n-1偶数按偶数规则放最后一行放第 n 列。这样就只需要一次循环生成列号O(n)线性时间5.用回溯法对下图求哈密顿回路问题。以a为起点开始遍历假设按字典序选择下一个点再从b开始选d、f、c发现不通开始回溯到f点选择g、e再次回溯到d先遍历g但是会再次失败直到从e开始遍历最终得到结果6.对图12.3(a)应用回溯法求解3色问题。7.用回溯法生成{1,2,3,4}的所有排列。8.a.应用回溯法对“子集和”问题的下面实例求解 A{1,3,4,5}, d11。也就是无解b.如果我们只使用两个不等式中的一个来判定没有希望的节点这个回溯算法能够正确工作吗算法仍然可以正确工作但状态空间树将包含比必要更多的节点。9.本节给出的回溯算法的通用模板只有在没有一个解是另一个解的前缀的情况下才能正常工作。修改这个伪代码使它在无此约束的情况下也能正确工作。算法 Backtrack(X[1..i]) //输入X[1..i]确定了一个解的前面i个有希望的分量 //输出代表问题的解的所有元组 if X[1..i]是一个解 write X[1..i] for 和X[1..i]以及约束相容的每一个元素 x∈S_(i1) do X[i1]←x Backtrack(X[1..i1])10.对于下面的问题写一个程序实现它的回溯算法a.哈密顿回路问题。#include stdio.h #define MAX 10 int n; // 顶点数 int graph[MAX][MAX]; // 邻接矩阵 int path[MAX]; // 保存回路 // 检查顶点 v 是否能加入路径 int isSafe(int v, int pos, int path[]) { // 相邻 if (graph[path[pos-1]][v] 0) return 0; // 是否已经在路径里 for (int i 0; i pos; i) if (path[i] v) return 0; return 1; } // 回溯 int hamCycle(int pos) { // 所有顶点都加入了 if (pos n) { // 最后一个点和起点相连 if (graph[path[pos-1]][path[0]] 1) return 1; else return 0; } // 尝试所有顶点 for (int v 1; v n; v) { if (isSafe(v, pos, path)) { path[pos] v; if (hamCycle(pos1) 1) return 1; path[pos] -1; // 回溯 } } return 0; } void printPath() { printf(哈密顿回路); for (int i 0; i n; i) printf(%d , path[i]); printf(%d\n, path[0]); } int main() { // 示例 n 5; int g[5][5] { {0,1,0,1,0}, {1,0,1,1,1}, {0,1,0,0,1}, {1,1,0,0,1}, {0,1,1,1,0} }; for (int i0; in; i) for (int j0; jn; j) graph[i][j] g[i][j]; path[0] 0; if (hamCycle(1) 1) printPath(); else printf(无哈密顿回路\n); return 0; }b. m色问题。#include stdio.h #define MAX 10 int n, m; int graph[MAX][MAX]; int color[MAX]; // 检查顶点 v 能否涂 c 色 int isSafe(int v, int c) { for (int i 0; i n; i) if (graph[v][i] c color[i]) return 0; return 1; } // 回溯着色 int mColoring(int v) { // 全部着色完成 if (v n) return 1; // 尝试所有颜色 for (int c 1; c m; c) { if (isSafe(v, c)) { color[v] c; if (mColoring(v1) 1) return 1; color[v] 0; // 回溯 } } return 0; } void printColors() { printf(着色方案); for (int i 0; i n; i) printf(%d , color[i]); printf(\n); } int main() { // 示例图 n 4; m 3; int g[4][4] { {0,1,1,1}, {1,0,1,0}, {1,1,0,1}, {1,0,1,0} }; for (int i0; in; i) for (int j0; jn; j) graph[i][j] g[i][j]; if (mColoring(0) 1) printColors(); else printf(无法用 %d 种颜色着色\n, m); return 0; }11.插棒游戏 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始的时候如下图所示除了一个孔所有孔都插上了插棒。一个插棒可以跳过它的直接邻居移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法求解该谜题的下列版本a.已知空孔的位置求出消去13个插棒的最短步骤对剩下的插棒的最终位置不限。backtrack(board, count, steps): if count 2: 更新最小步数 return if steps minSteps: return for 每一个位置 i 0..14: if board[i] 1: for 每一个 i 能跳的方向 (i→j→k): if board[j]1 且 board[k]0: // 做移动 board[i] 0 board[j] 0 board[k] 1 backtrack(board, count-1, steps1) // 回溯 board[i] 1 board[j] 1 board[k] 0b.已知空孔的位置求出消去13个插棒的最短步骤剩下的插棒最终要落在最初的空孔上。// 15个位置 int board[15]; // 每个点能跳的方向{from, over, to} int moves[][3] { {0,1,3}, {0,2,5}, {1,3,6}, {1,4,8}, // ... 所有合法跳跃方向 }; int minSteps 999; void backtrack(int count, int steps) { // a 问结束条件 if (count 2) { if (steps minSteps) minSteps steps; return; } // b 问结束条件 // if (count 2 board[emptyPos] 1) { ... } if (steps minSteps) return; // 遍历所有可能移动 for (each move) { int i move[0], jmove[1], kmove[2]; if (board[i]1 board[j]1 board[k]0) { // 跳 board[i]0; board[j]0; board[k]1; backtrack(count-1, steps1); // 回溯 board[i]1; board[j]1; board[k]0; } } }
