马踏棋盘/骑士周游问题
DFS算法的应用
思路分析
骑士周游问题的解决步骤和思路：
-
创建棋盘
初始化一个棋盘 chessBoard，它是一个二维数组，最终会显示出棋盘被访问的顺序（从1开始计数），也作为标记某个点是否被访问过使用（0则表示未访问过）。
-
设置当前位置已访问
将骑士的当前位置标记为已访问，并根据当前位置计算骑士能够跳到的合法位置。将这些位置存放在一个集合（如 ArrayList）中，最多包含8个合法的跳跃位置。每走一步，将步数 step 加 1（step从1开始）。
-
遍历可能的跳跃位置
遍历 ArrayList 中存放的所有跳跃位置，检查哪个位置可以合法地走通。如果找到可以继续走的合法位置，则继续往下走；如果走不通，进行回溯，尝试其他可能的路径。
-
判断是否完成任务
在每一步后，通过比较当前步数 step 和应走的总步数（例如，棋盘上总共有 64 格）来判断骑士是否完成了任务。如果步数未达到目标，表示任务尚未完成，需要将当前走的这步回溯（标记为未访问 + 从棋盘上移除step）
引入贪心算法的优化
原始算法回顾：
在原始的回溯算法中，每当骑士移动到一个新位置时，它会尝试从当前的位置出发，向所有可能的方向移动，直至找到一个合法的位置。如果某个位置无法继续走下去，算法就会回溯，尝试其他路径。这个过程有可能产生很多冗余的回溯操作，特别是当某些路径已经没有出路时，算法依然需要探索。
优化的贪心策略：
在优化后的版本中，我们对每一步的可能跳跃位置进行了排序，排序的依据是下一步的合法移动的数量。具体做法是，对于每一个当前位置，首先计算出它的所有可能的跳跃位置，接着计算每一个跳跃位置的下一步可能走的格子的数量（即它的“后继”点的数量），然后将这些点按“后继点数量”进行非递减排序，优先选择那些后继点数量少的点进行探索。
为什么这个优化是有效的？
-
减少回溯的次数：
通过优先选择“后继点数目少”的点，我们可以有效减少不必要的回溯。原因如下：
- 如果我们首先选择一个“后继点数目少”的点，那么骑士的下一步选择就会变得相对明确，不会出现太多的回溯，因为如果某个位置后继点数多，则它很可能导致更多的可能路径，造成更多的回溯操作。
- 反之，如果先选择了“后继点数目多”的点，可能导致骑士走入一个“死胡同”，这时算法会进行回溯，重新尝试其他的路径。通过贪心策略，减少了这类不必要的回溯。
-
更高效的路径探索：
通过排序后的优先选择，我们相当于是在“预测”哪些路径最有可能找到解，并优先探索这些路径。这使得每次选择跳跃点时，骑士能较早地走到棋盘的“易走”区域，避免在困难区域做无谓的探索，从而提高算法的效率。
-
防止局部最优：
贪心算法的一大优势是局部最优的选择能够帮助我们尽量避免走入死胡同。通过选择“后继点数目少”的位置，实际上是让骑士先走到那些可能性更少的地方，这样如果后续真的出现死局（即所有可能的后继都被访问过），程序可以尽早发现并进行回溯，而不是等到最后一步才回溯。
-
贪心策略的实际效果：
- 在没有优化的情况下，骑士可能在某些点周围存在很多可选的下一步位置（例如：有多个合法的跳跃位置），但这些位置的后继可能很复杂，导致更多的回溯。而引入贪心算法后，程序会先探索那些“跳跃空间”最小的路径，尽量避免复杂的回溯。
- 非递减排序的策略本质上是在优先选择“后继点最少”的点，这是一种启发式的选择方法。通过这种方法，算法通常能够更快地找到解决方案，或者发现路径的死胡同，减少了回溯的开销。
优化前：
优化后：
代码实现
HorseStepChess
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| package com.yukinoshita.algorithm.horseStepOnAChessBoard;
import java.awt.*;
import java.util.ArrayList;
public class HorseStepChess {
private static int R;
private static int C;
private static int[][] chessBoard;
private static boolean isFinished;
private static final int[] X_MOVE = {-2, -1, 1, 2, 2, 1, -1, -2};
private static final int[] Y_MOVE = {1, 2, 2, 1, -1, -2, -2, -1};
public static void main(String[] args) {
R = C = 8;
chessBoard = new int[R][C];
KnightTour(0, 0, 1);
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[i].length; j++) {
System.out.print(chessBoard[i][j] + " ");
}
System.out.println();
}
}
public static void KnightTour(int r, int c, int step) {
chessBoard[r][c] = step;
ArrayList<Point> nextPoints = getNext(new Point(c, r));
while (!nextPoints.isEmpty()) {
Point p = nextPoints.remove(0);
if (chessBoard[p.y][p.x] == 0) {
KnightTour(p.y, p.x, step + 1);
}
}
if (step < R * C && !isFinished) {
chessBoard[r][c] = 0;
} else {
isFinished = true;
}
}
public static ArrayList<Point> getNext(Point current) {
ArrayList<Point> points = new ArrayList<>();
for (int i = 0; i < 8; i++) {
int newX = current.x + X_MOVE[i];
int newY = current.y + Y_MOVE[i];
if (newX >= 0 && newX < C && newY >= 0 && newY < R) {
points.add(new Point(newX, newY));
}
}
return points;
}
}
|
优化后代码
- 在
KnightTour方法里，获取了当前点的下一步可走的所有点后，进行排序：
1
2
3
4
|
ArrayList<Point> nextPoints = getNext(new Point(c, r));
sortPoints(nextPoints);
|
sortPoints方法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static void sortPoints(ArrayList<Point> ps) {
ps.sort(new Comparator<Point>(){
@Override
public int compare(Point o1, Point o2) {
int size1 = getNext(o1).size();
int size2 = getNext(o2).size();
return size1 - size2;
}
});
}
|
- 在
main方法中，可以以下方式对比优化前后的效率（测优化前就在KnightTour方法注释掉sortPoints）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static void main(String[] args) {
R = C = 8;
chessBoard = new int[R][C];
long startTime = System.currentTimeMillis();
KnightTour(0, 0, 1);
long endTime = System.currentTimeMillis();
System.out.println("算法运行时间: " + (endTime - startTime) + " 毫秒");
for (int i = 0; i < chessBoard.length; i++) {
for (int j = 0; j < chessBoard[i].length; j++) {
System.out.print(chessBoard[i][j] + " ");
}
System.out.println();
}
}
|
