回溯法

要求解一个问题，最可靠的一种方法是：列出所有候选解，然后逐个检查，在检查所有或部分候选解后，便可找到所需要的解。理论上，只要候选解的数量有限，而且在检查了所有或部分候选解之后可以确定所需解，这种方法就是可行的。不过在实际应用中，这种方法很少用，因为候选解的数量通常都非常大。而即使速度最快的计算机，也只能对实例规模相当小的问题在合理的时间内解决。

回溯法和分支定界法是对候选解进行系统检查的两种方法。这两种方法使最坏情况下和一般情况下的求解时间大大减少。事实上，这两种方法使我们省去了对很大一部分候选解的检查，同时还使我们能够找到所需要的解。因此，这两种方法经常可以用来求解实例规模很大的问题。

一、算法思想

回溯法（backtracking）是搜索问题解的一种系统方法。

二、应用