常用十大算法_回溯算法

回溯算法

回溯算法已經在前面詳細的分析過了，詳見猛擊此處。

簡單的講：

回溯算法是一種局部暴力的枚舉算法

循環中，若條件滿足，進入遞歸，開啟下一次流程，若條件不滿足，就不進行遞歸，轉而進行上一次流程。這個過程稱之為回溯

結構往往是在一個循環中，嵌套一個條件判斷，條件判斷中，嵌套一個自身遞歸。三層結構，互相嵌套，缺一不可

【例子】在一個7*7的棋盤中，指定某個起始位置，如何才能使遵循馬走日規則的棋子，将36個棋盤位置全部走一遍，其走過的位置不能再走

算法分析：

馬走日是規則，極限情況下，一個棋子有如下圖8種可選方案，每種方案都對應着一個if語句，8種方案組成我們馬走日的行走政策

常用十大算法_回溯算法

采用回溯算法需要先找到目前棋子所有的可選方案（代碼中由next方法實作），然後周遊每個方案，每個方案采取上述相同的流程，直到找到可以符合題目要求的行走路線，或者是被判定無法再行走而終止遞歸（代碼中由 traversalChessboard 方法實作）

通過上述回溯算法就能完成馬踏棋盤問題求解

代碼實作：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.backtrace;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class 回溯算法_backtrace_馬踏棋盤 {
    private static int X;//棋盤寬度
    private static int Y;//棋盤高度
    private static boolean[] visited;//用于記錄棋牌被通路情況
    private static boolean finish=false;//用于記錄是否完成馬踏棋盤
    public static void main(String[] args) {
        //初始化資料
        X=7;
        Y=7;
        int row=3;//起始點為3行3列
        int col=3;
        visited=new boolean[X*Y];
        int[][] chessboard=new int[X][Y];
        long start=System.currentTimeMillis();//計時開始
        //調用馬踏棋盤解決方法
        traversalChessboard(chessboard,row-1,col-1,1);//為了人機互動友善，需要減-1操作
        long end=System.currentTimeMillis();//計時結束
        System.out.println("運算總耗時："+(end-start));;
        //輸出結果
        for (int[] temp:chessboard){
            System.out.println(Arrays.toString(temp));
        }
    }

    /**
     * 馬踏棋盤解決方案主體（回溯算法）
     * @param chessboard 棋盤
     * @param row 行數
     * @param col 列數
     * @param step 步數
     */
    public static void traversalChessboard(int[][] chessboard,int row,int col,int step){
        chessboard[row][col]=step;//将步數指派到對應棋盤位置上
        visited[row*X+col]=true;//将該處設定為已通路(row被-1)
        //調用next來獲得可選方案，注意next方法處理的時候先處理列，再處理行，是以傳入的point對象為point(y,x)
        ArrayList<Point> allow = next(new Point(col,row));//用于存儲目前可以進入的棋盤（存儲可選方案）
        //回溯算法核心：回溯式的找到所有位置
        while (!allow.isEmpty()){//可選方案非空時
            Point p=allow.remove(0);//拿取可選方案中的頭一個位置
            if (!visited[p.y*X+p.x]){//當該方案位置沒有被通路時
                traversalChessboard(chessboard,p.y,p.x,step+1);//以方案位置再進行上述查找
            }
        }
        //終止回溯條件
        if (step<X*Y && !finish){//當步數不夠且未完成所有位置時
            chessboard[row][col]=0;//初始化本次回溯過程中棋盤資料
            visited[row*X+col]=false;//将該位置仍然設定為未通路
        }else {//解決問題，可以跳出回溯了
            finish=true;
        }

    }

    /**
     * 把目前位置棋子的所有可通路棋盤位置以集合的形式輸出
     * @param curPoint 目前棋子
     * @return 目前位置棋子的所有可通路棋盤位置
     */
    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> allowPoint=new ArrayList<>();//存儲目前位置可以進入的位置
        Point allow=new Point();
        //下面的政策是先計算列，再計算行
        //走位置5
        if ((allow.x=curPoint.x-2)>=0 && (allow.y=curPoint.y-1)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置6
        if ((allow.x=curPoint.x-1)>=0 && (allow.y=curPoint.y-2)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置7
        if ((allow.x=curPoint.x+1)<X && (allow.y=curPoint.y-2)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置0
        if ((allow.x=curPoint.x+2)<X && (allow.y=curPoint.y-1)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置1
        if ((allow.x=curPoint.x+2)<X && (allow.y=curPoint.y+1)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置2
        if ((allow.x=curPoint.x+1)<X && (allow.y=curPoint.y+2)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置3
        if ((allow.x=curPoint.x-1)>=0 && (allow.y=curPoint.y+2)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置4
        if ((allow.x=curPoint.x-2)>=0 && (allow.y=curPoint.y+1)<Y){
            allowPoint.add(new Point(allow));
        }
        return allowPoint;
    }
}

運算總耗時：13322
[11, 8, 3, 20, 23, 16, 5]
[2, 21, 10, 7, 4, 19, 24]
[9, 12, 1, 22, 15, 6, 17]
[40, 33, 44, 13, 18, 25, 36]
[43, 30, 41, 34, 37, 14, 47]
[32, 39, 28, 45, 48, 35, 26]
[29, 42, 31, 38, 27, 46, 49]

上述代碼使用了回溯算法，雖然回溯算法是小規模的暴力，本身已經相較于枚舉算法有了提升。但上述執行個體中，在7*7的棋盤的3行3列上出發的棋子需要運算13322ms（結果不唯一）。這表明這種算法在處理大量資料時是低效率的（回溯了大量無用的步驟）。

為了提高算法效率，就要減少無用步驟的回溯次數

由于一個棋子可能存在多個可進入的位置，而進入這些位置中又可能會存在多個可進入位置。那麼我們按照這些位置的可能進入位置數升序排列，先運算可能性小的，再運算可能性大的。即更改了回溯的政策。這樣的優化一定程度上（與運氣有關）可以大大優化算法效率。

優化代碼：

package cn.dataStructureAndAlgorithm.demo.tenAlgorithm.backtrace;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class 回溯算法_backtrace_馬踏棋盤 {
    private static int X;//棋盤寬度
    private static int Y;//棋盤高度
    private static boolean[] visited;//用于記錄棋牌被通路情況
    private static boolean finish=false;//用于記錄是否完成馬踏棋盤
    public static void main(String[] args) {
        //初始化資料
        X=7;
        Y=7;
        int row=3;//起始點為3行3列
        int col=3;
        visited=new boolean[X*Y];
        int[][] chessboard=new int[X][Y];
        long start=System.currentTimeMillis();//計時開始
        //調用馬踏棋盤解決方法
        traversalChessboard(chessboard,row-1,col-1,1);//為了人機互動友善，需要減-1操作
        long end=System.currentTimeMillis();//計時結束
        System.out.println("運算總耗時："+(end-start));;
        //輸出結果
        for (int[] temp:chessboard){
            System.out.println(Arrays.toString(temp));
        }
    }

    /**
     * 馬踏棋盤解決方案主體（回溯算法）
     * @param chessboard 棋盤
     * @param row 行數
     * @param col 列數
     * @param step 步數
     */
    public static void traversalChessboard(int[][] chessboard,int row,int col,int step){
        chessboard[row][col]=step;//将步數指派到對應棋盤位置上
        visited[row*X+col]=true;//将該處設定為已通路(row被-1)
        //調用next來獲得可選方案，注意next方法處理的時候先處理列，再處理行，是以傳入的point對象為point(y,x)
        ArrayList<Point> allow = next(new Point(col,row));//用于存儲目前可以進入的棋盤（存儲可選方案）
        sort(allow);//!!!對結果進行排序優化!!!
        //回溯算法核心：回溯式的找到所有位置
        while (!allow.isEmpty()){//可選方案非空時
            Point p=allow.remove(0);//拿取可選方案中的頭一個位置
            if (!visited[p.y*X+p.x]){//當該方案位置沒有被通路時
                traversalChessboard(chessboard,p.y,p.x,step+1);//以方案位置再進行上述查找
            }
        }
        //終止回溯條件
        if (step<X*Y && !finish){//當步數不夠且未完成所有位置時
            chessboard[row][col]=0;//初始化本次回溯過程中棋盤資料
            visited[row*X+col]=false;//将該位置仍然設定為未通路
        }else {//解決問題，可以跳出回溯了
            finish=true;
        }

    }

    /**
     * 把目前位置棋子的所有可通路棋盤位置以集合的形式輸出
     * @param curPoint 目前棋子
     * @return 目前位置棋子的所有可通路棋盤位置
     */
    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> allowPoint=new ArrayList<>();//存儲目前位置可以進入的位置
        Point allow=new Point();
        //下面的政策是先計算列，再計算行
        //走位置5
        if ((allow.x=curPoint.x-2)>=0 && (allow.y=curPoint.y-1)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置6
        if ((allow.x=curPoint.x-1)>=0 && (allow.y=curPoint.y-2)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置7
        if ((allow.x=curPoint.x+1)<X && (allow.y=curPoint.y-2)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置0
        if ((allow.x=curPoint.x+2)<X && (allow.y=curPoint.y-1)>=0){
            allowPoint.add(new Point(allow));
        }
        //走位置1
        if ((allow.x=curPoint.x+2)<X && (allow.y=curPoint.y+1)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置2
        if ((allow.x=curPoint.x+1)<X && (allow.y=curPoint.y+2)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置3
        if ((allow.x=curPoint.x-1)>=0 && (allow.y=curPoint.y+2)<Y){
            allowPoint.add(new Point(allow));
        }
        //走位置4
        if ((allow.x=curPoint.x-2)>=0 && (allow.y=curPoint.y+1)<Y){
            allowPoint.add(new Point(allow));
        }
        return allowPoint;
    }
    public static void sort(ArrayList<Point> allow){
        allow.sort(new Comparator<Point>(){//覆寫排序方法，使用Lambda表達式完成
            @Override
            public int compare(Point p1,Point p2) {
                return next(p1).size()-next(p2).size();
            }
        });
    }
}

運算總耗時：637
[47, 16, 3, 30, 7, 18, 5]
[2, 29, 46, 17, 4, 31, 8]
[15, 48, 1, 40, 45, 6, 19]
[36, 41, 28, 49, 34, 9, 32]
[27, 14, 35, 44, 39, 20, 23]
[42, 37, 12, 25, 22, 33, 10]
[13, 26, 43, 38, 11, 24, 21]

你看運算時間從13秒優化到不到1秒，這就是程式設計的魅力（doge）

還有一個值得注意的地方是：兩次結果不同。這是由于回溯算法的不确定性組成的（我們更改了回溯的政策）

其他常用算法，見下各連結

【常用十大算法_二分查找算法】

【常用十大算法_分治算法】

【常用十大算法_貪心算法】

【常用十大算法_動态規劃算法（DP）】

【常用十大算法_KMP算法】

【常用十大算法_普裡姆（prim）算法，克魯斯卡爾（Kruskal）算法】

【常用十大算法_迪傑斯特拉（Dijkstra）算法，弗洛伊德（Floyd）算法】

【資料結構與算法整理總結目錄：＞】<-- 寶藏在此（doge）

常用十大算法_回溯算法

回溯算法

繼續閱讀

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希