回溯法

一、回溯法基础

1. 思想：能进则进，进不了则换，换不了则退（深度优先搜索）

2. 要素：

   1. 首先确定解的形式，确定问题的解空间
      1. 解空间：
         1. 定义：所有解组成的空间
         2. 解空间的组织结构：需要按照一定套路，即一定的组织结构搜索最优解，把这种组织结构形象地用树表示出来，就成为解空间树
         3. 搜索解空间：
            1. 隐约束：对能否得到问题的可行解或最优解做出的约束
               1. 如果不满足，就没有比踹开再沿着该结点的分支继续搜索，由此隐约束也称为剪枝函数（不再搜索该分支） eg：3个物体的01[[背包问题]]中，前两个物体放入后，已经超重，则不再继续搜索该分支
               2. 隐约束（剪枝函数）包含了约束函数和限界函数
         4. 解空间的大小和剪枝函数的好坏都直接影响搜索效率

            几个术语的说明： 1. 扩展结点：一个正在生成孩子的结点 2. 活结点：一个自身生成，但孩子还没有全部生成的结点 3. 死结点：一个孩子已经全部生成的结点 4. 子孙：结点E的子树上所有的结点都是E的子孙 5. 祖宗：从结点E到树根路径上的所有节点都是E的祖宗

3. 解题的方法

   1. 定义解空间
      1. 通过显约束限定解空间的大小
   2. 确定解空间的组织结构
      1. 解空间分为子集树、排列树、m叉树等
   3. 搜索解空间
      1. 回溯法是按照深度优先搜索策略，根据隐约束，在解空间中搜索问题的可行解或最优解，当发现当前结点不满足求解条件时，就回溯尝试其他的路径
      2. 如果问题只是要求可行解，则只需要设定约束函数即可
      3. 如果要求最优解，则需要设定约束函数和限界函数
4. 回溯法解题的关键：设计有效的显约束和隐约束