今天在leetcode上刷題，發現有關回溯算法這方面比較薄弱，就上B站找了找相關的學習視頻。於是就看到了尚硅谷的韓順平老師講解的數據結構與算法中的“馬踏棋盤”問題。其代碼實現用到了回溯+貪心思想。覺得很好。寫下這篇文章，算是自己的學習筆記吧。
什麼是回溯？
回溯算法也叫試探法，它是一種系統地搜索問題的解的方法（深度優先搜索）。回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。一般的實現方式是循環+遞歸
什麼是貪心？
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
什麼是馬踏棋盤算法？
馬踏棋盤算法也被稱之為騎士周遊問題將馬隨機放在國際象棋8*8棋盤上的某個方格中，按照馬走日的規則，每個方格只能進入一次，走遍棋盤上的全部64個方格遊戲演示：http://www.4399.com/flash/146267_2.htm （可以去4399上玩一玩）棋盤
馬踏棋盤問題解決步驟和思路
創建棋盤chessBoard，這是一個二維數組將當前位置設置成為已訪問，然後根據當前的位置，計算千里馬還能走哪些位置，並放入到一個集合中(ArrayList)。千里馬最多有8個位置可供選擇，每走一步，就是用step+1;遍歷ArrayList中存放的所有位置，看哪個可以走通，如果走通就繼續走；走不通就回溯判斷千里馬是否完成了任務，使用step和應該走的步數去比較，如果沒有達到數量，則表示沒有完成任務，將棋盤置零思考：千里馬不同的走法，會得到不同的結果，效率會有影響。（為使用貪心法優化埋下伏筆）
代碼實現
未優化的代碼
<code>package com.algorithm; import java.awt.Point; import java.util.ArrayList; import java.util.Comparator; //馬踏棋盤問題 public class HorseChessboard { private static int X;//棋盤的列數 private static int Y; //棋盤的行數 private static boolean[] isVisited; //判斷當前位置是否被訪問 private static boolean isFinished=false; //判斷最後是否完成任務 public static void main(String[] args) { System.out.println("馬踏棋盤算法優化後開始運行~"); X=8; //棋盤列數 Y=8; //棋盤行數 int row=1; //起始位置行 int col=1; //起始位置列 int[][] chessBoard=new int[X][Y]; isVisited=new boolean[X*Y]; //計算耗時 long start=System.currentTimeMillis(); travel(chessBoard,row-1,col-1,1); long end=System.currentTimeMillis(); System.out.println("共耗時："+(end-start)+"毫秒"); //輸出棋盤最後情況 for(int[] rows:chessBoard) { for(int step: rows) { System.out.print(step+"\t"); } System.out.println(); } } /** * 千里馬移動的方法 * @param chessBoard 棋盤 * @param row 千里馬當前位置的行 * @param col 千里馬當前位置的列 * @param step 移動的步數 */ public static void travel(int[][] chessBoard,int row,int col,int step) { chessBoard[row][col]=step; //數組中存儲的就是移動的步數 isVisited[row*X+col]=true; //標記該位置被訪問 //獲取當前位置可以走的下一個位置的集合 ArrayList ps=next(new Point(col,row)); //遍歷ps while(!ps.isEmpty()) { Point p=ps.remove(0); if(!isVisited[p.y*X+p.x]) { //還沒有訪問過 travel(chessBoard,p.y,p.x,step+1); } } //判斷千里馬是否完成任務 if(step next(Point curPoint){ //創建一個ArrayList ArrayList list=new ArrayList
未優化代碼耗時
<code>package com.algorithm; import java.awt.Point; import java.util.ArrayList; import java.util.Comparator; //馬踏棋盤問題 public class HorseChessboard { private static int X;//棋盤的列數 private static int Y; //棋盤的行數 private static boolean[] isVisited; //判斷當前位置是否被訪問 private static boolean isFinished=false; //判斷最後是否完成任務 public static void main(String[] args) { System.out.println("馬踏棋盤算法優化後開始運行~"); X=8; Y=8; int row=1; int col=1; int[][] chessBoard=new int[X][Y]; isVisited=new boolean[X*Y]; long start=System.currentTimeMillis(); travel(chessBoard,row-1,col-1,1); long end=System.currentTimeMillis(); System.out.println("共耗時："+(end-start)+"毫秒"); //輸出棋盤最後情況 for(int[] rows:chessBoard) { for(int step: rows) { System.out.print(step+"\t"); } System.out.println(); } } /** * 千里馬移動的方法 * @param chessBoard 棋盤 * @param row 千里馬當前位置的行 * @param col 千里馬當前位置的列 * @param step 移動的步數 */ public static void travel(int[][] chessBoard,int row,int col,int step) { chessBoard[row][col]=step; //數組中存儲的就是移動的步數 isVisited[row*X+col]=true; //標記該位置被訪問 //獲取當前位置可以走的下一個位置的集合 ArrayList ps=next(new Point(col,row)); sort(ps); //遍歷ps while(!ps.isEmpty()) { Point p=ps.remove(0); if(!isVisited[p.y*X+p.x]) { //還沒有訪問過 travel(chessBoard,p.y,p.x,step+1); } } if(step next(Point curPoint){ //創建一個ArrayList ArrayList list=new ArrayList<>(); //創建一個Point Point p1=new Point(); //表示千里馬可以走5這個位置 if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0) { list.add(new Point(p1)); } //表示千里馬可以走6這個位置 if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0) { list.add(new Point(p1)); } //表示千里馬可以走7這個位置 if((p1.x=curPoint.x+1)=0) { list.add(new Point(p1)); } //表示千里馬可以走0這個位置 if((p1.x=curPoint.x+2)=0) { list.add(new Point(p1)); } //表示千里馬可以走1這個位置 if((p1.x=curPoint.x+2)=0&&(p1.y=curPoint.y+2)=0&&(p1.y=curPoint.y+1) ps) { ps.sort(new Comparator() { @Override public int compare(Point o1, Point o2) { // TODO Auto-generated method stub int count1=next(o1).size(); int count2=next(o2).size(); if(count1/<code>
貪心法優化後代碼耗時
歡迎大家留言討論，如果有更好的算法可以在評論區留言，多多交流討論。