騎士周游問(wèn)題又叫馬踏棋盤(pán)問(wèn)題

1.未優(yōu)化前（沒(méi)有策略）

public class Main {    //定義棋盤(pán)的行數(shù)和列數(shù)    static int X = 8;    static int Y = 8;    //定義棋盤(pán)上的某個(gè)點(diǎn)是否被訪(fǎng)問(wèn)過(guò)    static boolean[] isVisited;    //記錄是否周游結(jié)束    static boolean isFinished = false;    public static void main(String[] args) {        isVisited = new boolean[X * Y];        int[][] chessBoard = new int[X][Y];        //從第一行第一列開(kāi)始走，第一次走算第一步，即step=1        travelChessboard(chessBoard,0,0,1);        //展示下chessBoard        for (int[] row: chessBoard){            for (int step: row){                System.out.print(step + "     ");            }            System.out.println();        }    }    /**     *     * @param chessBoard 是棋盤(pán)，因?yàn)檫f歸，所以在不斷變化     * @param row 是馬所在的行，也就是y值     * @param column 是馬所在的列，也就是x值     * @param step 馬走到的第幾步     */    public static void travelChessboard(int[][] chessBoard,int row,int column,int step){        //假定這一點(diǎn)是可以走的，所以設(shè)置已訪(fǎng)問(wèn)，步數(shù)也得加上        chessBoard[row][column] = step;//假定可以走，所以先走過(guò)去看看，設(shè)置走過(guò)去的步數(shù)        isVisited[row * X + column] = true;//假定可以走，所以先走過(guò)去看看，設(shè)置成已訪(fǎng)問(wèn)        //得到下一步可以走的點(diǎn)的集合        ArrayList<Point> nextPoints = getNext(new Point(column, row));        while (!nextPoints.isEmpty()){            //首先取出一個(gè)來(lái)            Point nextPoint = nextPoints.remove(0);            //如果這個(gè)點(diǎn)沒(méi)有被訪(fǎng)問(wèn)過(guò)            if (!isVisited[nextPoint.y * X + nextPoint.x]){                travelChessboard(chessBoard,nextPoint.y,nextPoint.x,step + 1);//這里我一開(kāi)始寫(xiě)了step++  其實(shí)應(yīng)該是step+1            }        }        //如果假定失敗，其實(shí)這個(gè)點(diǎn)是不可以走的，那么我們就進(jìn)行回溯?。。?/span>        if (step < X * Y && !isFinished){            chessBoard[row][column] = 0;            isVisited[row * X + column] = false;        }else {            isFinished = true;        }    }    /**     * 傳入當(dāng)前點(diǎn)，得到能走的下一個(gè)點(diǎn)的集合     * @param curPoint     * @return     */    public static ArrayList<Point> getNext(Point curPoint){        //創(chuàng)建結(jié)果集        ArrayList<Point> nextPoints = new ArrayList<>();        Point nextPoint = new Point();        //可以走0        if ((nextPoint.x = curPoint.x + 2) < X && (nextPoint.y = curPoint.y - 1) >= 0){            nextPoints.add(new Point(nextPoint));        }        //表示馬可以走1        if ((nextPoint.x = curPoint.x + 2) < X && (nextPoint.y = curPoint.y + 1) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走2        if ((nextPoint.x = curPoint.x + 1) < X && (nextPoint.y = curPoint.y + 2) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走3        if ((nextPoint.x = curPoint.x - 1) >= 0 && (nextPoint.y = curPoint.y + 2) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走4        if ((nextPoint.x = curPoint.x - 2) >= 0 && (nextPoint.y = curPoint.y + 1) < Y){            nextPoints.add(new Point(nextPoint));        }        //可以走5        if ((nextPoint.x = curPoint.x - 2) >= 0 && (nextPoint.y = curPoint.y - 1) >= 0){            nextPoints.add(new Point(nextPoint));        }        //可以走6        if ((nextPoint.x = curPoint.x - 1) >= 0 && (nextPoint.y = curPoint.y - 2) >= 0){            nextPoints.add(new Point(nextPoint));        }        //可以走7        if ((nextPoint.x = curPoint.x + 1) < X && (nextPoint.y = curPoint.y - 2) >= 0){            nextPoints.add(new Point(nextPoint));        }        return nextPoints;    }}

結(jié)果略去，等結(jié)果時(shí)間太長(zhǎng)了

2.貪心算法優(yōu)化后

主要是添加了這個(gè)方法
添加了這個(gè)方法后，可以減少回溯的次數(shù)，極大的提高效率

public static void getNextNext(ArrayList<Point> arrayList){      //重寫(xiě)集合的sort方法，將其按下一步可選點(diǎn)數(shù)目由小到大的順序排列，再準(zhǔn)確一點(diǎn)就是非遞減排序（因?yàn)橛邢嗤c(diǎn)）      arrayList.sort(new Comparator<Point>() {          @Override          public int compare(Point o1, Point o2) {              //得到o1的下一步可選點(diǎn)的數(shù)目              int count1 = getNext(o1).size();              //得到o2的下一步可選點(diǎn)的數(shù)目              int count2 = getNext(o2).size();              if (count1 > count2){                  return -1;              }else if (count1 == count2){                  return 0;              }else {                  return 1;              }          }      });  }

結(jié)果

1     16     43     32     3     18     45     22     42     31     2     17     44     21     4     19     15     56     53     60     33     64     23     46     30     41     58     63     54     61     20     5     57     14     55     52     59     34     47     24     40     29     38     35     62     51     6     9     13     36     27     50     11     8     25     48     28     39     12     37     26     49     10     7