1. 首頁 > 生活百科 > >

day53-馬踏棋盤

生活百科day53-馬踏棋盤

馬踏棋盤1.算法優化的意義

  1. 算法是程序的靈魂，為什么有些程序可以在海量數據計算時，依舊保持高速計算？
  2. 編程中算法很多，比如八大排序算法（冒泡、選擇、插入、快排、歸并、希爾、基數、堆排序）、查找算法、分治算法、動態規劃算法、KMP算法、貪心算法、普利姆算法、克魯斯卡爾算法、迪杰斯特拉算法、弗洛伊德算法
  3. 下面以騎士周游問題為例，體驗算法優化程序的意義，感受算法的威力
2.騎士周游問題
  • 馬踏棋盤算法介紹和游戲演示
  1. 馬踏棋盤算法也被稱為騎士周游問題
  2. 將馬隨機放在國際象棋的8*8棋盤Board[0-7][0-7]的某個方格中，馬按走棋規則移動（馬只能走日字） 。要求每個方格只進入一次，走遍棋盤上全部64個方格
  3. 會使用到圖的遍歷算法（DFS）+貪心算法優化

day53-馬踏棋盤

文章插圖
【day53-馬踏棋盤】馬踏棋盤(騎士周游問題)實際上是圖的深度優先搜索(DFS)的應用 。
使用回溯(就是深度優先搜索)來解決，假如馬兒踏了53個點 ， 如圖，走到了第53個，坐標為(1,0)，發現已經走到了盡頭 ， 沒辦法，那就只能回退了，查看其它的路徑，就在棋盤上不停地回溯……
這里我們先用基本的方法解決 ， 然后使用貪心算法(greedyalgorithm)進行優化 。解決馬踏棋盤問題，體會到不同的算法對程序效率的影響
3.思路分析
day53-馬踏棋盤

文章插圖
  1. 創建一個棋盤chessBoard，是一個二維數組
  2. 將馬兒當前位置設置為已經訪問 ， 然后根據當前位置，計算馬兒還能走哪些位置，并放入到一個集合中(ArrayList) ， 每一個位置的下一步最多有8個方向，每走一步 ， 就使用step+1
  3. 遍歷ArrayList中存放的所有位置，看看哪個可以走，如果可以走通，就繼續，走不通，就回溯
  4. 判斷馬兒是否完成了任務，使用step和應該走的步數比較，如果沒有達到數量，則表示沒有完成任務，將整個棋盤設置為0
注意：馬兒走的策略不同，得到的結果也會不一樣 ， 效率也不一樣 。
package li;import java.awt.*;import java.util.ArrayList;/** * @author 李 * @version 1.0 * 馬踏棋盤 */public class HorseChessBoard {//定義屬性private static int X = 6;//表示col-列private static int Y = 6;//表示row-行private static int[][] chessBoard = new int[Y][X];//棋盤private static boolean[] visited = new boolean[X * Y];//表示記錄某個位置是否走過private static boolean finished = false;//記錄馬兒是否遍歷完棋盤public static void main(String[] args) {//測試int row = 2;int col = 2;long start = System.currentTimeMillis();traversalChessBoard(chessBoard, row-1, col-1, 1);//將棋盤上開始的位置設置為起始第一步long end = System.currentTimeMillis();System.out.println("遍歷耗時="+(end - start));//輸出當前棋盤的情況for (int[] rows : chessBoard) {for (int step : rows) {//step表示 這個位置是馬兒應該走的第幾步System.out.print(step + "\t");}System.out.println();}}//最核心的算法，遍歷棋盤，如果遍歷成功，就將finished的值設置為true，//并且將馬兒走的每一步step記錄到chessBoardpublic static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {//先將step記錄到chessBoardchessBoard[row][col] = step;//把這個位置設置為已經訪問visited[row * X + col] = true;//就是將二維數組的下標對應到一位數組下標，按行的順序存放（注意下標從0開始）//獲取當前位置可以走的下一個位置有哪些ArrayList<Point> ps = next(new Point(col, row));//注意col-X,row-Y//遍歷while (!ps.isEmpty()) {//取出當前ps集合的第一個位置（點）Point p = ps.remove(0);//每取出一個點，就從集合中刪除這個點//判斷該點的位置是否走過，如果沒有走過 ， 就遞歸遍歷if (!visited[p.y * X + p.x]) {//遞歸遍歷traversalChessBoard(chessBoard, p.y, p.x, step + 1);}}//當退出while循環后，看看是否遍歷成功，如果沒有成功，就重置相應的值，然后進行回溯if (step < X * Y && !finished) {//重置chessBoard[row][col] = 0;visited[row * X + col] = false;} else {finished = true;}}//編寫方法，可以獲取當前位置 可以走的下一步 的所有位置(Point表示x,y)public static ArrayList<Point> next(Point curPoint) {//curPoint表示當前點//先創建一個ArrayListArrayList<Point> ps = new ArrayList<>();//創建一個Point對象，表示一個位置/點，準備放入到 ps集合中Point p1 = new Point();//判斷在curPoint位置 ， 是否可以走如下位置，如果可以走 ， 就將該點(p1)放入到集合ps中/*** 馬走日的話 ， 每個點就有八個方向可以走，并且這八個方向對于當前坐標的相對坐標都是固定的，* 通過當前坐標算出八個方向的相對坐標，然后排除掉那些可能會走出界的方向*///判斷是否可以走5位置if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走6位置if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走7位置if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {//注意索引的范圍是：0到X-1ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走0位置if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走1位置if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走2位置if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走3位置if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));//要創建一個新的點}//判斷是否可以走4位置if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));//要創建一個新的點}return ps;}}

推薦閱讀