数据结构与算法--算法思维之回溯算法_回溯算法的优缺点

目录

回溯算法

概念

经典问题：N皇后问题

时间复杂度

优缺点

适用场景

---

回溯算法

概念

        回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。

经典问题：N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  

        我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。

public class NQueens {
 
    static int QUEENS = 8;
 
    int[] result = new int[QUEENS];
 
    public void setQueens(int row){
        if (row == QUEENS){
            printQueens();
            return;
        }
 
        for (int col = 0; col < QUEENS; col++) {
 
            if (isOk(row, col)){
                //设置列
                result[row] = col;
                //开始下一行
                setQueens(row + 1);
            }
 
        }
    }
 
    private void printQueens(){
        for (int i = 0; i < QUEENS; i++) {
            for (int j = 0; j < QUEENS; j++) {
                if (result[i] == j){
                    System.out.print("Q| ");
                }else {
                    System.out.print("*| ");
                }
            }
            System.out.println();
        }
        System.out.println("---------------------------------");
    }
 
    private boolean isOk(int row, int col){
        int leftup = col - 1;
        int rightup = col + 1;
 
        for (int i = row -1; i >= 0; i--){
            //列上存在queen
            if (result[i] == col){
                return false;
            }
            //左上对角线存在queen
            if (leftup >= 0){
                if (result[i] == leftup){
                    return false;
                }
            }
 
            //右下对角线存在queen
            if (rightup < QUEENS){
                if (result[i] == rightup) {
                    return false;
                }
            }
            leftup--;
            rightup++;
        }
        return true;
    }
 
    public static void main(String[] args) {
        fangge queens = new fangge();
        queens.setQueens(0);
    }
 
}

 

时间复杂度

 N皇后问题的时间复杂度为： 实际为 O（n!） 实际为n！/ 2

 

优缺点

        优点： 回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。

        劣势： 效率相对于低（动态规划）

 

适用场景

        回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高， 是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率会非常低