极客观点
项目管理
HarmonyOS
我学习了《数据结构》课程中的回溯法后，然后就开始写代码来解决骑士游历问题！首先，我用的就是最简单的暴力回溯法，然后第二种方法就是使用预见性策略来优化提高效率。然后代码如下：
import java.util.*;
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
class TwoIntMap {
private int next;
private int nextAvailable;
public TwoIntMap(int next, int nextAvailable) {
this.next = next;
this.nextAvailable = nextAvailable;
}
public int getNext() {
return next;
}
public void setNext(int next) {
this.next = next;
}
public int getNextAvailable() {
return nextAvailable;
}
public void setNextAvailable(int nextAvailable) {
this.nextAvailable = nextAvailable;
}
}
public static void main(String[] args) {
Solution s = new Solution();
for (int i = 5; i < 9; i++) {
System.out.println(i + "================================================================================");
long startTime = System.currentTimeMillis();
List<String> res = s.traverse(i, 0, 0);
for (String line : res) {
System.out.println(line);
}
long endTime = System.currentTimeMillis();
System.out.println("traverse 运行耗时：" + (endTime - startTime) + " ms");
long startTime2 = System.currentTimeMillis();
List<String> res2 = s.traverse2(i, 0, 0);
for (String line : res2) {
System.out.println(line);
}
long endTime2 = System.currentTimeMillis();
System.out.println("traverse2 运行耗时：" + (endTime2 - startTime2) + " ms");
}
}
public List<String> traverse(int N, int sr, int sc) {
int[][] board = new int[N][N];
board[sr][sc] = 1;
List<String> res = new ArrayList<>();
dfs(board, sr, sc, res);
return res;
}
public List<String> traverse2(int N, int sr, int sc) {
int[][] board = new int[N][N];
board[sr][sc] = 1;
List<String> res = new ArrayList<>();
dfs2(board, sr, sc, res);
return res;
}
private boolean dfs(int[][] board, int sr, int sc, List<String> res) {
if (check(board)) {
for (int i = 0; i < board.length; i++) {
res.add(Arrays.toString(board[i]));
}
return true;
}
int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};
for (int i = 0; i < 8; i++) {
int[][] newBoard = deepthCopy(board);
int cr = sr + dr[i];
int cc = sc + dc[i];
if (cr >= 0 && cr < board.length && cc >= 0 && cc < board.length && board[cr][cc] == 0) {
newBoard[cr][cc] = newBoard[sr][sc] + 1;
if (dfs(newBoard, cr, cc, res)) {
return true;
}
}
}
return false;
}
private boolean dfs2(int[][] board, int sr, int sc, List<String> res) {
if (check(board)) {
for (int i = 0; i < board.length; i++) {
res.add(Arrays.toString(board[i]));
}
return true;
}
int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};
List<TwoIntMap> twoIntMaps = new ArrayList<>();
for (int i = 0; i < 8; i++) {
int[][] newBoard = deepthCopy(board);
int cr = sr + dr[i];
int cc = sc + dc[i];
if (cr >= 0 && cr < board.length && cc >= 0 && cc < board.length && board[cr][cc] == 0) {
newBoard[cr][cc] = newBoard[sr][sc] + 1;
twoIntMaps.add(new TwoIntMap(i, nextStepAvailableDirection(newBoard, cr, cc)));
}
}
twoIntMaps.sort(Comparator.comparingInt(TwoIntMap::getNextAvailable));
for (TwoIntMap twoIntMap : twoIntMaps) {
int[][] newBoard = deepthCopy(board);
int cr = sr + dr[twoIntMap.getNext()];
int cc = sc + dc[twoIntMap.getNext()];
newBoard[cr][cc] = newBoard[sr][sc] + 1;
if (dfs2(newBoard, cr, cc, res)) {
return true;
}
}
return false;
}
private int[][] deepthCopy(int[][] board) {
int[][] res = new int[board.length][board.length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
res[i][j] = board[i][j];
}
}
return res;
}
private boolean check(int[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[i][j] == 0) {
return false;
}
}
}
return true;
}
private int nextStepAvailableDirection(int[][] board, int sr, int sc) {
int res = 0;
int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};
for (int i = 0; i < 8; i++) {
int cr = sr + dr[i];
int cc = sc + dc[i];
if (cr >= 0 && cr < board.length && cc >= 0 && cc < board.length && board[cr][cc] == 0) {
res++;
}
}
return res;
}
}然后我在 for 循环里面通过设置不同的棋盘大小来测试两种实现的耗费时间，运行结果如下：
5================================================================================
[1, 6, 15, 10, 21]
[14, 9, 20, 5, 16]
[19, 2, 7, 22, 11]
[8, 13, 24, 17, 4]
[25, 18, 3, 12, 23]
traverse 运行耗时：221 ms
[1, 22, 11, 16, 7]
[12, 17, 8, 21, 10]
[25, 2, 23, 6, 15]
[18, 13, 4, 9, 20]
[3, 24, 19, 14, 5]
traverse2 运行耗时：55 ms
6================================================================================
[1, 12, 21, 28, 7, 10]
[22, 29, 8, 11, 20, 27]
[13, 2, 23, 4, 9, 6]
[30, 35, 32, 17, 26, 19]
[33, 14, 3, 24, 5, 16]
[36, 31, 34, 15, 18, 25]
traverse 运行耗时：6634 ms
[1, 10, 31, 20, 7, 12]
[32, 19, 8, 11, 30, 21]
[9, 2, 25, 36, 13, 6]
[18, 33, 16, 27, 22, 29]
[3, 26, 35, 24, 5, 14]
[34, 17, 4, 15, 28, 23]
traverse2 运行耗时：1 ms
7================================================================================
[1, 28, 37, 40, 25, 30, 9]
[38, 41, 26, 29, 10, 35, 24]
[27, 2, 39, 36, 23, 8, 31]
[42, 19, 44, 17, 32, 11, 34]
[45, 48, 3, 22, 5, 14, 7]
[20, 43, 18, 47, 16, 33, 12]
[49, 46, 21, 4, 13, 6, 15]
traverse 运行耗时：470 ms
[1, 30, 11, 46, 27, 32, 9]
[12, 45, 28, 31, 10, 37, 26]
[29, 2, 49, 38, 47, 8, 33]
[42, 13, 44, 19, 34, 25, 36]
[3, 16, 41, 48, 39, 22, 7]
[14, 43, 18, 5, 20, 35, 24]
[17, 4, 15, 40, 23, 6, 21]
traverse2 运行耗时：1 ms
8================================================================================现在的问题是，当 i = 8 时，第一种暴力回溯实现方法运行了几天了都没运算出结果来。所以我想问下是因为我的实现有问题吗（但是从输出上看 i= 5, 6, 7 时是正常输出的）？还是说当 i = 8 时，暴力回溯方法所要遍历的路径太多，真的是需要好久好久才能完成呢？
java
看了一下，原因有两点：
O(8^(N*N))，也就是说，8*8的棋盘复杂度为O(8^64)，这是一个天文数字举个例子，即使是100 * 100的棋盘，如果恰好每一步都选择的是正确的跳法，那么也只需要10000步即可算出答案（假设答案是存在的）。但假如运气不好，前面的选择都错了，导致程序需要不断重试，那么即使是5*5的棋盘，也需要大约8^25步才能找到答案！
而穷举法并不会去判断并选择最有可能的跳法去尝试，它只是无脑地按照顺序一次次尝试，所以找到答案所消耗的时间完全是凭运气。当N=5、6、7的时候运气较好，而N=8的时候运气却比较差。
原理部分就分析到这里，下面来谈谈优化。
虽然穷举法解出N=8比较困难，但是并不是说你的程序没有问题。我发现了几点问题可以改进
dfs方法（可以从5、6、7的计算时间看出改进效果，但N=8的时候仍然无能为力）调用的时候改为：