騎士游歷問題

我學(xué)習(xí)了《數(shù)據(jù)結(jié)構(gòu)》課程中的回溯法后，然后就開始寫代碼來解決騎士游歷問題！首先，我用的就是最簡單的暴力回溯法，然后第二種方法就是使用預(yù)見性策略來優(yōu)化提高效率。然后代碼如下：

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 循環(huán)里面通過設(shè)置不同的棋盤大小來測試兩種實現(xiàn)的耗費時間，運行結(jié)果如下：

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================================================================================

現(xiàn)在的問題是，當 i = 8 時，第一種暴力回溯實現(xiàn)方法運行了幾天了都沒運算出結(jié)果來。所以我想問下是因為我的實現(xiàn)有問題嗎（但是從輸出上看 i= 5, 6, 7 時是正常輸出的）？還是說當 i = 8 時，暴力回溯方法所要遍歷的路徑太多，真的是需要好久好久才能完成呢？

回答

編輯回答

祈歡

看了一下，原因有兩點：

窮舉法的復(fù)雜度較高，約為O(8^(N*N))，也就是說，8*8的棋盤復(fù)雜度為O(8^64)，這是一個天文數(shù)字
復(fù)雜度只是一方面，并不能代表最終的計算時間。之所以5、6、7的時候使用的時間較少，是因為它們在較少的嘗試次數(shù)下就可以找到答案了。所以耗費的時間并不多。而8*8的時候卻比較不幸，嘗試了很多次都不能成功，導(dǎo)致運行很久都找不到答案。

舉個例子，即使是100 * 100的棋盤，如果恰好每一步都選擇的是正確的跳法，那么也只需要10000步即可算出答案（假設(shè)答案是存在的）。但假如運氣不好，前面的選擇都錯了，導(dǎo)致程序需要不斷重試，那么即使是5*5的棋盤，也需要大約8^25步才能找到答案！

而窮舉法并不會去判斷并選擇最有可能的跳法去嘗試，它只是無腦地按照順序一次次嘗試，所以找到答案所消耗的時間完全是憑運氣。當N=5、6、7的時候運氣較好，而N=8的時候運氣卻比較差。

原理部分就分析到這里，下面來談?wù)剝?yōu)化。

雖然窮舉法解出N=8比較困難，但是并不是說你的程序沒有問題。我發(fā)現(xiàn)了幾點問題可以改進dfs方法（可以從5、6、7的計算時間看出改進效果，但N=8的時候仍然無能為力）

    // dr和dc放到方法外面定義，這樣每次遞歸的時候不用單獨創(chuàng)建一遍數(shù)組
    final int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
    final int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};

    // 修改dfs方法的參數(shù)，增加count和total，目的是消除check方法。
    // count表示當前進行到第幾步了，total是總步數(shù)，如果count=total，就表示棋盤已經(jīng)遍歷完了
    private boolean dfs(int[][] board, int sr, int sc, List<String> res, int count, int total) {
        if (/*check(board)*/count == total) {
            for (int i = 0; i < board.length; i++) {
                res.add(Arrays.toString(board[i]));
            }
            return true;
        }

        for (int i = 0; i < 8; i++) {
        // 去掉棋盤的copy，只使用原棋盤數(shù)組即可
//            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;
                // 每次遞歸前給下一步要嘗試的格子賦值，但如果沒找到答案，再把那個格子清空。這樣就可以實現(xiàn)無需借助棋盤拷貝也可以完成遞歸
                board[cr][cc] = count + 1;
                if (dfs(board, cr, cc, res, count + 1, total)) {
                    return true;
                } else {
                    board[cr][cc] = 0;
                }
            }
        }

        return false;
    }

調(diào)用的時候改為：