通用算法 -[图算法] - 回溯法

1、什么是回溯法?

概念：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

基本思想：确定了问题的解空间结构后，回溯法将从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。开始结点成为活结点，同时也成为扩展结点。在当前的扩展结点处，向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处，并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

关键要素：
(1) 针对给定的问题，定义问题的解空间；
(2) 确定易于搜索的解空间结构；
(3) 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

2、递归、回溯法与DFS的区别

• 递归是一种算法结构，回溯是一种算法思想；
• 回溯搜索属于深度优先搜索的一种；
• 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”。

剪枝的意思也就是说对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。

回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。

为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。

3、回溯法的基本框架

stack<int> path  // 从根节点到当前扩展节点的路径
visit[N] //  节点的所有节点的访问情况
seq[N] //每个节点的内容
OtherInfo //记录其他信息的数据结构,
//该数据结构在搜索过程中会发生变化

void DFS（layer）
{	if(layer == N or len(path) == N)
	{ 记录或输出；
		return;
	}
	
	for(i=1; i<=N; i++)
	{
		if (visit[i] == False and (其他约束条件))
		{
			path.push(seq[i]) ;
			visit[i] = True;
			修改OtherInfo;
			
			DFS(layer + 1) //向纵深方向搜索

			//回溯部分
			visit[i] = False
			path.pop()
			恢复OtherInfo		
		}
	}
	return
	
	
}

4、回溯法的简单应用实例

（1）全排列问题
描述：给定一个序列seq，生成该序列的全排列。
代码：

#使用回溯法生成全排列
def permutation(seq_org):

    visit = [False] * len(seq_org)

    seq_per = []

    results = []

    DFS(0,seq_org,visit,seq_per,results)

    print("results={}".format(results))


def DFS(layer,seq_org,visit,seq_per,results):

    if len(seq_per) == len(visit):

        results.append(list(seq_per))

        return

    for i in range(0,len(visit)):

        if visit[i] == False:

            seq_per.append(seq_org[i])

            print("seq_per={}".format(seq_per))

            visit[i] = True

            DFS(layer + 1,seq_org,visit,seq_per,results)

            visit[i] = False

            seq_per.pop()

    return 

if __name__ == '__main__':

    seq = ['x','y','z']
    
    permutation(seq) 
    

（2）素数环
描述：给定n个数，将这n个数组成一个环，每个数作为环中的一个结点。要求环中任意两个相邻结点的和为一个素数。
输出满足要求的所有方案。
代码：

class PrimeRing:

    seq = None

    visit = None

    ring = []

    results = []


    def Find(self,seq):

        self.seq = seq

        self.visit = [False] * len(seq)

        self.DFS(0)

        return self.results



    def DFS(self,layer):

        if len(self.ring) == len(self.visit) and self.IsPrime(self.ring[0],self.ring[-1]):

            self.results.append(list(self.ring))

            return 

        for i in range(0,len(self.visit)):

            if self.visit[i] == False:

                if layer == 0 or self.IsPrime(seq[i],self.ring[-1]):

                    self.ring.append(seq[i])

                    self.visit[i] = True

                    self.DFS(layer + 1)

                    self.visit[i] = False

                    self.ring.pop()
        
                
        return   

    def IsPrime(self,a,b):

        isprime = True

        s = a + b

        #此处注意，python的右移运算符（>>）、按位与(&)、或(|)、异或(^)优先级小于加减乘除

        for i in range(2,(s>>1) + 1):

            if s % i == 0:

                isprime = False

                break

        return isprime
            


if __name__ == '__main__':

    seq = [1,2,3,4]

    primering = PrimeRing()

    result = primering.Find(seq)

    print("result={}".format(result))

（3）8皇后问题
问题：在一个 8 * 8 的棋盘上放置8个皇后，使这8个皇后不在即不在同一行，也不在同一列，还不在同一条对角线上。
代码：

Q = [None for i in range(8)]

VM = [False for i in range(8)]
VL = [False for i in range(16)]
VR = [False for i in range(16)]

CNT = 0
N = 8

def dfs(cur):
    if cur == N:
        global CNT
        CNT += 1
    else:
        for i in range(0, N):
            if not VM[i] and not VL[cur+i] and not VR[cur-i+N]:
                VM[i] = VL[cur+i] = VR[cur-i+N] = True
                Q[cur] = i
                dfs(cur+1)
                VM[i] = VL[cur+i] = VR[cur-i+N] = False


dfs(0)
print('ans = ' + str(CNT))

（4）走迷宫问题
问题：*表示可走 ，#表示障碍 T表示出口
入口是(1,1)，数据保证左上角是入口。
代码：

#include<iostream>
using namespace std;

char maze[100][100];
bool flag[100][100];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int m,n;

bool dfs(int x,int y)
{
    flag[x][y]=1;              //走过的路标记为1
    if(maze[x][y]=='T')return true;
    for(int i=0;i<4;i++)       //四个方向
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(flag[nx][ny]==0||maze[nx][ny]=='*'||maze[nx][ny]=='T'&&nx>0&&ny>0&&nx<m+1&&ny<n+1)
        {
            return dfs(nx,ny);   
            flag[nx][ny]=0;    //回溯，将标记重新标记为0
        }
    }
    return false;             //找不到返回false
}

int main()
{

    while(cin>>m>>n){
    memset(maze,0,sizeof(maze));
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>maze[i][j];
    if(dfs(1,1))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    }
}

5、回溯法题型分类

4.1 基本入门题

基础题链接

4.2 高级进阶题
（1） 地图型：这种题型将地图输入，要求完成一定的任务。因为地图的存在。使得题意清楚形象化，容易理清搜索思路。

AOJ 869-迷宫(遍历地图，四向搜索)
HDU 1035-Robot Motion(指定方向搜索，迷路（循环）判断)
HDU 1045-Fire Net(check函数，回溯)
HDU 1010-Tempter of the Bone(奇偶剪枝，回溯)

（2）数据型：这种题型没有给定地图，一般是一串数字或字母，要求按照一定的任务解题。相对于地图型，这种题型较为抽象，需要在数据中进行搜索。数据以数组的形式存储，那么只要将数组也当作一张图来进行搜索就可以了。

HDU 1016-Prime Ring Problem(回溯、素数筛)
HDU 1258-Sum It Up(双重DFS递归，去重技巧)
HDU 1015-Safecraker(回溯，字符处理)
HDU 2676-Sudoku(抽象，回溯)

最后

以上就是风中微笑为你收集整理的通用算法 -[图算法] - 回溯法的全部内容，希望文章能够帮你解决通用算法 -[图算法] - 回溯法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。