回溯算法是一种可以找到全部或部分解的通用算法。跟暴力穷举法相比,由于可以对搜索域剪枝,因此效率要高。所谓回溯,就是走到某处后如果发现此路不通,会立即退回到上一步,而不是像暴力法那样仍不管不顾地都试一次。因此,回溯法是一种选优搜索法,又称为试探法。
回溯算法的编写格式:
boolean backtrack(candidate) { // 递归终止条件 if (isSolution(candidate)) { output(solution); return true; } // 标记当前结点(比如把当前结点标记在路径里) place(candidate); // 遍历和尝试所有下一级的结点 for (nextCandidate : listOfCandidates) { // 剪枝:对于不合适的结点,直接跳过 if (isValid(nextCandidate)) { // 继续深入到下一层。如果最终能找到解,返回;否则尝试下一个下级结点 if (backtrack(nextCandidate)) { return true; } } } // 清除当前结点的标记(比如把当前结点从路径上移除,这意味着从其他结点还能继续来这里) remove(candidate); return false; }
说明:
- backtrack函数是一个调用自己的递归函数,所以要有终止递归的条件
- 里面有一个循环,用于尝试所有下一级的结点。比如迷宫问题,当走到了某点后,继续尝试相邻的三个结点(前一个结点除外)。循环里应该有剪枝,避免不必要的递归调用开销。
- 经常需要标记当前结点,并在尝试完从这里开始的所有可能性后清除标记。(比如,不要重复访问已标记的地方)
例题:N皇后问题(八皇后问题)
暴力穷举法:把第一个皇后放置在第一行的每个位置,然后搜索所有的解(尝试把第二个皇后放在其他所有位置,再尝试把第三个皇后放在其他所有位置……)。其实这已经不太“暴力”了,因为完全的“暴力搜索”应该是把第一个皇后也放在棋盘的所有位置,最后再去掉重复的解。
回溯法:把第一个皇后放在第一行的每个位置,由于第一行肯定不能再放置皇后,因此,尝试把第二个皇后放在第二行的每个位置,判断一下是否满足条件,把不满足条件的跳过,然后再在第三行尝试放置第三个皇后……
进一步优化:保存一个长度为N的数组,在某一列放置过皇后的话,就把相应的数组位置设置为true。这样,在下一行放置下一个皇后时,先跳过所有置为true的各列,然后再判断某位置是否符合条件(因为还有斜向的攻击)。在退出前从数组中把其列标志清除。
总结:女人真可怕……我本人的话,性格应该跟“车”比较相似。