回溯的概念-171主机测评

回溯的定义和思想

回溯是一种试探算法，使用搜索的方式寻找问题的解。

回溯的基本思想是：沿着一条路尝试，如果可能存在符合要求的解则前进，如果不可能存在符合要求的解则回溯后退并换一条路尝试。回溯的名称来源于搜索过程中的回溯后退。

使用回溯搜索解的过程中，每一步都有多种选择，因此回溯的时间复杂度较高，通常为非多项式的指数级或阶乘级。搜索过程中，如果遇到不可能存在符合要求的解的情况则可立即回溯后退，停止当前路的继续搜索，这样的减少搜索空间的做法称为剪枝，使用剪枝可以在一定程度上降低回溯的平均时间复杂度。

回溯采用试探性搜索，其本质是深度优先搜索，因此回溯的思想基于深度优先搜索。一般而言，回溯问题比深度优先搜索问题更困难。

回溯和深度优先搜索的区别有以下几点。

深度优先搜索适用于显性图结构（包括树结构），回溯适用于隐性树结构。

深度优先搜索遍历图中的每个结点，回溯遍历每个可能的序列。

深度优先搜索的时间复杂度关于数据规模为线性或多项式，回溯的时间复杂度关于数据规模通常为指数级或阶乘级。