重庆网站建设科技公司,网站的站内结构锚文本是如何做的,html教程菜鸟教程视频,长春市长春网站制作站优化回溯法概念
概念#xff1a;在包含问题所有解的解空间树中#xff0c;按照深度优先搜索的策略#xff0c;根据根结点#xff08;开始节点#xff09;出发搜索解空间树。
流程#xff1a;首先根结点成为活节点#xff0c;同时也成为当前的扩展结点。在当前的扩展结点处…回溯法概念
概念在包含问题所有解的解空间树中按照深度优先搜索的策略根据根结点开始节点出发搜索解空间树。
流程首先根结点成为活节点同时也成为当前的扩展结点。在当前的扩展结点处搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵向方向移动则当前扩展结点就成为死结点。此时应往回移动回溯至最近的一个活结点处并使这个活结点成为当前的扩展结点。回溯法以这种方式递归的在解空间中搜索直到找到所要求的解或解空间中已无活结点为止 活结点active node指自身已生成但其孩子结点没有全部生成的结点 扩展节点expansion node指正在产生孩子结点的结点也称E结点 死结点dead node指其所有子结点均已生产的结点 保存结点的解回溯法求解时存在退回到祖先结点的过程所以需要保存搜索过的结点。通常有两种方法其一是用自定义栈来保存祖先结点其二是采用递归方法因为递归调用会将祖先结点保存到系统栈中在递归调用返回时自动回退到祖先结点。
避免无效搜索回溯法搜索解空间时通常采用两种策略避免无效搜索以提高回溯的搜索效率一是用约束函数在扩展结点处剪除不满足约束条件的路径二是用限界函数减去得不到问题解或最优解的路径这两类函数统称为剪枝函数。
回溯法的解题步骤
针对给定的问题确定问题的解空间树问题的解空间树应至少包含问题的一个解或最优解。确定结点的扩展搜索规则以深度优先方式搜索解空间树并在搜索过程中采用剪枝函数来便面无效搜索。其中深度优先方式可以选择递归回溯或者迭代非递归回溯
回溯算法与深度优先遍历的异同
访问次序不同访问次数不同剪枝不同 1访问次序不同深度优先遍历的目的是“遍历”本质是无序的也就是说访问次序不重要重要的是否被访问过实现上只需要对于每个位置记录是否被访问就足够。回溯法的目的是“求解过程”本质是有序的也就是说每一步都是要求的次序实现上要使用访问状态来记录也就是对于每个顶点记录以及访问过的邻居方向回溯之后从新的未访问过的方向去访问其他邻居。 2访问次序不同深度优先遍历对已经访问过的顶点不再访问所有顶点仅访问一次。回溯法中已经访问过的顶点可能再次访问 3剪枝不同深度优先遍历不含剪枝而很多回溯法会采用剪枝条件剪除不必要的分支以提高效能 回溯法的时间分析
时间分析依据解空间树中的结点数
假设解空间树共有n层第一层有m0个满足约束条件的结点每个结点有m1个满足约束条件的结点则第二层有m0m1m2个满足约束条件的结点同理第三层有m0m1m2个满足约束条件的结点......
执行时间T(n)m0m0m1m0m1m2m0m1m2m3....m0m1m2...(mn-1)
时间复杂度
解空间树为子集树时O(2^n)解空间树为排列树时O(n!)
1、N皇后问题
八皇后问题是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出在8X8格的国际象棋上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜率为1的斜线上问有多少种摆法每一行应有一个皇后 解决思路
解决皇后在棋盘上的攻击范围递归处理完成深度优先搜索并回溯过程进行调用的函数
put_queen函数使用一个attack数组来存放皇后的攻击范围1为不可放置区域0为安全区域。dx与dy数组组合完成对八个方向的扩展if判断语句来控制范围始终处于棋盘中
void put_queen(int x,int y,vectorvectorint attack) {static const int dx[] {-1,1,0,0,-1,-1,1,1 };static const int dy[] { 0,0,-1,1,-1,1,-1,1 };attack[x][y] 1;//皇后位置取值为1for (int i 0; i attack.size(); i) {for (int j 0; j 8; j){int nx x i * dx[j];int ny y i * dy[j];if (nx 0 nx attack.size() ny 0 ny attack.size()) {attack[nx][ny] 1;}}}
}
backtrack函数当皇后放置完后k溢出进行存储入solve数组操作核心思想为下一层无无位置时进行回溯
void backtrack(int k,int n,vectorstring queen,vectorvectorint attack,vectorvectorstring solve){//k:表示当前处理的行数//n:表示N皇后问题//queen:存储皇后的位置//attack:标记皇后的攻击范围//solve:存储N皇后的解法if (k n) {solve.push_back(queen);return;}//遍历for (int i 0; i n; i) {if (attack[k][i] 0) {vectorvectorint tmp attack;//备份attack数组queen[k][i] Q;put_queen(k, i, attack);//更新attack数组backtrack(k 1, n, queen, attack, solve);//递归试探k1行皇后位置attack tmp;//恢复attack数组queen[k][i] .;//恢复queen数组}}
}
solveQueens函数定义attack棋盘、solve解法保存数组、queen摆放方案循环初始化数组
vectorvectorstring solveQueens(int n) {vectorvectorstring solve;vectorvectorint attack;vectorstring queen;//使用循环初始化attack和queen数组for (int i 0; i n; i) {attack.push_back(std::vectorint());for (int j 0; j n; j) {attack[i].push_back(0);}queen.push_back();queen[i].append(n, .);}backtrack(0, n, queen, attack, solve);return solve;
}
主函数
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);vectorvectorstring result;result solveQueens(8);//8皇后问题cout 8皇后共有 result.size() 种解法 endl;for (int i 0; i result.size(); i) {cout 解法 i1 :\n endl;for (int j 0; j result[i].size(); j) {cout result[i][j].c_str() \n endl;}cout \n endl;}return 0;
}
