骑士周游算法

马踏棋盘算法代码实现：

骑士周游问题的解决步骤和思路 1.创建棋盘chessBoard,是一一个二维数组 2.将当前位置设置为已经访问,然后根据当前位置，计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置，每走一步,就使用step+1 3.遍历ArrayList中存放的所有位置，看看哪个可以走通,如果走通，就继续，走不通，就回溯 4.判断马儿是否完成了任务，使用step和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0

缺点：棋盘过大时，耗时太久，下面将使用贪心算法优化。

package com.horse; import java.awt.Point; import java.util.ArrayList; public class HorseChessboard { private static int X; //棋盘的列数 private static int Y; //棋盘的行数 //创建一个数组，标记棋盘的各个位置是否被访问过 private static boolean[] visited; //使用一个属性，标记棋盘所有位置是否被访问 private static boolean finished; //如果为true，表示成功 public static void main(String[] args) { X = 8; Y = 8; int row = 1; int column = 1; //创建棋盘 int[][] chessboard = new int[X][Y]; visited = new boolean[X * Y]; long start = System.currentTimeMillis(); traversalChessboard(chessboard,row-1,column-1,1); long end = System.currentTimeMillis(); System.out.println("共用时间为："+(end - start)); for (int[] rows : chessboard){ for (int step : rows){ System.out.print(step+" "); } System.out.println(); } } /** * 功能：完成骑士周游问题算法 * @param chessboard 棋盘 * @param row 马儿当前的位置的行，从0开始 * @param column 马儿当前的位置的列，从0开始 * @param step 是第几步,初始位置是第一步 * */ public static void traversalChessboard(int[][] chessboard,int row,int column,int step){ chessboard[row][column] = step; visited[row * X + column] = true; //标记该位置已经访问 //获取当前位置可以走的位置集合 ArrayList<Point> ps = next(new Point(column, row)); //遍历ps while (!ps.isEmpty()){ Point p = ps.remove(0); //取出下一个可以移动的位置 //判断该点是否被访问过 if (!visited[p.y * X + p.x]){//说明还没有被访问过 traversalChessboard(chessboard,p.y,p.x,step+1); } } //判断马儿是否完成任务，使用step和应走的部署比较 //如果没有达到数量，则表示任务没有完成，则将棋盘置0 if(step < X * Y && !finished){ chessboard[row][column] = 0; visited[row * X + column] = false; }else { finished = true; } } /** * 功能：根据当前位置（curPoint）,计算马儿还能走哪些位置,并放入一个集合中，最多有8个位置 * @param curPoint * @return * */ public static ArrayList<Point> next(Point curPoint){ //创建一个ArrayLi ArrayList<Point> ps = new ArrayList<>(); //创建一个point Point p1 = new Point(); //判断马是否可以走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){ ps.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; } }

使用贪心算法优化骑士周游算法:

1）我们获取当前位置，可以走的下一-个位置的集合//获取当前位置可以走的下一一个位置的集合ArrayList ps = next(new Point(column, rowl); 2）我们需要对ps中所有的Point的下一步的所有集合的数目，进行非递觏排序,就ok, 9, 7, 6，5,2, 1 //递减排序 1, 2,3, 4,5,6, 10, //递增排序 1,2,2,2,3,3,4,5, 6 //非递减 9, 7, 6, 6,6,5, 5,3, 2, 1 //非递增

package com.horse; 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[] visited; //使用一个属性，标记棋盘所有位置是否被访问 private static boolean finished; //如果为true，表示成功 public static void main(String[] args) { X = 8; Y = 8; int row = 1; int column = 1; //创建棋盘 int[][] chessboard = new int[X][Y]; visited = new boolean[X * Y]; long start = System.currentTimeMillis(); traversalChessboard(chessboard,row-1,column-1,1); long end = System.currentTimeMillis(); System.out.println("共用时间为："+(end - start)+"毫秒"); for (int[] rows : chessboard){ for (int step : rows){ System.out.print(step+" "); } System.out.println(); } } /** * 功能：完成骑士周游问题算法 * @param chessboard 棋盘 * @param row 马儿当前的位置的行，从0开始 * @param column 马儿当前的位置的列，从0开始 * @param step 是第几步,初始位置是第一步 * */ public static void traversalChessboard(int[][] chessboard,int row,int column,int step){ chessboard[row][column] = step; visited[row * X + column] = true; //标记该位置已经访问 //获取当前位置可以走的位置集合 ArrayList<Point> ps = next(new Point(column, row)); //对ps进行排序，排序的规则就是对ps的所有对象的下一步的位置的数目，进行非递减排序 sort(ps); //遍历ps while (!ps.isEmpty()){ Point p = ps.remove(0); //取出下一个可以移动的位置 //判断该点是否被访问过 if (!visited[p.y * X + p.x]){//说明还没有被访问过 traversalChessboard(chessboard,p.y,p.x,step+1); } } //判断马儿是否完成任务，使用step和应走的部署比较 //如果没有达到数量，则表示任务没有完成，则将棋盘置0 if(step < X * Y && !finished){ chessboard[row][column] = 0; visited[row * X + column] = false; }else { finished = true; } } /** * 功能：根据当前位置（curPoint）,计算马儿还能走哪些位置,并放入一个集合中，最多有8个位置 * @param curPoint * @return * */ public static ArrayList<Point> next(Point curPoint){ //创建一个ArrayLi ArrayList<Point> ps = new ArrayList<>(); //创建一个point Point p1 = new Point(); //判断马是否可以走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){ ps.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; } //根据当前这个一步的所有的下一步的选择位置，进行非递减排序 public static void sort(ArrayList<Point> ps){ ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { int count1 = next(o1).size(); int count2 = next(o2).size(); if (count1 < count2){ return -1; }else if (count1 == count2){ return 0; }else { return 1; } } }); } }