01-回溯算法

第15章　回溯算法

回溯 （backtracking）算法，又称为试探算法，实际上类似于枚举的搜索尝试过程。它在搜索尝试过程中寻找问题的解，当发现不满足求解条件时，就“回溯”返回，尝试其他路径。回溯算法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先的选择并不优或达不到目标，就退回上一步重新选择。这种走不通就退回再走的方法称为回溯，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的、规模较大的问题都可以使用回溯算法求解，回溯算法有“通用解题算法”的美称。