3.7.6 回溯算法会影响算法效率吗

下面是回溯的3个要素。

（1）解空间：要解决问题的范围，不知道范围的搜索是不可能找到结果的。

（2）约束条件：包括隐形的和显性的，题目中的要求以及题目描述中隐含的约束条件，是搜索有解的保证。

（3）状态树：构造深搜过程的依据，整个搜索以状态树展开。

回溯算法适合解决没有要求求出最优解的问题，如果采用，一定要注意跳出条件及搜索完成的标志，否则会陷入泥潭不可自拔。

下面是影响算法效率的因素。

· 搜索树的结构、解的分布、约束条件的判断。

· 改进回溯算法的途径。

· 搜索顺序。

· 节点少的分支优先，解多的分支优先。

· 让回溯尽量早发生。