请问什么是回溯算法

回溯（backtracking）是一种系统地搜索问题解答的方法.为了实现回溯,首先需要为问题定义一个解空间（solution space）,这个空间必须至少包含问题的一个解（可能是最优的）.
下一步是组织解空间以便它能被容易地搜索.典型的组织方法是图(迷宫问题)或树(N皇后问题).
一旦定义了解空间的组织方法,这个空间即可按深度优先的方法从开始节点进行搜索.
回溯方法的步骤如下：
1) 定义一个解空间,它包含问题的解.
2) 用适于搜索的方式组织该空间.
3) 用深度优先法搜索该空间,利用限界函数避免移动到不可能产生解的子空间.
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间.在搜索期间的任何时刻,仅保留从开始节点到当前节点的路径.因此,回溯算法的空间需求为O（从开始节点起最长路径的长度）.这个特性非常重要,因为解空间的大小通常是最长路径长度的指数或阶乘.所以如果要存储全部解空间的话,再多的空间也不够用.