文章和代码曾经归档至【Github 仓库:https://github.com/timerring/java-tutorial】或者公众号【AIShareLab】回复 java 也可获取。
骑士环游问题
算法优化意义
- 算法是程序的灵魂,为什么有些程序能够在海量数据计算时,仍然保
持高速计算? - 编程中算法很多,比方八大排序算法 (冒泡、抉择、插入、快排、归并.
希尔、基数、堆排序)、查找算法、分治算法、动静布局算法、KMP 算法、贪婪算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法。
经典算法面试题 - 骑士环游问题
马踏棋盘算法介绍
- 马踏棋盘算法也被称为骑士环游问题
- 将马随机放在国际象棋的 8×8 棋盘
Board[0 ~7][0~7]
的某个方格中,马按走棋规定 (马走日字) 进行挪动。要求每个方格只进入一次,走遍棋盘上全副 64 个方格。 - 游戏演示:
https://u.ali213.net/games/horsesun/index.html?game_code=403 - 会应用到图的遍历算法(DFS)+ 贪婪算法优化
- 马踏棋盘问题 (骑士环游问题) 实际上是图的深度优先搜寻 (DFS) 的利用。
- 如果应用回溯 (就是深度优先搜寻) 来解决, 如果马儿踏了 53 个点,如图: 走到了第 53 个, 坐标(1,0),发现曾经走到止境, 没方法,那就只能回退了,查看其余的门路,就在棋盘上不停的回溯 …..,思路剖析 + 代码实现。
- 先用根本形式来解决,而后应用贪婪算法 (greedyalgorithm) 进行优化。解决马踏棋盘问题, 领会到不同的算法对程序效率的影响。
- 应用后面的游戏来验证算法是否正确。
骑士环游问题的解决步骤和思路剖析
- 创立棋盘
chessBoard
, 是二维数组 - 将以后地位设置为曾经拜访, 而后依据以后地位,计算马儿还能走哪些地位,并放入到一个汇合中(ArrayList), 最多有 8 个,每走一步,应用 step + 1。
- 遍历 ArrayList 中寄存的所有地位,看看那个能够走,如果能够走通,就持续,走不通,就回溯。
- 判断马儿是否实现了工作,应用 step 和应该走的步数比拟,如果没有达到数量,则示意没有实现工作,将整个棋盘设置为 0。
留神: 马儿走的策略不同,则失去的后果也不一样,效率也不一样。
对代码应用 贪婪算法,进行优化,进步速度:
剖析
- 咱们当初走的下一个地位,是依照咱们的顺时针来筛选地位,因而抉择的这个点的下一个能够走的地位的个数是不确定的.
- 优化思路是: 咱们应该抉择下一个的下一个能够走的地位较少的点,开始走,这样能够缩小回溯。
- 代码: 对咱们的 ps 汇合依照能够走的下一个地位的次数进行排序,升序排序。
package com.hspedu;
import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
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();}
}
// 写一个办法,对 ps 的各个地位,能够走的下一个地位的次数进行排序, 把可能走的下一个地位从小到大排序
public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {return next(o1).size() - next(o2).size();}
});
}
// 编写最外围的算法,遍历棋盘,如果遍历胜利,就把 finished 设置为 true ,
// 并且,将马儿走的每一步 step,记录到 chessBoard
public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {
// 先把 step 记录到 chessBoard
chessBoard[row][col] = step;
// 把这个地位,设置为曾经拜访
visited[row * X + col] = true;
// 获取以后这个地位能够走的下一个地位有哪些
ArrayList<Point> ps = next(new Point(col, row)); // 留神这里的解决:col - X , row - Y
sort(ps);// 排序:咱们应该抉择下一个的下一个能够走的地位较少的点,开始走,这样能够缩小回溯
// 遍历
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) {
// 创立一个 ArrayList
ArrayList<Point> ps = new ArrayList<>();
// 创立一个 Point 对象(点 / 地位), 筹备放入到 ps
Point p1 = new Point();
// 判断在 curPoint 是否能够走如下地位,如果能够走,就将该点(Point) 放入到 ps
// 判断是否能够走 5 地位
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 6 地位
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 7 地位
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 0 地位
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 1 地位
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 2 地位
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 3 地位
if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
// 判断是否能够走 4 地位
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1)); // 这里肯定要 new Point
}
return ps;
}
}