人生没有回溯!我多想回溯啊。(祝你生日快乐)
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法
,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。
回溯问题胃酸法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;
}
最终的结果。
有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皇后。
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;
}
给定一个无向图(输入二维邻接矩阵,顶点数为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;
}