【算法分析与设计】第八章

2024-06-26 17:24| 来源: 网络整理| 查看: 265

一、知识铺垫约束条件分为显式约束和隐式约束显式：规定了问题的解的分量的取值范围。如求n的全排列每个位置只能取1~n 隐式：用于判定候选解是否为可行解。如全排列的每个数字不允许重复。问题状态和状态空间树状态空间树是描述问题解空间的树形结构，每个结点称为一个问题状态。树的每条分支代表一次决策，从根结点到叶结点的路径就代表了一个候选解，称该叶结点所代表的状态为解状态。如果候选解是可行解则称之为答案状态。剪枝函数剪枝函数分为约束函数和限界函数约束函数：避免无所谓的搜索那些已知不含答案状态的子树。限界函数：用于最优化问题，剪去那些不可能含有最优答案结点的子树。二者的区别在于：约束函数是对约束条件的实现，剪去不带答案结点的子树。而限界函数常用于求解最优化问题，它剪去的子树可能带答案结点，但不会是最优答案结点。二、什么是回溯法

回溯法是一种更为一般的解题方法。回溯法是通过搜索状态空间树来求问题的可行解或最优解的方法。本质就是dfs + 剪枝。

三、回溯法的使用场景

如果问题的解可表示成一个n元组 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1,x2,...,xn)，我们就可以通过枚举所有的可能排列来搜索答案。比如求全排列、迷宫问题、n皇后、子集和数、图的着色问题等。

四、回溯法的解题步骤 void BackTrack(int k){ if k == n { 输出答案 } else{ for 所有可能的x[k]取值 if x[k] 满足约束条件 BackTrack(k+1) } } 五、典例 n皇后问题 #include using namespace std; typedef long long LL; const int N = 15; int g[N], ans[N]; int n; LL cnt; bool vis[N]; bool check(int k, int j){ for(int i = 1; i if(d == n + 1){ for(int i = 1; i // 隐式约束 ans[d] = i; vis[i] = 1; nQueens(d + 1); vis[i] = 0; } } } int main(){ cin >> n; nQueens(1); cout for(int i = k + 1; i //不选 k x[k] = 0; dfs(s, k + 1, r - w[k]); } } int main(){ cin >> n >> m; for(int i = 0; i > w[i], tmp[i] = w[i]; // tmp copy w for print int r = 0, s = 0; for(int i = 0; i

【本文地址】

公司简介

联系我们