回溯算法

定义

回溯算法实际上一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

N 对括号问题

给出 N 代表生成括号的对数,请写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 N = 3,生成结果为:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

这是一个很经典的回溯法问题,代码如下:

public static List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backTracking("", result, n, n);
    return result;
}

public static void backTracking(String s, List<String> result, int left, int right) {
    if (left == 0 && right == 0) {
        result.add(s);
        return;
    }
    if (right > left) {
        backTracking(s + ")", result, left, right - 1);
    }
    if (left > 0) {
        backTracking(s + "(", result, left - 1, right);
    }
}

对于回溯法来说,必须齐备的三要素:

  1. 选择。在这个例子中,解就是一个合法的括号组合形式,而选择无非是放入左括号,还是放入右括号。
  2. 条件。在这个例子中,选择是放入左括号,还是放入右括号,是有条件约束的,不是随便放的。而这个约束就是括号的数量。只有剩下的右括号比左括号多,才能放右括号。只有左括号数量大于0才能放入左括号。这里if的顺序会影响输出的顺序,但是不影响最终解;
  3. 结束。这里的结束条件很显然就是,左右括号都放完了。

下面列出了每次递归调用时,一些主要的参数(从左至右分别为当前结果,左括号剩余数,右括号剩余数,绿色为最终结果):

N 皇后问题

N 皇后问题是指在 N * N 的棋盘上放置 N 个皇后,使这 N 个皇后无法吃掉对方(也就是说两两不在一行,不在一列,也不在对角线上)。经典的是 8 皇后问题,这里我们为了简单,以 4 皇后为例。

  1. 首先利用回溯算法,先给第一个皇后安排位置,如下图所示,安排在(1,1)
  2. 然后给第二个皇后安排位置,可知(2,1),(2,2)都会产生冲突,因此可以安排在(2,3)
  3. 然后安排第三个皇后,在第三行没有合适的位置,因此回溯到第二个皇后
  4. 重新安排第二个皇后的位置,安排到(2,4),然后安排第三个皇后到(3,2),安排第四个皇后有冲突,因此要回溯到第三个皇后
  5. 第三个皇后也就仅此一个位置,无处可改,故继续向上回溯到第二个皇后,也没有位置可更改,因此回溯到第一个皇后
  6. 更改第一个皇后的位置,继续上面的做法,直至找到所有皇后的位置,如下图所示。


public class NQueensII {  
    int[] x;//当前解    
    int N;//皇后个数  
     int sum = 0;//当前已找到的可行方案数  
    public int totalNQueens(int n) {  
        N = n;  
        x = new int[N+1];  
        backTrace(1);  
        return sum;  
    }  

    /** 
     * 判断该位置能不能放,需要判断对角线和同列上是否可放
     */  
    private boolean place(int col){  
        for(int i = 1; i < col; i++){  
            if(Math.abs(col - i)==Math.abs(x[col]-x[i])||x[col]==x[i]){  
                return false;  
            }  
        }  
        return true;  
    }  

    private void backTrace(int t) {  
        if(t>N){  
            sum++;  
        }else {  
            //第t行,遍历所有的节点  
            for(int j = 1; j <= N; j++) {  
                 x[t] = j ;  
                 //如果第j个节点可以放下皇后  
                if(place(t)){  
                    //接着放下一个  
                    backTrace(t+1);  
                }  
            }  
        }  

    }  

    public static void main(String[] args) {  
        NQueensII n = new NQueensII();  
        System.out.println(n.totalNQueens(4));  
    }  
} 

总结

回溯法有通用解法的美称,是一个很重要的算法,对于很多问题,如迷宫等都有很好的效果。

回溯算法的精髓就是在不满足条件后进行“回溯”,尝试其他路径,直至找出所有解。

回溯算法虽然也是 Brute-Force (暴力破解),但是它可以避免去搜索很多的不可能的情况,因此算法是优于 Brute-Force 的。

本作品采用知识共享署名-非商业性使用-禁止演绎 3.0 未本地化版本许可协议进行许可。 打赏

微信 支付宝 支付宝领红包

如果觉得我的文章对您有用,请随意赞赏~

发表评论

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