【内部资料】回溯法

回溯法

回溯法 (Backtracking)也算是枚举法中的一种。对于某些问题而言，回溯法是一种可以找出所有(或一部分)解的一般性算法，同时避免枚举不正确的数值。一旦发现不正确的数值，就不再递归到下一层，而是回溯到上一层，以节省时间，是一种走不通就退回再走的方式。它的特点主要是在搜索过程中寻找问题的解，当发现不满足求解条件时，就回溯(返回)，尝试别的路径，避免无效搜索。

例如，老鼠走迷宫就是一种“回溯法” (Backtracking) 的应用。老鼠走迷宫问题的陈述是:假设把一只大老鼠放在一个没有盖子的大迷宫盒的入口处,盒中有许多墙使得大部分的路径都被挡住而无法前进。老鼠可以按照尝试错误的方法找到出口。不过，这只老鼠必须具备走错路时就会退回来并把走过的路记下来，避免下次走重复的路，就这样直到找到出口为止。简单来说，老鼠行进时，必须遵守以下 3 个原则。

(1) 一次只能走一格。

(2) 遇到墙无法往前走时，则退回一步找找看是否有其他的路可以走。

(3) 走过的路不会再走第二次。