python 回溯法 记录

一直不是太理解回溯法，这几天集中学习了一下，记录如下。

回溯法有“通用的解题法”之称。

也叫试探法，它是一种系统地搜索问题的解的方法。

从一条路往前走，能进则进，不能进则退回来，换一条路再试。

定义一个解空间（子集树、排列树二选一）

利用适于搜索的方法组织解空间。  

利用深度优先法搜索解空间。  

利用剪枝函数避免移动到不可能产生解的子空间。

是否满足显约束（存在）

是否满足隐约束（最优）

遍历子集树，时间复杂度 O(2^n)

如果解的长度是不固定的，那么解和元素顺序无关，即可以从中选择0个或多个。例如：子集，迷宫，...

如果解的长度是固定的，那么解和元素顺序有关，即每个元素有一个对应的状态。例如：子集，8皇后，...

解空间的个数指数级别的，为2^n,可以用子集树来表示所有的解

适用于：幂集、子集和、0-1背包、装载、8皇后、迷宫、...

遍历排列树，时间复杂度O(n!)

解空间是由n个元素的排列形成，也就是说n个元素的每一个排列都是解空间中的一个元素，那么，最后解空间的组织形式是排列树

适用于：n个元素全排列、旅行商、...