馬踏棋盤算法，帶你領略回溯+貪心思想

今天在leetcode上刷題，發現有關回溯算法這方面比較薄弱，就上B站找了找相關的學習視頻。於是就看到了尚硅谷的韓順平老師講解的數據結構與算法中的“馬踏棋盤”問題。其代碼實現用到了回溯+貪心思想。覺得很好。寫下這篇文章，算是自己的學習筆記吧。

什麼是回溯？

回溯算法也叫試探法，它是一種系統地搜索問題的解的方法（深度優先搜索）。回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。一般的實現方式是循環+遞歸

什麼是貪心？

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

什麼是馬踏棋盤算法？

1. 馬踏棋盤算法也被稱之為騎士周遊問題
2. 將馬隨機放在國際象棋8*8棋盤上的某個方格中，按照馬走日的規則，每個方格只能進入一次，走遍棋盤上的全部64個方格
3. 遊戲演示：http://www.4399.com/flash/146267_2.htm （可以去4399上玩一玩）

棋盤

馬踏棋盤問題解決步驟和思路

1. 創建棋盤chessBoard，這是一個二維數組
2. 將當前位置設置成為已訪問，然後根據當前的位置，計算千里馬還能走哪些位置，並放入到一個集合中(ArrayList)。千里馬最多有8個位置可供選擇，每走一步，就是用step+1;
3. 遍歷ArrayList中存放的所有位置，看哪個可以走通，如果走通就繼續走；走不通就回溯
4. 判斷千里馬是否完成了任務，使用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 
<>();
		//創建一個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)/<code>

未優化代碼耗時

<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>

貪心法優化後代碼耗時

歡迎大家留言討論，如果有更好的算法可以在評論區留言，多多交流討論。