實驗內容

• 對九宮重排問題，建立圖的啟發式搜索求解方法；
• 用A*演算法求解九宮重排問題，

實驗要求

3х3九宮棋盤，放置數碼為1~8的8個棋子，棋盤中留有一個空格，空格周圍的棋子可以移動到空格中，從而改變棋盤的布局，根據給定初始布局和目標布局，移動棋子從初始布局到達目標布局，求解移動步驟并輸出，請設計演算法，使用合適的搜索策略，在較少的空間和時間代價下找到最短路徑，

編程語言的選擇

• 編程語言：Java
• 編譯環境：JDK1.8
• 開發工具：IntelliJ IDEA

專案思路

專案決議

（1）1-8八個數字隨機分布在一個九宮格內
（2）九宮格記憶體在一個無數字格（稱為空格），為方便計算，可用#代替
（3）空格周圍的幾個數字都可與空格互換位置
（4）經過多次互換，使得空格位于九宮格重要，數字1-8從左上角宮格開始，順時針依次排布
（5）從初始狀態經過多次互換達到最終狀態有無數種可能，求最優演算法

演算法選擇

A*演算法

A* 演算法，A*(A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效演算法，演算法中的距離估算值與實際值越接近，最終搜索速度越快，
注意——是最有效的直接搜索演算法，之后涌現了很多預處理演算法(如ALT，CH，HL等等)，在線查詢效率是A*演算法的數千甚至上萬倍，
公式表示為：f(n)=g(n)+h(n),
其中， f(n) 是從初始狀態經由狀態n到目標狀態的代價估計，
g(n)是在狀態空間中從初始狀態到狀態n的實際代價，
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價，
(對于路徑搜索問題，狀態就是圖中的節點，代價就是距離)
h(n)的選取保證找到最短路徑(最優解的)條件，關鍵在于估價函式f(n)的選取(或者說h(n)的選取)，
我們以d(n)表達狀態n到目標狀態的距離，那么h(n)的選取大致有如下三種情況:
（1）如果h(n)<d(n)到目標狀態的實際距離，這種情況下，搜索的點數多，搜索范圍大，效率低，但能得到最優解，
（2）如果h(n)=d(n)，即距離估計h(n)等于最短距離，那么搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的，
（3）如果h(n)>d(n)，搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解，

代碼實作如下：

public static int A_star(int[][] MT) {
        // 找到空格所在的位置
        int x0 = 0, y0 = 0;
        for (x0 = 0; x0 < N; x0++) {
            boolean flag = false;
            for (y0 = 0; y0 < N; y0++) {
                if (MT[x0][y0] == 0) {
                    flag = true;
                    break;
                }
            }
            if (flag)
                break;
        }
        // 優先佇列
        Queue<node> q = new PriorityQueue<node>(cmp);
        int[][] curmt = new int[N][];
        int[][] markemt = new int[N][];
        // clone方法用于復制一個物件，在記憶體中開辟同樣大小的空間
        for (int r = 0; r < N; r++)
            curmt[r] = MT[r].clone();
        for (int r = 0; r < N; r++)
            markemt[r] = MT[r].clone();
        List<int[][]> path = new ArrayList<int[][]>();
        // path加入初始狀態
        path.add(MT);
        // 創建一個結點，表示空格，估價函式初始化為0
        node cur = new node(x0, y0, 0, 0, 0, curmt, path);
        // 將出現過的所有狀態都加入marke集合中
        marke.add(markemt);
        // 入隊并遍歷
        q.add(cur);
        while (!q.isEmpty()) {
            // 隊首元素出隊
            cur = (node) q.poll().clone();
            boolean tag = false;
            // 判斷當前狀態是不是目標狀態
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (cur.mt[i][j] != endMT[i][j]) {
                        tag = true;
                    }
                }
            }
            // 如果是，輸出結果
            if (!tag) {
                System.out.println("共擴展了" + marke.size() + "個結點");
                return cur.step;
            }
            // 遍歷四種方向上的移動
            for (int i = 0; i < 4; i++) {
                node next = (node) cur.clone();
                next.x = cur.x + dir[i][0];
                next.y = cur.y + dir[i][1];
                // 如果空格位置不合法就忽略這個狀態
                if (next.x >= 0 && next.x < N && next.y >= 0 && next.y < N) {
                    // 因為上面next定義時clone了cur，所以在這里更新空格的位置
                    next.mt[cur.x][cur.y] = next.mt[next.x][next.y];
                    next.mt[next.x][next.y] = 0;
                    boolean mark = false;
                    // 判斷當前狀態有沒有出現過
                    for (int c = 0; c < marke.size(); c++) {
                        int x = 0, y = 0;
                        for (x = 0; x < N; x++) {
                            for (y = 0; y < N; y++)
                                if (marke.get(c)[x][y] != next.mt[x][y])
                                    break;
                            if (y < N)
                                break;
                        }
                        if (x == N && y == N)
                            mark = true;
                    }
                    // 若出現過則忽略這個狀態
                    if (!mark) {
                        // 更新next的屬性值step和估價函式g
                        next.step++;
                        next.g++;
                        // 將當前狀態加入到結點的path中，因為程式中定義結點時，clone了上一個結點，所以在當前結點添加的狀態也會clone到下一個結點中，
                        next.path.add(next.mt);
                        // 計算估價函式h，獲取每個位置的數字，到達目標狀態中對應數字的位置，所需要的步數
                        int count = 0;
                        for (int row = 0; row < N; row++) {
                            for (int cow = 0; cow < N; cow++) {
                                if (cow != 0 && next.mt[row][cow] != endMT[row][cow]) {
                                    count += Math.abs(row - map.get(next.mt[row][cow])[0])
                                            + Math.abs(cow - map.get(next.mt[row][cow])[1]);
                                }
                            }
                        }
                        next.h = count;
                        // 將擴展狀態入隊
                        int[][] newmt = new int[N][];
                        for (int r = 0; r < N; r++)
                            newmt[r] = next.mt[r].clone();
                        marke.add(newmt);
                        q.add((node) next.clone());
                    }
                }
            }
        }
        return 0;
    }