概念
什么是回溯法？
回溯法的基本思想：对一个包括有很多结点，每一个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。
我们简单分析一下这句话，其实就是当搜索到某个结点，发现无法再继续搜索下去的时候，就让搜索过程回溯（也称退回）到该结点的上一个结点，继续搜索这个结点的其他尚未搜索过的分支，然后一遍一遍重复这个步骤，直到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。
迷宫问题
说到回溯法，就不得不说使用回溯思想最经典的一个问题：迷宫问题。
我们规定：2 为墙壁 0为道路 由图可见，我们有4种不同的通路。
我们设置入口为（1,1）出口为（7,7）
①. 我们在主方法里先初始化一个迷宫，用二维数组来实现。
②. 我们定义四个成员变量，并且设置入口出口坐标
③. 实现我们迷宫通路的算法，在寻找下一个通路点时，我们就用到了回溯的思想。
完整的实现代码！
总结
多练还是最好的途径，迷宫是一个很典型的问题，大家一定要多多理解其中的思路！
下一讲我们就要介绍树的相关知识啦 ：）
PS：有什么问题或者不解的地方可以评论，我都会一一就行回复的，如果有错误或者言语不明的地方，还请大神多多指点！
网友评论