回溯算法

回溯算法是一种可以找到全部或部分解的通用算法。跟暴力穷举法相比,由于可以对搜索域剪枝,因此效率要高。所谓回溯,就是走到某处后如果发现此路不通,会立即退回到上一步,而不是像暴力法那样仍不管不顾地都试一次。因此,回溯法是一种选优搜索法,又称为试探法。

回溯算法的编写格式:

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的各列,然后再判断某位置是否符合条件(因为还有斜向的攻击)。在退出前从数组中把其列标志清除。

总结:女人真可怕……我本人的话,性格应该跟“车”比较相似。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注