• 【人工智能】Astar算法求解8數碼問題（QDU）
  
• 【人工智能】利用α-β搜索的博弈樹算法編寫一字棋游戲（QDU）
  
• 【人工智能】Fisher 線性分類器的設計與實現（QDU）
• 【人工智能】感知器算法的設計實現（QDU）
• 【人工智能】SVM 分類器的設計與應用（QDU）
• 卷積神經網絡 CNN 框架的實現與應用（寫的比較水，就沒放上）

實驗目的

熟悉和掌握啟發式搜索的定義、估價函數和算法過程，并利用 A* 算法求解 N 數碼難題，理解求解流程和搜索順序。

實驗原理

盲?的搜索?法沒有利?問題本身的特性信息，在決定要被擴展的節點時，都沒有考慮該節點在解的路徑上的可能性有多?，是否有利于問題求解以及求出的解是否最優；

啟發式搜索要?到問題?身的某些特性信息，在選擇節點時充分利?與問題有關的特征信息，估計出節點的重要性，在搜索時選擇重要性較?的節點以利于求得最優解。

啟發性信息和估價函數

?于指導搜索過程，且與具體問題有關的控制性信息稱為啟發性信息；?于評價節點重要性的函數稱為估價函數。

估價函數記作：
$$f(x)=g(x)+h(x)$$

• $g(x)$為從初始節點$S_0$到節點$x$已經實際付出的代價

• $h(x)$是從節點$x$到?標節點$S_g$的最優路徑的估計代價，體現了問題的啟發性信息，稱為啟發函數

• $f(x)$表示從初始節點經過節點$x$到達?標節點的最優路徑的代價估價值，其作?是?來評估OPEN表中各節點的重要性，決定其次序

實驗內容

八數碼問題

問題描述：

3×3九宮棋盤，放置數碼為1 -8的8個棋牌，剩下一個空格，只能通過棋牌向空格的移動來改變棋盤的布局。根據給定初始布局（即初始狀態）和目標布局（即目標狀態），如何移動棋牌才能從初始布局到達目標布局，找到合法的走步序列。

問題分析：

對于八數碼問題的解決，首先要考慮是否有答案。每一個狀態可認為是一個1×9的矩陣，由數學知識可知，計算這兩個有序數列的逆序值，如果兩者都是偶數或奇數，則可通過變換到達，否則這兩個狀態不可達。這樣，就可以在具體解決問題之前判斷出問題是否可解，從而可以避免不必要的搜索。

廣度優先搜索

搜索過程：

寬度優先搜索算法的主要涉及到兩個對象數組的使用，分別是OPEN表和CLOSED表，用來記錄已擴展但未搜索的節點和已搜索的節點。由于寬度搜索是盲目的，所以并不需要計算估計函數的值，只需要根據OPEN表節點的順序依次進行遍歷即可。

擴展節點的方法：首先找到數值“0”所在的坐標，根據坐標選擇可擴展的方向，例如坐標為（2,0）只可向右擴展和向上擴展。同時，為了避免死循環，擴展的方向不可與父節點的方向相反。

擴展節點后，將其放入OPEN表的尾部，然后再進行新一輪的遍歷，直到找到與目標節點相同的節點或者OPEN為空為止。

流程圖如下：

全局擇優搜索

全局擇優搜索（Global Optimization Search）屬于啟發式搜索，即利用已知問題中的啟發式信息指導問題求解，而非蠻力窮舉的盲目搜索。

此處，啟發函數定義為：$f(n)=g(n)+h(n)$，其中$g(n)$表示當前結點的深度，h(n)表示定義為當前節點與目標節點差異的度量。

搜索過程：

與寬度優先搜索相比，啟發性的全局擇優搜索則需要通過計算估計函數的值來決定搜索的方向，而不是盲目的進行遍歷。

同樣地，全局擇優算法也會涉及OPEN表和CLOSED表的使用。但與寬度優先搜索不同的是，每一次擴展子節點都要計算該節點的估計函數值，并且，在將某節點的所有擴展子節點加入OPEN表的尾部后，需要根據估計函數值對OPEN表進行從小到大排序，之后再從OPEN表取出第一個節點放入CLOSED表中，進行新一輪的遍歷，直到找到與目標節點相同的節點或者OPEN為空為止。

流程圖如下：

A* 算法

A* 算法與全局擇優算法均是啟發性的搜索算法，但全局擇優算法僅適合于狀態空間是樹狀結構的情況，如果狀態空間是一個有向圖的話，在OPEN表中可能會出現重復的節點，節點的重復將導致大量的冗余搜索，使效率大大降低。

A*算法的優勢在于 : 如果某一問題有解，那么利用 A* 搜索算法對該問題進行搜索一定能以搜索到最優的解結束。

搜索過程：

A* 算法在全局擇優算法的基礎上對其進行了改進：在擴展節點的時候加入了對子節點存在性的判斷。如果擴展的某個新子節點已經在OPEN表或CLOSED表中出現過并且新子節點的估價值更小，則將原節點刪除，并將新節點添加到OPEN表中，否則保留原節點，不進行改動。

流程圖如下：

啟發函數

本實驗共涉及到兩種啟發函數$h(n)$，具體定義如下：

• $h(n)$定義為當前節點與目標節點差異的度量：即當前節點與目標節點格局相比，位置不符的數字個數。

實驗原理：從數值0遍歷到數值8，將每個數字不在位的個數作為啟發信息。

• $h(n)$定義為當前節點與目標節點距離的度量：當前節點與目標節點格局相比，位置不符的數字移動到目標節點中對應位置的最短距離之和。

實現原理：從數值0遍歷到數值8，將每個數字從當前位置移動到目標位置的歐拉距離作為啟發信息。

實驗表格

表 1 不同啟發函數 $h(n)$ 求解 8 數碼問題的結果比較

	啟發函數 h(n)
	不在位數	歐拉距離	0
初始狀態	130824765	130824765	130824765
目標狀態	123804765	123804765	123804765
最優解	--第 0 步-- 1|3|?? --------- 8|2|4 --------- 7|6|5 --第 1 步-- 1|??|3 --------- 8|2|4 --------- 7|6|5 --第 2 步-- 1|2|3 --------- 8|??|4 --------- 7|6|5	--第 0 步-- 1|3|?? --------- 8|2|4 --------- 7|6|5 --第 1 步-- 1|??|3 --------- 8|2|4 --------- 7|6|5 --第 2 步-- 1|2|3 --------- 8|??|4 --------- 7|6|5	--第 0 步-- 1|3|?? --------- 8|2|4 --------- 7|6|5 --第 1 步-- 1|??|3 --------- 8|2|4 --------- 7|6|5 --第 2 步-- 1|2|3 --------- 8|??|4 --------- 7|6|5
擴展節點數	2	2	4
生成節點數	3	3	7
運行時間	0.0308ms	0.1244ms	0.126ms

表 2 不同啟發函數 $h(n)$ 求解 15 數碼問題的結果比較

	啟發函數 h(n)
	不在位數	歐拉距離	0
初始狀態	1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,0	1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,0	1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,0
目標狀態	1,2,3,4,5,6,7,8,9,10, 11,12,0,13,14,15	1,2,3,4,5,6,7,8,9,10, 11,12,0,13,14,15	1,2,3,4,5,6,7,8,9,10, 11,12,0,13,14,15
最優解	--第 0 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|14|15|???? --第 1 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|14|????|15 --第 2 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|????|14|15 --第 3 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- ????|13|14|15	--第 0 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|14|15|???? --第 1 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|14|????|15 --第 2 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|????|14|15 --第 3 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- ????|13|14|15	--第 0 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|14|15|???? --第 1 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|14|????|15 --第 2 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- 13|????|14|15 --第 3 步-- ??1|??2|??3|??4 ------------------- ??5|??6|??7|??8 ------------------- ??9|10|11|12 ------------------- ????|13|14|15
擴展節點數	3	3	7
生成節點數	4	4	13
運行時間	0.1444ms	0.3127ms	2.3763ms

實驗設計

本實驗采用Java高級程序設計語言實現八數碼問題及十五數碼問題的可視化，對不同啟發函數下的不同算法進行性能分析。

算法設計

廣度優先搜索

該算法的實現并沒有使用OPEN和CLOSED表對節點進行操作，甚至都沒有使用鏈表結構。主要依賴于Java中自帶的隊列數據結構，調用自帶函數，用隊列的”入隊“與”出隊“實現廣度優先搜索。

將起點入隊后只要隊列非空，持續執行取隊首、出隊，先判斷該節點是否為目標狀態，若為目標狀態則結束，否則由該節點進行四連通擴展，通過Map記錄每種狀態是否出現過，若未出現過則將擴展子節點入隊。每次擴展節點都要保存每個子節點對應的父節點，這是為了方便輸出路徑時直接根據Map向前遍歷即可。

全局擇優搜索

該算法使用自定義鏈表類作為OPEN表，該鏈表的首節點為空，從其next節點開始保存狀態信息；使用以String為鍵、以Boolean為值的Map作為CLOSED表，這是因為CLOSED表只需記錄某個節點是否還可以進行擴展，因此無需為其創建鏈表。該算法并未采用對OPEN表按估計函數值從小到大對節點繼續排序，而是每次去遍歷OPEN表，找到估計函數值最小的節點作為擴展節點，這樣可以有效的降低時間復雜度。

先向OPEN表中起點及其信息，只要OPEN表的首節點有后繼節點就死循環，循環中先通過自定義函數找到OPEN鏈表中估計函數值最小的節點，如果該節點的狀態與目標狀態一致，則說明到達目標狀態，退出；否則在此狀態下確定空格的位置，讓其與四個方向的數字交換，得到四種不同的狀態，對于CLOSED表中存在的狀態不予以考慮；若剩余的狀態在不OPEN表則將其加入到OPEN表中。

A* 算法

與”全局擇優搜索“基本一致，唯一不同的是：對于不在CLOSED表中的擴展子節點，若擴展到的狀態在OPEN表中存在則還需要判斷是已保存在OPEN表中的該狀態對應的估計函數值與由當前節點擴展到該狀態的估計函數值的大小關系，若由當前節點擴展到該狀態的估計函數值更小，則需要將原節點刪除并將該狀態對應的新節點加入OPEN表中；若擴展到的狀態在OPEN表中不存在，則該狀態對應的節點無條件加入到OPEN表。

程序設計

初始界面

功能介紹

左側九宮格（或十六宮格）對應初始狀態，右側九宮格（或十六宮格）對應目標狀態，兩種狀態均可由用戶向文本框中輸入，若輸入不合法則彈出警告框，又若輸入的初始狀態無法到達目標狀態，則會根據算法判斷逆序數的奇偶性，若無解會彈出警告框。

用戶需先對靠上的下拉列表進行操作選擇”八數碼“還是”十五數碼“，點擊其下方的”確定“后宮格將切換成對應的樣式；在方格內輸入初始狀態和目標狀態后通過靠下的下拉列表選擇采用”估價函數1“還是”估價函數2“，點擊其下方的”確定“后開始執行算法。

左下方的選擇卡總共三個TAB，分別對應三種算法，每個TAB中的文本域顯示對應算法的執行過程，即從初始狀態變換到目標狀態的操作方式。右下方的文本域顯示三種算法在選取不同的估價函數后得到結果的最佳步數和時間，可以根據顯示對算法性能進行對比分析。

程序要求

• 一個方格中最多存在兩個字符
• 表示空格子的方格必須存在且要在空格中輸入一個空格字符
• 初始狀態和目標狀態包括的數字（或字符串）必須完全一致

若不滿足這些要求接下來的操作會彈出錯誤提示框無法繼續執行，甚至程序崩潰。

若輸入的初始狀態無法到達目標狀態，則彈出警告框。

程序局限性

• 當一個方格內的輸入存在兩位字符時，在左下方的文本域中會出現宮格格式不標準的情況
• 未對“程序要求”中的錯誤情況進行健壯性處理，即存在程序報錯的情況，未用try-catch捕獲并處理
• 未在宮格中可視化空格的移動過程
• 代碼冗余度高

運行截圖

采用啟發函數1解決八數碼問題，左側九宮格為初始狀態，右側九宮格為目標狀態。下圖為默認狀態，用戶可以根據需要向九宮格中輸入初始狀態和目標狀態。點擊“八數碼”下方的“確定”表示選定解決八數碼問題，點擊“估價函數1”下方的“確定”表示選定使用“估價函數1”作為啟發函數解決此問題。

下方左側選擇卡中的文本域顯示不同算法執行每一步得到的狀態，右側文本域顯示采用不同算法解決該問題所需的時間與計算得到的最短移動次數。

操作靠上的下拉列表切換成”十五數碼“后點擊其下方的”確定“，可以實現將”初始狀態“和”目標狀態“的輸入框轉換為$4\times 4$的格式。輸入完成后操作靠下的下拉列表切換啟發函數，點擊其下方的”確定“后執行三種算法，時間與步數將不覆蓋地顯示在右下側的文本域中，完整移動過程將覆蓋地顯示與不同算法各自的執行過程。

附錄（代碼）

Window.java 程序

其中包含了界面設計的代碼和三個核心算法。

package exp1;import javax.swing.*; import java.awt.*; import java.util.*;/*** @author LJR* @create 2021-11-04 18:52* @description* 要求：* 1. 空格子內必須是一個空格！* 2. 必須先確定是“八數碼”還是“十五數碼”！否則出錯* 不足：* 1. 當一個方格內的輸入存在兩位字符時，在文本域中會出現顯示不標準的情況* 2. 未對“要求”中的錯誤情況進行健壯性處理* 3. 未可視化空格的移動過程* 4. 代碼冗余度高*/public class Window extends JFrame {private static final long serialVersionUID = -6740703588976621222L;int size = 8;int row_max = 0, col_max = 0; // 數碼表的行數與列數int width = 0, height = 0; // 數碼表每格寬高int left_x = 0, left_y = 0, right_x = 0, right_y = 0; // 初始數碼表的左上角坐標，目標數碼表的右上角坐標int fontsize = 0;int nums_original[] = {1, 3, 0, 8, 2, 4, 7, 6, 5}; // 八數碼的測試int nums_target[] = {1, 2, 3, 8, 0, 4, 7, 6, 5};public Window() {super("A* 算法求解 8 數碼問題");Container c = this.getContentPane();c.add(getJButton());c.setBackground(Color.white);this.setSize(700, 850);this.setUndecorated(false);this.setLocationRelativeTo(null);this.setVisible(true);this.setResizable(false);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);}JButton jButton, jb; // 確定按鈕JLabel label1, label2; // 文字標題JComboBox box; // 下拉列表JComboBox EorF; // 下拉列表JTextField jf[][] = new JTextField[3][20]; // 九宮格或十六宮格JTextArea textarea1, textarea2, textarea3; // 左下方三個文本域JTextArea ja; // 右下方文本域int v1steps = 0, v2steps = 0, v3steps = 0; // 全局擇優、A*、BFS對應的步數double v1time = 0, v2time = 0, v3time = 0; // 全局擇優、A*、BFS對應的用時public JPanel getJButton() {JPanel jP = new JPanel();jP.setOpaque(false);jP.setLayout(null);// 設置空布局，即絕對布局// “確認”按鈕jb = new JButton("確認");jb.setBounds(293, 220, 100, 35);// 設置位置及大小jb.setFont(new Font("華文行楷", Font.PLAIN, 18));jb.setFocusPainted(false);jButton = new JButton("確認");jButton.setBounds(293, 315, 100, 35);// 設置位置及大小jButton.setFont(new Font("華文行楷", Font.PLAIN, 18));jButton.setFocusPainted(false);jP.add(jb);jP.add(jButton);// "初始狀態"JLabel start = new JLabel("初始狀態");start.setBounds(110, 130, 500, 35);start.setFont(new Font("華文行楷", Font.PLAIN, 20));jP.add(start);// "目標狀態"JLabel target = new JLabel("目標狀態");target.setBounds(490, 130, 500, 35);target.setFont(new Font("華文行楷", Font.PLAIN, 20));jP.add(target);// 第一行文字label1 = new JLabel("請分別填入初始狀態（左）和目標狀態（右）");label1.setBounds(110, 30, 500, 35);label1.setFont(new Font("華文行楷", Font.PLAIN, 25));jP.add(label1);// 第二行文字label2 = new JLabel("點擊“確定”按鈕查看移動過程和分析結果");label2.setBounds(140, 80, 500, 35);label2.setFont(new Font("華文行楷", Font.PLAIN, 22));jP.add(label2);// 下拉列表EorF = new JComboBox();EorF.setBounds(277, 170, 130, 40);EorF.setFont(new Font("華文行楷", Font.PLAIN, 18));EorF.addItem(" 八數碼");EorF.addItem(" 十五數碼");box = new JComboBox();box.setBounds(277, 265, 130, 40);box.setFont(new Font("華文行楷", Font.PLAIN, 18));box.addItem(" 估價函數 1");box.addItem(" 估價函數 2");jP.add(EorF);jP.add(box);// 顯示數碼時的格式 // int nums_original[] = {1, 3, 0, 8, 2, 4, 7, 6, 5}; // 八數碼的測試 // int nums_target[] = {1, 2, 3, 8, 0, 4, 7, 6, 5}; // int nums_original[] = {1, 2, 3, 4, 5, 6, 7, 8, 0}; // 八數碼的測試 // int nums_target[] = {1, 2, 3, 4, 6, 5, 7, 0, 8}; // int nums_original[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11, 12, 13, 14, 15}; // 十五數碼的測試 // int nums_target[] = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};if (size == 8) {row_max = col_max = 3;width = height = 60;left_x = 60;left_y = 170;right_x = 445;right_y = 170;fontsize = 30;} else if (size == 15) {row_max = col_max = 4;width = height = 45;left_x = 60; // 40left_y = 170;right_x = 445; // 465right_y = 170;fontsize = 25;}// 為八數碼按鈕綁定點擊監聽jb.addActionListener((actionEvent ->{int eightOrFifteen = EorF.getSelectedIndex();if (eightOrFifteen == 0) {size = 8;row_max = col_max = 3;width = height = 60;left_x = 60;left_y = 170;right_x = 445;right_y = 170;fontsize = 30;nums_original = new int[]{1, 3, 0, 8, 2, 4, 7, 6, 5}; // 八數碼的測試nums_target = new int[]{1, 2, 3, 8, 0, 4, 7, 6, 5};// 刪除十六宮格文本域組件，并顯示九宮格組件for (int i = 0;i < 16;i ++) {try {jf[0][i].setVisible(false);jf[1][i].setVisible(false);} catch (Exception e) {}}for (int row = 0; row < row_max; row++) // 按順序依次創建方格并進行排列for (int col = 0; col < col_max; col++) {int left_ch = nums_original[row * row_max + col];int right_ch = nums_target[row * row_max + col];jf[0][row * row_max + col] = new JTextField(left_ch + ""); // 創建文本框jf[1][row * row_max + col] = new JTextField(right_ch + "");jf[0][row * row_max + col].setBounds(col * width + left_x, row * height + left_y, width, height);jf[1][row * row_max + col].setBounds(col * width + right_x, row * height + right_y, width, height);jf[0][row * row_max + col].setFont(new Font("黑體", Font.PLAIN, fontsize));jf[1][row * row_max + col].setFont(new Font("黑體", Font.PLAIN, fontsize));jf[0][row * row_max + col].setOpaque(false); // 文本框透明jf[1][row * row_max + col].setOpaque(false);jf[0][row * row_max + col].setDocument(new LimitedLength()); // 限制文本框中的內容不超過兩個字符jf[1][row * row_max + col].setDocument(new LimitedLength());jf[0][row * row_max + col].setText(left_ch == 0 ? " " : left_ch + ""); // 文本框中的默認數字jf[1][row * row_max + col].setText(right_ch == 0 ? " " : right_ch + "");jf[0][row * row_max + col].setVisible(true);jf[1][row * row_max + col].setVisible(true); // 設置可見后相當于覆蓋jP.add(jf[0][row * row_max + col]);jP.add(jf[1][row * row_max + col]);}} else {size = 15;row_max = col_max = 4;width = height = 45;left_x = 60; // 40left_y = 170;right_x = 445; // 465right_y = 170;fontsize = 25;nums_original = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}; // 十五數碼的測試nums_target = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15};// 刪除九宮格文本域組件for (int i = 0;i < 16;i ++) {try {jf[0][i].setVisible(false);jf[1][i].setVisible(false);} catch (Exception e) {}}for (int row = 0; row < row_max; row++)for (int col = 0; col < col_max; col++) {int left_ch = nums_original[row * row_max + col];int right_ch = nums_target[row * row_max + col];jf[0][row * row_max + col] = new JTextField(left_ch + "");jf[1][row * row_max + col] = new JTextField(right_ch + "");jf[0][row * row_max + col].setBounds(col * width + left_x, row * height + left_y, width, height);jf[1][row * row_max + col].setBounds(col * width + right_x, row * height + right_y, width, height);jf[0][row * row_max + col].setFont(new Font("黑體", Font.PLAIN, fontsize));jf[1][row * row_max + col].setFont(new Font("黑體", Font.PLAIN, fontsize));jf[0][row * row_max + col].setOpaque(false); // 文本框透明jf[1][row * row_max + col].setOpaque(false);jf[0][row * row_max + col].setDocument(new LimitedLength()); // 限制文本框中的內容不超過兩個字符jf[1][row * row_max + col].setDocument(new LimitedLength());jf[0][row * row_max + col].setText(left_ch == 0 ? " " : left_ch + ""); // 文本框中的默認數字jf[1][row * row_max + col].setText(right_ch == 0 ? " " : right_ch + "");jf[0][row * row_max + col].setVisible(true);jf[1][row * row_max + col].setVisible(true);jP.add(jf[0][row * row_max + col]);jP.add(jf[1][row * row_max + col]);}}}));// 為估價函數按鈕綁定點擊監聽jButton.addActionListener((actionEvent -> {boolean flag = true, empty = false;/* 將初始文本框和目標文本框中的內容存在String數組中，排序后逐一比較，要求完全相同方可執行算法 */String[] left = new String[size + 1], right = new String[size + 1]; // 用于排序，方便判斷初始和目標包含的數字是否一致String[] left_copy = new String[size + 1], right_copy = new String[size + 1]; // 原位置for (int i = 0; i <= size; i++) {left[i] = new String(jf[0][i].getText());right[i] = new String(jf[1][i].getText());left_copy[i] = new String(jf[0][i].getText());right_copy[i] = new String(jf[1][i].getText());}Arrays.sort(left); // 排序Arrays.sort(right);for (int i = 0; i <= size; i++) { // 判斷是否存在不同的字符串，是否存在重復字符串if (!left[i].equals(right[i]) || (i != size && left[i].equals(left[i + 1]))) {flag = false;break;}if (left[i].equals(" ")) empty = true; // 必須要存在空格}if (flag && empty) { // 左右文本框內容不存在異常String string = box.getSelectedItem().toString();char option = string.charAt(string.length() - 1);int eightOrFifteen = EorF.getSelectedIndex();if (calDe(left_copy) % 2 != calDe(right_copy) % 2)JOptionPane.showMessageDialog(null, "無解", "錯誤", JOptionPane.ERROR_MESSAGE);else {/* 左側GOS文本域 */textarea1.setText(""); // 清空文本域new GOS(left_copy, right_copy, Integer.parseInt(option + ""), eightOrFifteen);/* 左側A*文本域 */textarea2.setText("");new Astar(left_copy, right_copy, Integer.parseInt(option + ""), eightOrFifteen);/* 左側BFS文本域 */textarea3.setText("");new BFS(left_copy, right_copy, eightOrFifteen);/* 選擇的估價函數 */if (option == '1') ja.append("h1(n)，啟發函數定義為當前節點與目標節點差異的度量：即當前節點與目標節點格局相比，位置不符的數字個數。\n\n");else if(option == '2') ja.append("h2(n)，啟發函數定義為當前節點與目標節點距離的度量：當前節點與目標節點格局相比，位置不符的數字移動到目標節點中對應位置的最短距離之和。\n\n");/* 右側GOS時間與步數 */ja.append("全局擇優算法所需時間為：" + v1time + "ms，" + "所需步數為：" + v1steps + "\n\n");v1steps = 0;/* 右側A*時間與步數 */ja.append("A*算法所需時間為：" + v2time + "ms，" + "所需步數為：" + v2steps + "\n\n");v2steps = 0;/* 右側BFS時間與步數 */ja.append("BFS算法所需時間為：" + v3time + "ms，" + "所需步數為：" + v3steps + "\n\n");v3steps = 0;ja.append("------------------------------------------\n");/* 文本域自動滾動 */ja.setCaretPosition(ja.getText().length());}} else { // 彈出警告框JOptionPane.showMessageDialog(null, "初始數碼與目標數碼異常", "錯誤", JOptionPane.ERROR_MESSAGE);}}));// 初始數碼與目標數碼的顯示（默認，即剛打開程序得到的界面）for (int row = 0; row < row_max; row++)for (int col = 0; col < col_max; col++) {int left_ch = nums_original[row * row_max + col];int right_ch = nums_target[row * row_max + col];jf[0][row * row_max + col] = new JTextField(left_ch + "");jf[1][row * row_max + col] = new JTextField(right_ch + "");jf[0][row * row_max + col].setBounds(col * width + left_x, row * height + left_y, width, height);jf[1][row * row_max + col].setBounds(col * width + right_x, row * height + right_y, width, height);jf[0][row * row_max + col].setFont(new Font("黑體", Font.PLAIN, fontsize));jf[1][row * row_max + col].setFont(new Font("黑體", Font.PLAIN, fontsize));jf[0][row * row_max + col].setOpaque(false); // 文本框透明jf[1][row * row_max + col].setOpaque(false);jf[0][row * row_max + col].setDocument(new LimitedLength()); // 限制文本框中的內容不超過兩個字符jf[1][row * row_max + col].setDocument(new LimitedLength());jf[0][row * row_max + col].setText(left_ch == 0 ? " " : left_ch + ""); // 文本框中的默認數字jf[1][row * row_max + col].setText(right_ch == 0 ? " " : right_ch + "");jP.add(jf[0][row * row_max + col]);jP.add(jf[1][row * row_max + col]);}// 選擇卡/* 將三個文本域分別加入到三個JScrollPane（滾動條面板）中，將三個滾動條面板加入同一個JTabbedPane（選擇卡）的不同tab中 */JTabbedPane tabbedPane = new JTabbedPane();tabbedPane.setBounds(40, 410, 275, 360);/* 第一個文本域 */textarea1 = new JTextArea();textarea1.setLineWrap(true); // 文本自動換行textarea1.setFont(new Font("宋體", Font.PLAIN, 15)); // 設置文本域字體textarea1.setEditable(false); // 設置不可編輯文本域，只能通過程序執行修改JScrollPane scrollPane1 = new JScrollPane(textarea1); // 創建滾動條面板scrollPane1.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); // 總是出現滾動條/* 第二個文本域 */textarea2 = new JTextArea();textarea2.setFont(new Font("宋體", Font.PLAIN, 15));textarea2.setLineWrap(true);textarea2.setEditable(false);JScrollPane scrollPane2 = new JScrollPane(textarea2);scrollPane2.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);/* 第三個文本域 */textarea3 = new JTextArea();textarea3.setFont(new Font("宋體", Font.PLAIN, 15));textarea3.setLineWrap(true);textarea3.setEditable(false);JScrollPane scrollPane3 = new JScrollPane(textarea3);scrollPane3.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);/* 設置選擇卡 */tabbedPane.setFont(new Font("宋體", Font.PLAIN, 12)); // 設置tab按鍵中的字體tabbedPane.addTab("全局擇優搜索", scrollPane1); // 設置tab按鍵中的文字tabbedPane.addTab("A*搜索", scrollPane2);tabbedPane.addTab("寬度優先搜索", scrollPane3);jP.add(tabbedPane); // 添加選擇卡面板// 文本域（顯示用時）ja = new JTextArea();JScrollPane sp = new JScrollPane();sp.setBounds(370, 410, 275, 360); // 創建滾動條面板，也不用設置文本域的位置了ja.setFont(new Font("宋體", Font.PLAIN, 12));ja.setLineWrap(true); // 自動換行sp.setViewportView(ja); // 將文本域加入到滾動條面板中sp.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); // 總是出現滾動條ja.setEditable(false); // 設置不可編輯文本域，只能通過程序執行修改jP.add(sp); // 只需將滾動條面板加入jP中，無需將文本域加入到jP中// 左側文本域上方文字信息："執行過程"JLabel label3 = new JLabel("執行過程");label3.setBounds(120, 220, 275, 330);label3.setFont(new Font("華文行楷", Font.PLAIN, 25));jP.add(label3);// 右側文本域上方文字信息："時間和最短移動次數"JLabel label4 = new JLabel("時間和最短移動次數");label4.setBounds(395, 220, 275, 330);label4.setFont(new Font("華文行楷", Font.PLAIN, 25));jP.add(label4);// jP.setFocusable(false); // 讓光標開始不聚焦return jP;}public int calDe(String[] s) { // 計算逆序對數int sum = 0;for (int i = 0; i <= size; i++) {for (int j = i + 1; j <= size; j++) {if (s[j].equals(" ")) continue;if (s[i].compareTo(s[j]) > 0) sum++;}}return sum;}// A*class Astar {final int offset[][] = new int[][]{{-1, 1, 0, 0}, {0, 0, -1, 1}};int evaluate_function = 1; // 啟發函數1int eightOrFifteen = 0; // 0:8 1:15int size; // 方格總個數int size_unit; // 方格寬高Map<String, Boolean> closed_list = new HashMap<String, Boolean>();String[] original_status;String goal; // 即空格串MyLink open_list = new MyLink();AllNodes allNodes; // AllNodes是父類，單純為了繼承其目標狀態public Astar(String[] original_status, String[] target_status, int evaluate_function, int eightOrFifteen) {allNodes = new AllNodes(target_status);// 賦值this.evaluate_function = evaluate_function;this.eightOrFifteen = eightOrFifteen;this.original_status = original_status;this.size = (eightOrFifteen == 0 ? 9 : 16); // 總個數this.size_unit = (eightOrFifteen == 0 ? 3 : 4); // 每行每列個數this.goal = new String(" ");v2time = AstarAlgorithm()*1.0/1e6;}public Node getMinfNode() { // 獲取OPEN中最小f對應的節點Node pp = open_list.head;Node p = pp.next;Node pres = pp;Node res = p;while (p != null) {if (p.f < res.f) {res = p;pres = pp;}p = p.next;pp = pp.next;}pres.next = res.next;closed_list.put(changeStringArrayTo(res.status), true);return res;}public void printPath(Node tnode) { // 顯示路徑，將路徑添加到文本域中if (v2steps == 0) v2steps = tnode.g;if (tnode == null) return;printPath(tnode.parent);textarea2.append("\n--第 " + tnode.g + " 步--\n");for (int i = 0; i < size_unit; i++) {for (int j = 0; j < size_unit; j++) {if (j == 0) textarea2.append(" ");textarea2.append("" + tnode.status[i * size_unit + j] + (j == size_unit - 1 ? '\n' : '|'));}if (i != size_unit - 1) {textarea2.append(" ");for (int j = 0; j < 2 * size_unit - 1; j++)textarea2.append("-");textarea2.append("\n");}}}// 這個函數是為了方便Map的鍵值不用使用數組，將每個方格中的字符串以三個dollar符隔開，而譯碼的時候也按照三個dollar符切開即可；// 之所以選三個dollar符是因為方格最多可以輸入兩個字符，三個字符作為分隔符最有效public String changeStringArrayTo(String[] str_arr) {String res = new String("");for (int i = 0; i < size; i++) res += str_arr[i] + "$$$";return res;}public long AstarAlgorithm() {long starttime2 = System.nanoTime();System.currentTimeMillis();open_list.addNode(-1, original_status, null, evaluate_function, eightOrFifteen); // 插入起點int tmp_cnt = 0;while (open_list.head.next != null) {Node current_node = getMinfNode(); // for (int i = 0;i < size;i ++) System.out.print(current_node.status[i] + " ");System.out.println(); // 測試輸出if (current_node.evaluate(evaluate_function, eightOrFifteen) == 0) {long endtime = System.nanoTime();// 找到最短路System.out.println(tmp_cnt);printPath(current_node);return endtime - starttime2; // 時間}tmp_cnt++;int goal_position = 0; // 獲取goal位置while (!current_node.status[goal_position].equals(goal)) goal_position++;for (int k = 0; k < 4; k++) { // 四個方向int x = goal_position / size_unit, y = goal_position % size_unit;int tx = x + offset[0][k], ty = y + offset[1][k];if (tx < 0 || ty < 0 || tx >= size_unit || ty >= size_unit) continue;String[] temp_status = new String[size]; // 拷貝一份for (int i = 0; i < size; i++) { // 拷貝并實現交換if (i == x * size_unit + y)temp_status[i] = new String(current_node.status[tx * size_unit + ty]);else if (i == tx * size_unit + ty)temp_status[i] = new String(current_node.status[x * size_unit + y]);else temp_status[i] = new String(current_node.status[i]);}if (closed_list.containsKey(changeStringArrayTo(temp_status))) continue;Node pp = open_list.head;Node p = pp.next;while (p != null) {if (p.status == temp_status) break;p = p.next;pp = pp.next;}int h = new Node(temp_status, evaluate_function, eightOrFifteen).evaluate(evaluate_function, eightOrFifteen);if (p == null || p.f > current_node.g + 1 + h) { // 比較fopen_list.addNode(current_node.g, temp_status, current_node, evaluate_function, eightOrFifteen);}}}return 0;}}// BFSclass BFS {final int offset[][] = new int[][]{{-1, 1, 0, 0}, {0, 0, -1, 1}};public int eightOrFifteen = 0; // 0:8 1:15public int size; // 方格總個數public int size_unit; // 方格寬高public Map<String, String> st = new HashMap<String, String>();public String[] original_status;public String target_string;public String goal = " ";public Queue<String> q = new LinkedList<String>();public BFS(String[] original_status, String[] target_status, int eightOrFifteen) {// 賦值this.size = (eightOrFifteen == 0 ? 9 : 16);this.size_unit = (eightOrFifteen == 0 ? 3 : 4);this.eightOrFifteen = eightOrFifteen;this.original_status = original_status;this.target_string = changeStringArrayTo(target_status); // size的賦值要于此之前！v3time = BFSAlgorithm()*1.0/1e6;}public String changeStringArrayTo(String[] str_arr) {String res = new String("");for (int i = 0; i < size; i++) res += str_arr[i] + "$$$";return res;}// 解碼public String[] recoveryToStringArray(String str) {return str.split("\\$\\$\\$");}public void printPath(String cur) {int idx = 0;Stack<String> stack = new Stack<String>(); // 路徑輸出使用的是棧do {stack.push(cur);cur = st.get(cur);} while (cur != null);while (!stack.empty()) {String[] s = recoveryToStringArray(stack.peek());stack.pop();textarea3.append("\n--第 " + idx + " 步--\n");for (int i = 0; i < size_unit; i++) {for (int j = 0; j < size_unit; j++) {if (j == 0) textarea3.append(" ");textarea3.append("" + s[i * size_unit + j] + (j == size_unit - 1 ? '\n' : '|'));}if (i != size_unit - 1) {textarea3.append(" ");for (int j = 0; j < 2 * size_unit - 1; j++)textarea3.append("-");textarea3.append("\n");}}idx++;}v3steps = idx - 1;}public long BFSAlgorithm() {long starttime = System.nanoTime();String ori = changeStringArrayTo(original_status);q.add(ori);st.put(ori, null);while (!q.isEmpty()) {String top = q.peek();q.poll();String[] stringArrayOfTop = recoveryToStringArray(top);if (top.equals(target_string)) {long endtime = System.nanoTime();printPath(top);return endtime - starttime;}int goal_position = 0;while (!stringArrayOfTop[goal_position].equals(goal)) goal_position++;for (int k = 0; k < 4; k++) {int x = goal_position / size_unit, y = goal_position % size_unit;int tx = x + offset[0][k], ty = y + offset[1][k];if (tx < 0 || ty < 0 || tx >= size_unit || ty >= size_unit) continue;String[] temp_string = new String[size]; // 拷貝一份for (int i = 0; i < size; i++) { // 拷貝并實現交換if (i == x * size_unit + y) temp_string[i] = new String(stringArrayOfTop[tx * size_unit + ty]);else if (i == tx * size_unit + ty)temp_string[i] = new String(stringArrayOfTop[x * size_unit + y]);else temp_string[i] = new String(stringArrayOfTop[i]);}String temp = changeStringArrayTo(temp_string);if (st.containsKey(temp)) continue;st.put(temp, top);q.add(temp);}}return 0;}}// GOSclass GOS {final int offset[][] = new int[][]{{-1, 1, 0, 0}, {0, 0, -1, 1}};int evaluate_function = 1; // 啟發函數1int eightOrFifteen = 0; // 0:8 1:15int size; // 方格總個數int size_unit; // 方格寬高Map<String, Boolean> closed_list = new HashMap<String, Boolean>();String[] original_status;String goal;MyLink open_list = new MyLink();AllNodes allNodes;public GOS(String[] original_status, String[] target_status, int evaluate_function, int eightOrFifteen) {allNodes = new AllNodes(target_status);// 賦值this.evaluate_function = evaluate_function;this.eightOrFifteen = eightOrFifteen;this.original_status = original_status;this.size = (eightOrFifteen == 0 ? 9 : 16);this.size_unit = (eightOrFifteen == 0 ? 3 : 4);this.goal = new String(" ");v1time = GOSAlgorithm()*1.0/1e6;}public Node getMinfNode() {Node pp = open_list.head;Node p = pp.next;Node pres = pp;Node res = p;while (p != null) {if (p.f < res.f) {res = p;pres = pp;}p = p.next;pp = pp.next;}pres.next = res.next;closed_list.put(changeStringArrayTo(res.status), true);return res;}public void printPath(Node tnode) {if (v1steps == 0) v1steps = tnode.g;if (tnode == null) return;printPath(tnode.parent);textarea1.append("\n--第 " + tnode.g + " 步--\n");for (int i = 0; i < size_unit; i++) {for (int j = 0; j < size_unit; j++) {if (j == 0) textarea1.append(" ");textarea1.append("" + tnode.status[i * size_unit + j] + (j == size_unit - 1 ? '\n' : '|'));}if (i != size_unit - 1) {textarea1.append(" ");for (int j = 0; j < 2 * size_unit - 1; j++)textarea1.append("-");textarea1.append("\n");}}}public String changeStringArrayTo(String[] str_arr) {String res = new String("");for (int i = 0; i < size; i++) res += str_arr[i] + "$$$";return res;}public long GOSAlgorithm() {long starttime = System.nanoTime();open_list.addNode(-1, original_status, null, evaluate_function, eightOrFifteen); // 插入起點while (open_list.head.next != null) {Node current_node = getMinfNode(); // for (int i = 0;i < size;i ++) System.out.print(current_node.status[i] + " ");System.out.println(); // 測試輸出if (current_node.evaluate(evaluate_function, eightOrFifteen) == 0) {long endtime = System.nanoTime();// 找到最短路printPath(current_node);return endtime - starttime;}int goal_position = 0; // 獲取goal位置while (!current_node.status[goal_position].equals(goal)) goal_position++;for (int k = 0; k < 4; k++) {int x = goal_position / size_unit, y = goal_position % size_unit;int tx = x + offset[0][k], ty = y + offset[1][k];if (tx < 0 || ty < 0 || tx >= size_unit || ty >= size_unit) continue;String[] temp_status = new String[size]; // 拷貝一份for (int i = 0; i < size; i++) { // 拷貝并實現交換if (i == x * size_unit + y)temp_status[i] = new String(current_node.status[tx * size_unit + ty]);else if (i == tx * size_unit + ty)temp_status[i] = new String(current_node.status[x * size_unit + y]);else temp_status[i] = new String(current_node.status[i]);}if (closed_list.containsKey(changeStringArrayTo(temp_status))) continue;Node pp = open_list.head;Node p = pp.next;while (p != null) {if (p.status == temp_status) break;p = p.next;pp = pp.next;}int h = new Node(temp_status, evaluate_function, eightOrFifteen).evaluate(evaluate_function, eightOrFifteen);if (p == null) {open_list.addNode(current_node.g, temp_status, current_node, evaluate_function, eightOrFifteen);}}}return 0;}}}

MyLink.java 程序

A*算法和全局擇優搜索中使用的自定義鏈表數據結構，其中包含節點類和計算啟發信息的函數。

import javafx.scene.Parent;/*** @author LJR* @create 2021-11-05 15:38*/class AllNodes {public static String[] target_status; // 靜態public AllNodes() {}public AllNodes(String[] status) {target_status = status;} }class Node extends AllNodes {public int f, g, h;public String[] status;public Node next = null; // 鏈表中的nextpublic Node parent = null; // 結果路徑中的parent的狀態public Node() {}public Node(Node node, int eightOrFifteen) {f = node.f;g = node.g;h = node.h;status = new String[(eightOrFifteen==0?9:16)];for (int i = 0;i < (eightOrFifteen==0?9:16);i ++) status[i] = new String(node.status[i]);parent = node.parent;next = node.next;}public Node(String[] s, int option, int eightOrFifteen) {this.status = s;this.h = evaluate(option, eightOrFifteen);this.f = g + this.h;}public Node(int g, String[] s, int option, int eightOrFifteen) { // 0:8 1:15this.status = s;this.h = evaluate(option, eightOrFifteen);this.f = g + this.h;this.g = g;}public Node(int g, String[] s, Node parent_node, int option, int eightOrFifteen) { // 0:8 1:15this(g, s, option, eightOrFifteen);this.parent = parent_node;}// 計算h(n)public int evaluate(int option, int eightOrFifteen) {int res = 0;int size = (eightOrFifteen == 0 ? 9 : 16);int size_unit = (eightOrFifteen == 0 ? 3 : 4);if (option == 1) { // System.out.println("h(n)定義為當前節點與目標節點差異的度量：即當前節點與目標節點格局相比，位置不符的數字個數。");for (int i = 0; i < size; i++)res += (status[i].equals(target_status[i]) ? 0 : 1);} else if (option == 2) { // System.out.println("h(n)定義為當前節點與目標節點距離的度量：當前節點與目標節點格局相比，位置不符的數字移動到目標節點中對應位置的最短距離之和。");for (int i = 0; i < size; i ++) {for (int j = 0;j < size; j ++) {if (status[i].equals(target_status[j])) {res += Math.abs((i / size_unit) - (j / size_unit)) + Math.abs((i % size_unit) - (j % size_unit));break;}}}}return res;}}public class MyLink {public Node head = new Node(-1, null, -1, -1);public void addNode(int preNodeg, String[] status, Node parent, int option, int eightOrFifteen) {Node newNode = new Node(preNodeg + 1, status, parent, option, eightOrFifteen); // 實例化一個節點if (head.next == null) {head.next = newNode;return;}Node tmp = head.next;while (tmp.next != null) {tmp = tmp.next;}tmp.next = newNode;}}

LimitedLength.java 程序

該程序用于限制用戶向方格中輸入的字符數不得大于2。

import javax.swing.text.AttributeSet; import javax.swing.text.BadLocationException; import javax.swing.text.PlainDocument;public class LimitedLength extends PlainDocument {private static final long serialVersionUID = 1L;private int max_length = 2;@Overridepublic void insertString(int offs, String str, AttributeSet a) throws BadLocationException {if (str == null) return ;if(getLength() + str.length() > max_length) return ;else super.insertString(offs, str, a);} }

總結

以上是生活随笔為你收集整理的【人工智能】Astar算法求解8数码问题（QDU）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。