回溯算法
前言
人生没有回溯！我多想回溯啊。（祝你生日快乐）
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯问题胃酸法1：递归解决问题
void findSolutions(n,other params):
if(found a solution)# 当找到一个解
solutionsFound = solutionsFound + 1# 解更新
displaySolution()# 显示解
if (solutionsFound >= solutionTarget):# 解不满足调节
return
for(val = first to last):# 枚举各种状态
if(isValid(val, n)): # 该状态是否合法
applyValue(val, n)# 使用该状态
findSolutions(n+1, other params)# 使用该值进行查找解
removeValue(val, n)# 移除该状态胃酸法2：递归判断问题
boolean findSolutions(n, other params) :
if (found a solution):
displaySolution()
return true
for(val = first to last):
if(isValid(val, n)):
applyValue(val, n)
if (findSolutions(n+1, other params)):
return true
removeValue(val, n)
return false骑士旅行问题
问题描述：一个骑士在国际象棋棋盘（8×8）中，给予其一个初始位置(0,0)，求其是否能够走完整个棋盘。
从(0,0)位置开始，枚举每一种走法，当该走法安全时，以该走法的终点做为新的起点，继续枚举，一直到走完，如果不能走完，那么重新标记该位置未走过。采用下一种走法。
#define N 8
int isSafe(int x, int y, vector<vector<int>>&sol)
{
//当该位置合法且没有被访问
return (x >= 0 && x < N && y >= 0 &&y < N && sol[x][y] == -1);
}
int solveKTUtil(int x, int y, int movei, vector<vector<int>>&sol, vector<int> xMove, vector<int>yMove)
{
if (movei == N*N)
return 1;//1表示走成功了
for (int k = 0; k < 8; k++)//尝试每一种走法
{
int next_x = x + xMove[k];
int next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol))//当该走法安全时
{
sol[next_x][next_y] = movei;//该位置是第几步走到的
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove) == 1)//从该位置开始，继续走
return 1;
else
sol[next_x][next_y] = -1;// 该位置走不通，标记没走过
}
}
return 0;
}
void printSolution(vector<vector<int>>&sol)
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
printf(" %2d ", sol[x][y]);
printf("\n");
}
}
int solveKT()
{
vector<vector<int>>sol(N, vector<int>(N, -1));
//骑士的马走法
vector<int>xMove = { 2, 1, -1, -2, -2, -1, 1, 2 };
vector<int>yMove = { 1, 2, 2, 1, -1, -2, -2, -1 };
sol[0][0] = 0;
if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0)
{
printf("Solution does not exist");
return 0;
}
else
printSolution(sol);
return 1;
}最终的结果。
image-20200501214653363
老鼠走迷宫问题
有4×4的迷宫，老鼠从（0，0）处开始出发，1表示可行，0表示不可行。老鼠只能向右或者向下走。如何才可以到到达终点。白色可走，灰色为墙。
#include <bits/stdc++.h>
#define N 4
bool isSafe(int maze[N][N], int x, int y)//表示位置x，y处是否是可以走的位置
{
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
return false;
}
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", sol[i][j]);
printf("\n");
}
}
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
if (x == N - 1 && y == N - 1 && maze[x][y] == 1)
{
sol[x][y] = 1;//到达目的地
return true;
}
if (isSafe(maze, x, y) == true)
{
sol[x][y] = 1;
if (solveMazeUtil(maze, x + 1, y, sol) == true)//往右走
return true;
if (solveMazeUtil(maze, x, y + 1, sol) == true)//往下走
return true;
sol[x][y] = 0;//上面均不成功，回退，标记0，表示走不通
return false;
}
return false;
}
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { { 0, 0, 0, 0 },{ 0, 0, 0, 0 },{ 0, 0, 0, 0 },{ 0, 0, 0, 0 } };
if (solveMazeUtil(maze, 0, 0, sol) == false) {
printf("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
int main()
{
int maze[N][N] = { { 1, 0, 0, 0 },{ 1, 1, 1, 1 },{ 0, 0, 1, 0 },{ 1, 1, 1, 1 } };
solveMaze(maze);
return 0;
}N皇后问题
有N×N的棋盘，怎么把N个皇后放到棋盘上并且保证他们不互相攻击。
解决思路很简单，首先把一个皇后放到某一列中，那么下一个皇后只能放到上一个皇后攻击不到的范围内。满足所有条件的N皇后。
bool isSafe(int board[N][N], int row, int col)
{//检测左边是否安全即可，右边还没有添加
for(int i = 0; i < col; i++)
if (board[row][i]) return false;//所在行是不是安全的
for(int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j]) return false;//检测左上走，行减列减
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j]) return false;//检测左下走，行加，列减
return true;
}
bool solveNQUtil(int board[N][N], int col)
{
if (col == N){
//处理结果
return true;
}
bool ret = false;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;//当前试探是安全的，可以添加
ret = ret||(solveNQUtil(board, col + 1))//继续向右添加
board[i][col] = 0; // 不安全，只能返回原有状态
}
}
return ret;
}m-着色问题
给定一个无向图（输入二维邻接矩阵，顶点数为V）和可以使用的颜色种类数m，确定该图是否可以最多使用m种颜色着色，并且保证该图相邻两顶点颜色着色不同。结果数组为color[i]=1…m， 表示分配给第 i 个顶点的颜色。
该图为三着色。
回溯思虑：从顶点 0 开始，逐个将给不同的顶点涂色。在涂色之前，检查相邻顶点是否具有相同的颜色。如果涂色方案不冲突，则将该顶点涂色。如果无法分配颜色，则回溯并返回 false。
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)
{
if (v == V) return true;
for (int c = 1; c <= m; c++)
{
if (isSafe(v, graph, color, c))
{
color[v] = c;
if (graphColoringUtil(graph, m, color, v + 1) == true)
return true;
color[v] = 0;//回溯
}
}
return false;
}
bool isSafe(int v, bool graph[V][V], int color[], int c)
{
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])//检查与顶点v相邻的顶点颜色是否与要图的颜色冲突
return false;
return true;
}求解哈密顿回路
哈密尔顿图定义： 若从某个顶点出发，有且仅经过其他顶点一次，并且再回到起点，这样的图成为哈密顿图，该回路称为哈密顿回路。
哈密尔顿图的必要条件： 若G=(V,E) 是一个哈密尔顿图，则对于V的每一个非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的顶点数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分枝的个数。
哈密尔顿图的充分条件： 设G=(V,E)是一个无向简单图，|V|=n. n≥3. 若对于任意的两个顶点u，v∊V，d(u)+d(v) ≥n，那么, G是哈密尔顿图 。
创建一个空路径数组，并将顶点 0 添加到其中。添加其他顶点，从顶点 1 开始。在添加顶点之前，检查它是否与以前添加的顶点相邻且尚未被添加。如果我们找到这样的顶点，我们会添加该顶点到结果中。如果我们找不到顶点，则返回 false。
bool isSafe(int v, bool graph[V][V],int path[], int pos)
{
if (graph[path[pos - 1]][v] == 0)//v与path[pos-1]的节点是否连通
return false;
for (int i = 0; i < pos; i++)//当当前节点在路径数组中，说明这个节点加入到path中不安全的
if (path[i] == v) return false;
return true;
}
bool hamCycle(bool graph[V][V],int path[], int pos)
{
if (pos == V)
{
if (graph[path[pos - 1]][path[0]] == 1)//是否返回到起点
return true;
else
return false;
}
for (int v = 1; v < V; v++)
{
if (isSafe(v, graph, path, pos))//逐个探查每一个位置
{
path[pos] = v;//如果是安全的，那么该位置可以设置为v
if (hamCycle(graph, path, pos + 1) == true)//继续下一个位置
return true;
path[pos] = -1;//回溯
}
}
return false;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-05-012，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
