通用算法 -[图算法] - 回溯法_Albert_YuHan的博客-程序员宅基地

技术标签: 数据结构与算法  

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(抽象,回溯)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/duan20140614/article/details/98943590

智能推荐

rabbitmq通过代码创建队列和交换机以及绑定_猿来是蜡笔小象啊的博客-程序员宅基地_rabbitmq使用命令创建交换机、队列及绑定

rabbitmq通过代码创建队列和交换机以及绑定代码如下:@Configurationpublic class RabbitConfig { private final String exchange_name="exchange_name_qy129"; private final String queue_name="queue_name_qy129";// 创建交换机 @Bean(value = "exchange") public Exchange E

码率、帧率、分辨率三者的关系_云初爱小蓝鲸的博客-程序员宅基地_码率和分辨率的关系

视频图像包含着极大的冗余信息,分为时间冗余和空间冗余。而视频压缩技术就是去除其中的冗余信息(即相关性)。帧率: FPS (frame per second)每秒钟播放的视频码率: kbps 编码器每秒钟编出的数据量大小分辨率: 单位英寸中所包含的像素点数分析三者对于视频传输的影响帧率帧率影响画面的流畅度,帧率越高,流畅度越大;帧率越低,画面跳动感越强。基于人眼的生理结构,通常认为帧率高于16时,察觉不出跳动感,这称为视觉暂留。假定每一帧的分辨率是固定的(即可认为每一帧需要的数据量是一定的),那么

charles 3.11.2 for mac安装文件下载及破解charles.jar下载_iteye_20793的博客-程序员宅基地

charles 官方下载地址:http://www.charlesproxy.com/ charles V3.11.2 for mac安装文件及破解文件charles.jar下载地址:http://download.csdn.net/detail/forestqqqq/9699790 破解步骤:1,安装charles的dmg文件2,替换/Applications...

fork函数创建进程_文文同学1的博客-程序员宅基地

创建进程函数fork的使用:函数原型:pid_t fork(void);返回值:fork函数调用成功,返回两次返回值为0,代表当前进程是子进程返回值非负数,代表当前进程是父进程调用失败,返回-1include &lt;stdio.h&gt;#include &lt;sys/types.h&gt;#include &lt;unistd.h&gt;int main (){ int pid; printf("current pid is %d\n

睿象云入围 | 腾讯云原生加速器首期成员名单_睿象云的博客-程序员宅基地

睿象云入围 | 腾讯云原生加速器首期成员名单6月30日,“开源向善·应云而生”腾讯云原生加速器公布了首期入选企业名单,睿象云等 38 家优秀云原生企业从全球500多家参与企业中脱颖而出,携手腾讯共建云原生生态,面向云原生未来加速启航。产业数字化浪潮中,云原生已成大势。企业发展中的开发、运维、管理等环节日趋复杂,云原生技术为企业提供了面向未来的信息化平台构建方式,并已逐渐开始融入各行各业。腾讯积极构建云原生生态,联手生态伙伴,共同为企业提供便捷、安全的云原生服务。由此,“腾讯云原生加速器”应运而生,输出腾

常用windbg命令(转)_StephenQin的博客-程序员宅基地

1、查看版本信息:version、vertarget。2、查看模块信息:lm、!dlls、!lmvi等。3、调用栈:用k命令显示调用栈,用.frames命令切换栈帧。4、内存操作:读内存用d命令,写内存用e命令。5、自动分析:!analyze、!owner等。6、符号命令:.reload加载符号, .sympath设置符号路径, !sym设置符号选项。7、进程线程:!process...

随便推点

Mysqlbackup 备份详解(mysql官方备份工具)_X-X的博客-程序员宅基地

转 http://blog.csdn.net/m582445672/article/details/7649944A.1全库备份.命令:mysqlbackup --defaults-file=/home/mysql-server/mysql3/my.cnf  --user=root --password=root  --databases="mysql total2" --with

DOTNETBAR的使用方法_weixin_30588907的博客-程序员宅基地

DOTNETBAR的使用方法我这里讨论的版本是DotNetBar 6.7.0.1 for VS2005的破解版本,其他版本我一个是没有时间找到,另外也是因为大同小异下载地址,见这里,如果还有哪个朋友下载不了,就加我QQ吧,如果你能提供一个群,我会写在这里,然后利用群空间来整理控件,方便你我下载地址是www.vscodes.com/soft/show.asp?id=2...

_WIN32_WINNT 定义_weixin_30693183的博客-程序员宅基地

Windows XP _WIN32_WINNT&gt;=0x0501Windows 2000 _WIN32_WINNT&gt;=0x0500Windows NT 4.0...

Tri_integral Summer Training 6_Tri_integral的博客-程序员宅基地

比赛链接题目ABCDEFI这是Open Ural FU Championship 2012.由于UVALive跪了,所以找了场比赛ural上的比赛.加勒比海盗专场,但英语充斥着俄罗斯风味,可以和印度英语相媲美.开场Moor艰难的读完A觉得可做,然后开始敲,为了确保题意,让我再读一边,我还没读完Moor就敲完了,场上已经过了很多,然后就交了,0:08:15 1

关于最小二乘法详解_梦想家DBA的博客-程序员宅基地_最小二乘法csdn

最小二乘法的原理与要解决的问题最小二乘法的矩阵法解法最小二乘法的几何解释最小二乘法的局限性和适用场景 最小二乘法的python实战import numpy as npimport scipy as spfrom scipy.optimize import leastsqimport matplotlib.pyplot as plt%matplotlib inline# 目标函数def real...

Java加密技术(十)——单向认证_yangcbyang的博客-程序员宅基地

在Java 加密技术(九)中,我们使用自签名证书完成了认证。接下来,我们使用第三方CA签名机构完成证书签名。     这里我们使用thawte提供的测试用21天免费ca证书。     1.要在该网站上注明你的域名,这里使用www.zlex.org作为测试用域名(请勿使用该域名作为你的域名地址,该域名受法律保护!请使用其他非注册域名!)。     2.如果域名有效,你会收到邮件要求你访问