N-puzzle-Problem
?
N-Puzzle Problem
文章目錄
- N-Puzzle Problem
- Preview
- N-Puzzle Problem:
- N-Puzzle Problem 的可解性判斷
- Algorithms
- Three Stages and Related Algorithms
- First phase：
- 所需解決樣例以及最多時間：
- Algorithm：A*
- Code：
- Result:
- Second phase：
- 所需解決樣例以及最多時間：
- Algorithm：IDA*
- Code：
- Result:
- Third phase：
- 所需解決樣例以及最多時間：
- Algorithm：IDA*+Disjoint Pattern Database Heuristics
- 不斷優化的啟發式
- 1、曼哈頓距離
- 2、Manhattan Distance+Linear Conflict
- 3、非可加性的模式數據庫
- 4、不相交的模式數據庫（可加性的）
- 5、裁剪
- 6、動態分區模式數據庫啟發式 Dynamically-Partitioned Database Heuristics
- Code：不相交模式數據庫靜態6-6-3分區
- Result:
- Reference resources
Preview
N-Puzzle Problem:
在人工智能中，常常以N-Puzzle 問題的求解為例子來說明各種搜索策略。
N=K*K-1;
當N=8時，即為重排九宮格問題；當N=15時，即為十五迷問題；
一個狀態：N個數碼及一個空格的每一組置放形式，就形成了該問題的一個狀態。
N-Puzzle問題空間：所有（N+1)!個互不相同的狀態構成了一個N-Puzzle問題空間。
128M 1e7
操作：平移操作——把與空格相鄰 的某一數碼移入空格，稱這種操作為平移操作。
Problem:對于給定的任一初始狀態，使用平移操作，求解到目標狀態的最優步數 (最少步驟的移法) 以及移動的每一步狀態。
Goal position:
N-Puzzle Problem 的可解性判斷
分奇偶性然后根據逆序數判斷。
https://blog.csdn.net/Wood_Du/article/details/88730885
Algorithms
? N-Puzzle問題之所以能用來為例說明各種搜索策略，在于對于N-Puzzle問題，根據所需求解的初始狀態的復雜性，我們可以從爆搜開始，一步一步優化，當某種算法不足于求解時，可從優化數據結構，更換搜索算法上升一個境界，求得更加復雜的初始狀態的解。
：你會搜索嗎？
：我會爆搜 dfs+STL庫，但是DFS不能找到最優解；找最優解我會bfs
：那么存狀態呢？
：STL庫會很廢效率，我可以用hash判重；正好學了Zobrist Hash
：你還有什么可以進一步優化嗎？
：為了減少狀態的膨脹，我可以使用雙向廣搜，從初始狀態和目標狀態同時開始搜索，當某方向遇到另一個方向搜索過的狀態的時候，則搜索成功。兩個方向對接得到最后結果。
：這些都是無信息搜索算法，你可以使用有信息搜索嗎？
：啟發式搜索，那就想辦法減少搜索范圍，降低問題復雜度。這個時候我們就可以上A*+Hash了。啟發函數可以用錯位數或者曼哈頓距離。
：對于A*，需要每次找到Open表中f（f(n) = g(n)+h(n)) 最小的的元素。如果排序那么工作量會很大應該怎么辦呢？
：上優先隊列
：但是對于15碼問題，內存不能存下狀態了
:IDA*,解決內存問題。
是基于迭代加深的A*算法。并且不需要判重，不需要估價排序，用不到哈希表，空間需求量變得超級少。啟發函數用曼哈頓距離。在找最優解的時候，對超過目前最優解的地方進行剪枝，可導致搜索深度急劇減少。再check一下不要回到上個狀態。
：一般的15碼樣例都能解決，但是對于15碼最復雜的一些樣例，仍然需要三四十分鐘才能解出答案。還有什么可以優化嗎？
：那就只能去啃英文論文了。A.Felner,R.Korf的Disjoint Pattern Database Heuristics, 不相交模式數據庫啟發式算法。Additive Pattern Database Heuristics ——E.Korf，A.Felner，S.Hanan。這是一中新的設計更精確的可容許啟發式評價函數的方法，該方法基于模式數據庫。
本文我們將略去無信息搜索算法，求解最小步數，詳解算法為：
從A* 開始，優化數據結構；
再到IDA*；
最后用Pattern Database Heuristics解決15碼最復雜的樣例。
針對不同復雜度的樣例，本文后面將分為三個階段。
每個階段將說明解決的樣例，求解的要求時間，算法以及啟發函數，代碼實現以及每個樣例的解決時間。
對于展示代碼因為代碼量很大，并且是一個框架，所以只能展示核心代碼，若需要查看整個項目代碼，我會push到github上。
Three Stages and Related Algorithms
First phase：
所需解決樣例以及最多時間：
? 對于以下兩個實例，均能夠在1秒之類解出
Algorithm：A*
? A*算法是一種靜態網中求解最短路徑最有效的直接搜索方法也是也是一種啟發式算法。在搜索過程中使用啟發函數。估價函數與實際值越接近，最終搜索到目標格局的時間越快。
估價函數表示：
f(n) = g(n) + h(n) //f(n) 表示從初始狀態到目標狀態的估測代價 //g(n) 表示從初始狀態到當前狀態（節點n）的代價（已經確定） //h(n) 表示從當前狀態(節點n)到目標狀態的估測代價(預測)h(n) < h'(n) //h'(n)為當前狀態到目標狀態的實際步數h(n) 的好壞直接影響評估函數的好壞。
流程圖：
? 從初始狀態出發 =>經過一系列中間狀態 =>最終到達目標狀態（或者無法到達）。
? 該算法用于經過中間狀態時候的行進策略（其中的中間狀態或者由題目給出，或者在前邊已經推導得出）。
優點：與廣度優先搜索策略和深度優先搜索策略相比，A*算法不是盲目搜索，而是有提示的搜索
缺點：該算法一般要使用大量的空間用于存儲已搜索過的中間狀態，防止重復搜索。隨著樣例變復雜將會爆內存。
Code：
完整代碼傳送門：？？？
Search為A*算法，此代碼由于調用了框架中其他類的代碼所以比較抽象，我是邊百度java邊寫這個項目，沒學過java的娃娃面向百度編程。所以如果你會java,相信你噸噸噸就看明白我代碼了。
package core.astar;import core.problem.Action; import core.problem.Problem; //操作 import core.problem.State;import java.util.ArrayList;public class AStar {public AStar(Problem problem) {super();this.problem = problem;}public Node childNode(Node parent, Action action) {State state = problem.result(parent.getState(), action);//getPathCost 初始到當前的實際代價 stepCost 從父級到后續任務的路徑成本int pathCost = parent.getPathCost() + problem.stepCost(parent.getState(), action);int heuristic = problem.heuristic(state); //估計從狀態到目標狀態最便宜路徑的成本return new Node(state, parent, action, pathCost, heuristic);}public Problem getProblem() {return problem;}public void setProblem(Problem problem) {this.problem = problem;}public Node Search(){//起始節點State initState = problem.getInitialState();Node node = new Node(initState, null, null, 0, problem.heuristic(initState));Fringe fringe = new Fringe();fringe.insert(node);Explored explored = new Explored();while (true) {if (fringe.isEmpty()) return null; //失敗node = fringe.pop(); //choose the lowest-cost node in frontierif (problem.goalTest(node.getState())) return node;explored.insert(node.getState());for (Action action : problem.Actions(node.getState())) {Node child = childNode(node, action);//child.getState()不再在擴展節點的集合(Close表中）且fringe(Open表）中不存在狀態為state的節點 則將節點插入fringe中if (!explored.contains(child.getState()) && !fringe.contains(child.getState())) {fringe.insert(child);}else {/**如果鄰接結點N’在CLOSED表中，比較CLOSED表中的g(N')值和當前的g(N')值，如果當前的g(N')更小，那么刪除CLOSED表中的N'，把N設成N'的父節點，重新將N'插入OPEN表。如果鄰接結點N’在OPEN表中，比較OPEN表中的g(N')值和當前的g(N')值，如果當前的g(N')更小，那么刪除OPEN表中的N'，把N設成N'的父節點，重新將N'插入OPEN表。***/Node revisited = fringe.revisited(child.getState());if (revisited != null && revisited.evaluation() > child.evaluation()) {fringe.replace(revisited, child);//用child節點代替Fringe中的 revisited節點}}}} }//用動畫展示問題的解路徑public void solution(Node node){// Fix me// 調用Problem的drawWorld方法，和simulateResult方法problem.drawWorld();}private Problem problem; }Result:
項目目錄：Searching_Student: E:\University\AI\Searching_student
| 1 | 8, 6, 7, 2, 5, 4, 3, 0, 1 | 31 | 0.132s | 1s |
| 2 | 6, 4, 7, 8, 5, 0, 3, 2, 1 | 31 | 0.133s | 1s |
| 3 | 8, 13, 0, 6, 1, 15, 9, 14, 3, 4, 5, 11, 7, 2, 10, 12 | 52 | 1.929s | |
| 4 | 2,9,5,11, 8,3,4,14, 7,10,1,12, 0,15,6,13 | GC | ||
| 5 | 4,7,0,9,12,10,11,8,14,6,15,1,2,5,3,13 | GC |
Second phase：
所需解決樣例以及最多時間：
4階的，能夠在與老師程序同級別的時間內，解決相同 的問題實例。
對于以上后面幾個初始狀態，A*就已經無法解決。因為會生成太多新狀態并消耗大量內存維護這些列表。直接爆內存。
Algorithm：IDA*
IDA*算法, ID(Iterative Deepening)指的是迭代加深.
迭代加深搜索算法，在搜索過程中采用估值函數，以減少不必要的搜索。
IDA*算法核心：
? 設置每次可達的最大深度depth，若沒有到達目標狀態則加深最大深度。
? 采用估值函數，剪掉f(n)大于depth的路徑
IDA*算法的步驟
a、首先對初始狀態進行評估, 評估值作為最小限度, 而最大限度為自己的設置.這個評估值在這個問題中可以用此狀態到正確狀態的每個位置的曼哈頓距離來表示.
b、從最小限度到最大限度進行遍歷, 此值作為當前dfs的限度值, 這個限度不斷在有效范圍內遞增的過程就稱作迭代加深
c、進行dfs, 調整狀態, 將新狀態加入到新的dfs中, 直到找到了一個解(由于迭代加深, 此解為最優解). 進行回溯, 加入路徑, 算法結束.
IDA* is described as follows:
-
Set threshold equal to the heuristic evaluation of the initial state.
-
Conduct a depth-first search, pruning a branch when the cost of the latest node exceeds threshold. If a solution is found during the search, return it.
-
If no solution is found during the current iteration, increment threshold by the minimum amount it was exceeded, and go back to the previous step.
-
設置閾值等于初始狀態的啟發式評估。
-
進行深度優先搜索，在最新節點的成本超過閾值時修剪分支。如果在搜索過程中找到解決方案，請將其返回。
-
如果在當前迭代期間未找到解決方案，則將閾值增加超過最小值，然后返回上一步驟。
Code：
完整代碼傳送門：???
IDA*代碼除了讀取數據時調用了框架中的類，其他在一個類完成。
當時已經對框架有點絕望。由于我使用反向搜索使用框架會改很多類。加上不能與滑塊公用一個算法,所以寫在一個類里面。
第二階段我采用IDA*反向搜索，從目標狀態到初始狀態搜索，所以看代碼要注意。速度會快很多，對于給定樣例有的比老師快幾十倍，分析過原因。不過后面理論又被自己否定，應該是由于樣例的特殊性所以加快了速度。
main函數中調用：
ArrayList<Problem> problems = ProblemFactory.getProblems(1);test2(problems);test2():
public static void test2(ArrayList<Problem> problems) {for (Problem problem : problems) {Rstep=0;flg=0;result = new int[200][20];PuzzleState state = (PuzzleState) problem.getInitialState();side = state.getSide();tmp = state.getStatus();System.out.println();xx = new int[20];yy = new int[20];for (int i = 0; i < side * side; i++) {if (tmp[i] == 0) pos = i;else {xx[tmp[i]] = (i / side);yy[tmp[i]] = (i % side);}}if (!check(tmp)) System.out.println("No");mat = new int[20];for (int i = 0; i < side * side; i++) mat[i] = i + 1;mat[side * side - 1] = 0;pos = side * side - 1;double time1 = 0;Stopwatch timer1 = new Stopwatch(); // for(int i=0;i<100;i++){ // layer[i]=-1; // }//System.out.println(H(mat));for (bound = H(mat); bound <= 100; bound = dfs(0, H(mat), 4))if (flg == 1) break;time1 = timer1.elapsedTime();Ans_show();System.out.printf("行走了 %s 步，執行了 %.3f 秒\n", Rstep, time1);}}check（）方法：檢查是否可行解
public static boolean check(int[] a) {int tot=0;int flag=0;for(int i=0;i<side*side;i++){if(a[i]==0) {flag = i/side;continue;}for(int j=0;j<i;j++){if(a[j]>a[i]){tot++;}}}if(side%2==1) return tot%2==0;else{tot+= abs(flag-(side-1));if(tot%2==0) return true;else return false;}}H()方法：算曼哈頓距離
public static int H(int[] mat) {int h = 0;for (int i = 0; i < side*side-1; i++) {h += abs(xx[mat[i]] - (i / side)) + abs(yy[mat[i]] - (i % side));}return h;}ok()方法：判斷是否回到上一個狀態
public static boolean ok(int x,int y){if(x>y){int ff=x;x=y;y=ff;}if(x==0&y==1) return false; //與操作 1 1 為1if(x==2&&y==3) return false;return true;}IDA*:
public static int dfs(int step, int h, int las) {//g(n)+h(n)=f(n) 更新f(n) bound 最大限度 采用估值函數，剪掉f(n)大于depth的路徑if (step + h > bound) return step + h; // // if(layer[h]==-1)layer[h]=step; // if(step>layer[h]+15){ // System.out.printf("enter\n"); // return step+h; // }if (h == 0) { // 到達最終狀態 輸出g(n)即可// System.out.println(step);flg = 1;Rstep = step;return step;}int pos1 = pos;int ret = 127, x = pos1 / side, y = pos1 % side;int dx, dy, tar, ht, temp, i;for (i = 0; i < 4; i++) { //四個方向擴展dx = x + u[i];dy = y + p[i];if (dx < 0 || dy < 0 || dx > side - 1 || dy > side - 1 || !ok(i, las)) continue;tar = (dx * side) + dy; //計算出擴展出的新節點的一維坐標 2,2 2*4+2= 10mat[pos1] = mat[tar]; // 0的坐標等于擴展出來的點的坐標 a.mat[10]=11;mat[tar] = 0;//相當于swap()pos = tar;//計算新的h值//階段三主要在這修改 用不相交模式數據庫 h(n) 為當前節點的各點的曼哈頓距離和。ht = h - (Math.abs(xx[mat[pos1]] - dx) + Math.abs(yy[mat[pos1]] - dy)) + Math.abs(xx[mat[pos1]] - x) + Math.abs(yy[mat[pos1]] - y);if (step + ht <= bound)for (int k = 0; k < side*side; k++)result[step][k] = mat[k];temp = dfs(step + 1, ht, i);if (flg == 1) return temp;if (ret > temp) ret = temp;mat[tar] = mat[pos1];mat[pos1] = 0;pos = pos1;}return ret;}Result:
項目目錄：SearchingAstar: E:\University\AI\SearchingAstar
Limited Time為老師IDA跑的時間。從結果可以看出，反向IDA速度會更快。
| 1 | 8, 6, 7, 2, 5, 4, 3, 0, 1 | 31 | 0.000s | 0.047s |
| 2 | 6, 4, 7, 8, 5, 0, 3, 2, 1 | 31 | 0.003s | 0.047s |
| 3 | 8, 13, 0, 6, 1, 15, 9, 14, 3, 4, 5, 11, 7, 2, 10, 12 | 52 | 0.147s | 0.304s |
| 4 | 2,9,5,11, 8,3,4,14, 7,10,1,12, 0,15,6,13 | 51 | 2.423s | 3.652s |
| 5 | 4,7,0,9,12,10,11,8,14,6,15,1,2,5,3,13 | 56 | 0.554s | 12.367s |
| 6 | 12, 10, 3, 2, 0, 7, 14, 9, 1, 15, 5, 6, 8, 4, 13, 11 | 57 | 4.341s | 75.458s |
| 7 | 12, 1, 5, 6, 2, 11, 7, 9, 14, 10, 0, 4, 15, 3, 13, 8 | 50 | 0.058s | 3.671s |
| 8 | 4, 6, 15, 13, 12, 9, 10, 2, 8, 0, 7, 3, 14, 5, 1, 11 | 61 | 10.918s | 299.286s |
| 9 | 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0 | 70 | 1761.019s |
Third phase：
所需解決樣例以及最多時間：
? 4階的，能夠在1分鐘之內，解出以下實例
說明：對于這個樣例，曾聽說過老師用IDA*大概跑了四十多分鐘得出結果，不過由于樣例的特殊性，我們可以使用反向搜索，這樣會增快速度，我跑的時間不到30分鐘，不過這個時間肯定也不是我們所能接受的，我們需要的是在一分鐘內
、
對于15碼最復雜的狀態，A*肯定不能解，會爆內存。
IDA*雖然在空間上消耗少，但是由于初始狀態逆序數大，要搜很久，即大概三四十分鐘才能解決。
解決辦法：
a、曼哈頓距離加線性沖突——優化不了多少
b、添加不相交模式數據庫（Disjoint Pattern Database Heuristics）與靜態6-6-3分區
Algorithm：IDA*+Disjoint Pattern Database Heuristics
這個算法就只能硬著頭皮去讀E.Korf和A.Felner的論文Disjoint Pattern Database Heuristics。
就剛開始看了Tsan-sheng Hsu的一個應該是用來講課的pdf,看完之后？？？開始思考三連：我是，我去，我思？？？大概花了一下午的時間看完那篇pdf，當時是很崩潰的，伴隨著這門課的無理取鬧與老師的嗯。。。就已經絕望了，此時，滑塊那邊也沒有進展，老師張口閉口嚴格證明就很無語老師你是真的沒搞懂滑塊吧，真準備棄了。當天晚上又因為一個評估函數的優劣性被同學懟了，心情很糟糕。
第二天醒來已經中午，開始接手了N-Puzzle和滑塊兩個問題，開始了找牛逼網友過程。也找到了那篇論文開始啃，（英語真的毀我一生）。
參考論文：
Additive Pattern Database Heuristics ——E.Korf，A.Felner，S.Hanan
Disjoint Pattern Database Heuristics——E.Korf，A.Felner
以下內容來自論文（有些地方翻譯會有問題）
不斷優化的啟發式
1、曼哈頓距離
? 例如，在滑動拼圖拼圖中，要將拼貼從位置x移動到位置y，x和y必須相鄰，并且位置y必須為空。如果我們忽略空約束，我們得到一個簡化的問題，任何瓦片都可以移動到任何相鄰位置，并且多個瓦片可以占據相同的位置。在這個新問題中，瓦片彼此獨立，我們可以通過沿著最短路徑將每個瓦片移動到其目標位置來最佳地解決任何實例，計算所做的移動的數量。
? 解決這個簡化問題的最佳解決方案的成本恰好是曼哈頓從初始狀態到目標狀態的距離。由于我們刪除了對移動的約束，原始問題的任何解決方案也是簡化問題的解決方案，并且針對簡化問題的最優解決方案的成本是對原始問題的最優解決方案的成本的下限。
不足：曼哈頓距離之所以只是實際解決方案成本的下限，就是沒有考慮到滑塊的相互作用。
可改進：
通過考慮其中一些相互作用，我們可以計算出更準確的可接受的啟發函數。
2、Manhattan Distance+Linear Conflict
Historically, the linear-con?ict heuristic was the ?rst signi?cant improvementover Manhattan distance [5]. It applies to tiles in their goal row or column, but reversed relative to each other. For example, assume the top row of a given state contains the tiles (2 1) in that order, but in the goal state they appear in the order (1 2). To reverse them, one of the tiles must move out of the top row, to allow the other tile to pass by, and then move back into the top row. Since these two moves are not counted in the Manhattan distance of either tile, two moves can be added to the sum of the Manhattan distances of these two tiles without violating admissibility.
（從歷史上看，線性沖突啟發式是曼哈頓距離的第一個顯著改進[5]。它適用于目標行或列中的切片，但相對于彼此反轉。例如，假設給定狀態的頂行按順序包含tile（2 1），但在目標狀態下它們按順序出現（1 2）。要反轉它們，其中一個切片必須移出頂行，以允許另一個切片通過，然后移回頂行。由于這兩個移動不計入任一區塊的曼哈頓距離，因此可以將兩個移動添加到這兩個區塊的曼哈頓距離的總和而不違反可接受性。）
同樣的想法也可以應用于其目標列中的切片。實際上，目標位置的圖塊可以同時參與行和列的沖突。由于解決行沖突所需的額外移動是垂直移動，而解決列沖突所需的額外移動是水平移動，因此兩組移動都可以添加到曼哈頓距離，而不會違反允許性。與曼哈頓距離相比，線性沖突啟發式減少了一個數量級的節點數量，成本幾乎是速度的兩倍，總體加速比超過五倍。接下來的兩行用于不相交的模式數據庫啟發式。
3、非可加性的模式數據庫
圖顯示了十五個拼圖拼貼的子集，稱為邊緣拼貼。對于給定狀態，使邊緣拼貼到其目標位置所需的最小移動次數（包括其他拼塊的所需移動）是解決整個拼圖所需的移動次數的下限。
與其他瓦片的位置無關。
因此，我們可以預先計算所有這些值，將它們存儲在內存中，并在搜索過程中查找它們。由于有七個邊緣拼貼和一個空白，以及十六個不同的位置，邊緣拼貼和空白的可能排列總數為16！/（16-8）！= 518,918,400。
對于每個排列，我們存儲將數字圖塊和空白移動到其目標位置所需的移動次數，這需要不到一個字節。因此，我們可以將整個模式數據庫表存儲在少于495兆字節的內存中。
存儲表后，我們使用IDA *搜索特定問題實例的最佳解決方案。在生成每個狀態時，使用數字圖塊和空白的位置來計算圖案數據庫中的索引，并且使用相應的條目，即解決數字圖塊和空白所需的移動的數量，作為該狀態的啟發式值。
使用這種模式數據庫，Culberson和Schaeffer將生成的節點數量減少了346倍，并將運行時間縮短了6倍，與曼哈頓距離相比[1]。將此與另一個模式數據庫相結合，并將兩個數據庫值的最大值作為整體啟發式值，將生成的節點減少大約一千，將運行時間減少十二。
局限：
非加性模式數據庫的主要限制是它們無法解決更大的問題。例如，由于二十四個拼圖包含25個不同的位置，一個覆蓋n個拼貼和空白的模式數據庫需要25！/（25 - n - 1）！條目。僅有六個圖塊和空白的數據庫將需要超過24億個條目。此外，來自僅六個瓦片的數據庫的值將小于所有瓦片的曼哈頓距離。對于多個數據庫，允許組合它們的最佳方法是獲取其值的最大值，即使這些圖塊組是不相交的。原因是非加性模式數據庫值包括解決模式切片所需的所有移動，包括其他切片的移動
可改進：
我們希望能夠在不違反可接受性的情況下對其值進行求和，以獲得更準確的啟發式，而不是采用最大的不同模式數據庫值。這是不相交模式數據庫的主要思想。
4、不相交的模式數據庫（可加性的）
為了構建滑動拼圖的不相交模式數據庫，我們將拼貼劃分為不相交的組，這樣任何拼貼都不屬于多個組。然后，我們預先計算每組中瓦片最小移動次數的表格，這些移動是將這些瓦片移動到其目標位置所需的。我們稱這些表為一組，每組一個瓦片，一個不相交的模式數據庫，或簡稱為adisjoint數據庫。然后，給定搜索中的特定狀態，對于每組圖塊，我們使用這些圖塊的位置來計算相應表格中的索引，檢索解決該組中圖塊所需的移動次數，然后將每個組的值相加，以計算給定狀態的整體啟發式。該值至少與曼哈頓距離一樣大，并且通常更大，因為它考慮了同一組中的切片之間的交互。
上述不相交數據庫和非附加數據庫之間的關鍵區別在于，非加法數據庫包括解決圖案圖塊所需的所有移動，包括不在圖案集中的圖塊移動。結果，給定兩個這樣的數據庫，即使它們的區塊之間沒有重疊，我們也只能將這兩個值中的最大值作為可接受的啟發式，因為在一個數據庫中計數的移動可能會移動另一個數據庫中的區塊，因此這些舉動將被計算兩次。在不相交的數據庫中，我們只計算組中切片的移動。
這兩種類型的數據庫之間的第二個區別是我們的不相交數據庫不考慮空白位置，減小它們的大小。一個不相交的數據庫包含了解決一組圖塊所需的最小移動量，對于所有可能的空白位置。
該搜索的狀態由所討論的圖塊的位置和空白的位置唯一地確定，并且僅計算感興趣的圖塊的移動。由于滑動拼圖拼圖的操作員是可逆的，我們可以從其目標位置開始對每個拼貼執行單個搜索，并記錄將拼塊移動到每個其他位置需要多少移動。對所有圖塊執行此操作會生成一組表格，這些表格為每個圖塊的每個可能位置提供距其目標位置的曼哈頓距離。
對于每個圖塊，我們可以使用上述廣度搜索來自動計算將圖塊從任何位置移動到其目標位置所需的最小移動次數的表格。這樣的一組表格將包含從每個位置到其目標位置的每個瓦片的曼哈頓距離。然后，給定一個特定的狀態，我們只需在相應的表中查找每個圖塊的位置并對結果值求和，從而計算曼哈頓距離的總和。
因此我們可以將曼哈頓距離相加以獲得可接受的啟發式
作為一般規則，在對圖塊進行分區時，我們希望將目標狀態中彼此靠近的圖塊組合在一起，因為這些圖塊將彼此交互最多。
使用[12]中開發的分析結果，我們可以預測，單獨使用曼哈頓距離解決二十四難題每個問題平均需要大約5萬年！對于10,000個初始狀態的隨機樣本，曼哈頓平均距離是76.078個移動，而對于我們的不相交數據庫啟發式，它是81.607個移動。
第一行給出了曼哈頓距離啟發式的結果。
第二行是通過線性沖突增強的曼哈頓距離。
第三行表示啟發式，它是圖4左側所示的七和八數據庫值的總和
第四行表示通過從第三行的啟發式開始計算的啟發式。然后，我們計算圖4右側所示的七和八數據庫值的總和。最后，整體啟發式是這兩個總和中的最大值。
第一個數據列顯示了啟發函數在1000個初始狀態下的平均值。第二列給出了每個問題實例生成的平均節點數，以找到第一個最優解。第三列顯示算法的平均速度，以每秒節點數為單位，, on a 440 MegaHertz Sun Ultra10 workstation. 。第四列表示找到第一個最佳解決方案的平均運行時間（以秒為單位）。最后一列給出了生成的平均節點數，以找到問題實例的所有最優解。
采用其最大值來組合來自不同模式數據庫的啟發式算法。這是最通用的方法，因為任何兩個可接受的啟發式方法的最大值始終是另一個可接受的啟發式方法。我們引入了不相交模式數據庫，以允許將來自不同數據庫的值相加，從而產生更準確的啟發式值。不相交的模式數據庫將子目標集劃分為不相交的組，然后將解決每個組中所有子目標的成本加在一起。這要求組不相交，并且單個運算符僅影響單個組中的子目標。例如，在滑動拼圖游戲中，每個操作員僅移動一個拼貼。這與獲取不同值的最大值一樣有效，但更準確，并且仍然可以接受。
5、裁剪
used a technique, based on ?nite-state machines (FSMs), to prune duplicate nodes representing the same state arrived at via different paths in the graph
*使用了一種基于有限狀態機（FSM）的技術來修剪表示通過圖中不同路徑到達的相同狀態的重復節點[16]。 FSM修剪減少了IDA 在五個問題上產生的節點數量，范圍從2.4到3.6。對于這項工作，我們沒有使用FSM修剪，因為該技術很復雜，結果取決于所使用的特定FSM，使得其他研究人員難以重現相同的結果。
6、動態分區模式數據庫啟發式 Dynamically-Partitioned Database Heuristics
? 之前（Korf＆Felner，2002）我們展示了如何將滑動拼圖塊靜態劃分為不相交的拼貼組以計算可接受的啟發式，為每個狀態和問題實例使用相同的分區。在這里，我們擴展該方法并顯示它也適用于其他域。我們還提出了另一種加法啟發式方法，我們將其稱為動態分區模式數據庫。在這里，我們動態地將問題劃分為每個搜索狀態的不相交的子問題。
論文：Additive Pattern Database Heuristics
15-puzzle ;24-puzzle 動態模式數據庫會比靜態模式數據庫慢。
35-puzzle 動態模式數據庫會比靜態模式數據庫快。
Code：不相交模式數據庫靜態6-6-3分區
完整代碼傳送門：？？？
模式數據庫生成器：
/*** File: PatternDatabaseGenerator.java* Author: Brian Borowski* Date created: June 10, 2010* Date last modified: May 13, 2011*/ import java.io.BufferedOutputStream; import java.io.DataOutputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Set; import java.util.StringTokenizer;/*** Examples:* When generating a complete pattern database (i.e. no dummy tiles):* java PatternDatabaseGenerator 8 1,2,3,4,5,6,7,8,0 8-puzzle.db** When generating a disjoint additive pattern database (i.e. dummy tiles 'x'):* java PatternDatabaseGenerator 15 0,2,3,4,x,x,x,x,x,x,x,x,x,x,x,0 15-puzzle-663-0.db* java PatternDatabaseGenerator 15 1,x,x,x,5,6,x,x,9,10,x,x,13,x,x,0 15-puzzle-663-1.db* java PatternDatabaseGenerator 15 x,x,x,x,x,x,7,8,x,x,11,12,x,14,15,0 15-puzzle-663-2.db*/ public final class PatternDatabaseGenerator {public static final byte KEY_NOT_FOUND = -1;final int numOfTiles, numOfTilesMinusOne, dimension;PrimitiveHashMap tempMap;List<Entry> stateToCostEntries_8_puzzle;byte[] costTable_15_puzzle;long[] configTable_15_puzzle;public PatternDatabaseGenerator(final int numOfTiles, final long boardConfig,final byte dummyTile, final String filename) {this.numOfTiles = Node.numOfTiles = numOfTiles;this.numOfTilesMinusOne = numOfTiles - 1;this.dimension = Node.dimension = (int)Math.sqrt(numOfTiles);DataOutputStream dos = null;if (filename != null) {try {dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(filename)));} catch (final FileNotFoundException fnfe) {System.err.println("Error: Cannot open file '" + filename + "' for output.");System.exit(1);}}if (numOfTilesMinusOne == 15) {generateFifteenPuzzleDB(dummyTile, boardConfig);outputFifteenPuzzleData(filename, dos);} else {generateEightPuzzleDB(boardConfig);outputEightPuzzleData(filename, dos);}}private void generateFifteenPuzzleDB(final byte dummyTile,final long boardConfig) {final boolean[] tilesInSubset = computeSubset(dummyTile, boardConfig);final int[] tilePositions = new int[tilesInSubset.length];int numTilesInSubset = 0;for (int i = 0; i < tilePositions.length; ++i) {if (tilesInSubset[i]) {tilePositions[i] = numTilesInSubset++;}}breadthFirstSearch(boardConfig, tilesInSubset);final int tableLength = (int)Math.pow(2, numTilesInSubset * 4);costTable_15_puzzle = new byte[tableLength];configTable_15_puzzle = new long[tableLength];for (int i = tableLength - 1; i >= 0; --i) {costTable_15_puzzle[i] = KEY_NOT_FOUND;}System.err.println("Total states visited: " + tempMap.size());System.err.print("Removing duplicates...");final Set<Entry> entries = tempMap.entrySet();final Iterator<Entry> it = entries.iterator();while (it.hasNext()) {final Entry entry = it.next();final long config = entry.getKey();final byte movesRequired = entry.getValue();final int index = indexFor(config, true, tilesInSubset, tilePositions);final byte moves = costTable_15_puzzle[index];if (moves == KEY_NOT_FOUND || movesRequired < moves) {configTable_15_puzzle[index] = config;costTable_15_puzzle[index] = movesRequired;}}int numElements = 0;for (int i = tableLength - 1; i >= 0; --i) {if (costTable_15_puzzle[i] != KEY_NOT_FOUND) {++numElements;}}System.err.println("done");System.err.println("States in subset: " + numElements);}private void generateEightPuzzleDB(final long boardConfig) {breadthFirstSearch(boardConfig, null);final PrimitiveHashMap costMap_8_puzzle = new PrimitiveHashMap();System.err.println("Total states visited: " + tempMap.size());System.err.print("Removing duplicates...");final Set<Entry> entries = tempMap.entrySet();final Iterator<Entry> it = entries.iterator();while (it.hasNext()) {final Entry entry = it.next();final long config = entry.getKey();final byte movesRequired = entry.getValue();final byte moves = costMap_8_puzzle.get(config);if (moves == PrimitiveHashMap.KEY_NOT_FOUND || movesRequired < moves) {costMap_8_puzzle.put(config, movesRequired);}it.remove();}System.err.println("done");final int numElements = costMap_8_puzzle.size();stateToCostEntries_8_puzzle = new LinkedList<Entry>(costMap_8_puzzle.entrySet());System.err.print("Sorting entries...");Collections.sort(stateToCostEntries_8_puzzle, new Comparator<Entry>() {public int compare(final Entry e1, final Entry e2) {return e1.getValue() - e2.getValue();}});System.err.println("done");System.err.println("States in subset: " + numElements);}private void outputFifteenPuzzleData(final String filename,final DataOutputStream dos) {System.err.print("Writing file...");if (filename == null) {// Write values to stdout. User can redirect stdout to a file, if desired.for (int i = 0; i < configTable_15_puzzle.length; ++i) {final long config = configTable_15_puzzle[i];System.out.println((i + 1) + "," + config + "," +costTable_15_puzzle[i] + "," +Utility.longToString(config, numOfTiles));}} else {int i = 0;try {for ( ; i < costTable_15_puzzle.length; ++i) {dos.writeByte(costTable_15_puzzle[i]);}} catch (final IOException ioe) {System.err.println("Error: Cannot write entry " + i + " to file.");System.exit(1);} finally {try {if (dos != null) {dos.close();}} catch (final IOException ioe) { }}}System.err.println("done");}private void outputEightPuzzleData(final String filename,final DataOutputStream dos) {System.err.print("Writing file...");final Iterator<Entry> listIter = stateToCostEntries_8_puzzle.iterator();if (filename == null) {// Write values to stdout. User can redirect stdout to a file, if desired.int i = 1;while (listIter.hasNext()) {final Entry entry = listIter.next();final long config = entry.getKey();System.out.println(i + "," + config + "," + entry.getValue() +"," + Utility.longToString(config, numOfTiles));++i;}} else {int i = 0;try {while (listIter.hasNext()) {final Entry entry = listIter.next();dos.writeLong(((Long)entry.getKey()).longValue());dos.writeByte(((Byte)entry.getValue()).byteValue());++i;}} catch (final IOException ioe) {System.err.println("Error: Cannot write entry " + i + " to file.");System.exit(1);} finally {try {if (dos != null) {dos.close();}} catch (final IOException ioe) { }}}System.err.println("done");}private void breadthFirstSearch(final long boardConfig,final boolean[] tilesInSubset) {BFSNode currentState = new BFSNode(boardConfig);currentState.cost = 0;tempMap = new PrimitiveHashMap();tempMap.put(boardConfig, (byte)0);final Queue<BFSNode> queue = new LinkedList<BFSNode>();queue.add(currentState);byte previous = 1;while (true) {final char fromDirection = currentState.direction;if (fromDirection != 'R') {final BFSNode left = currentState.moveLeftNode(tilesInSubset);if (left != null) {final byte moves = tempMap.get(left.boardConfig);if (moves == PrimitiveHashMap.KEY_NOT_FOUND || left.cost < moves) {tempMap.put(left.boardConfig, left.cost);queue.add(left);}}}if (fromDirection != 'L') {final BFSNode right = currentState.moveRightNode(tilesInSubset);if (right != null) {final byte moves = tempMap.get(right.boardConfig);if (moves == PrimitiveHashMap.KEY_NOT_FOUND || right.cost < moves) {tempMap.put(right.boardConfig, right.cost);queue.add(right);}}}if (fromDirection != 'D') {final BFSNode up = currentState.moveUpNode(tilesInSubset);if (up != null) {final byte moves = tempMap.get(up.boardConfig);if (moves == PrimitiveHashMap.KEY_NOT_FOUND || up.cost < moves) {tempMap.put(up.boardConfig, up.cost);queue.add(up);}}}if (fromDirection != 'U') {final BFSNode down = currentState.moveDownNode(tilesInSubset);if (down != null) {final byte moves = tempMap.get(down.boardConfig);if (moves == PrimitiveHashMap.KEY_NOT_FOUND || down.cost < moves) {tempMap.put(down.boardConfig, down.cost);queue.add(down);}}}if (!queue.isEmpty()) {currentState = queue.remove();final byte movesRequired = currentState.cost;if (movesRequired > previous) {System.err.println("Generating boards with up to " + previous +" moves; map size: " + tempMap.size());previous = movesRequired;}} else {break;}}}private int indexFor(final long boardConfig, final boolean isFifteenPuzzle,final boolean[] tilesInSubset, final int[] tilePositions) {if (isFifteenPuzzle) {int hashCode = 0;for (int i = numOfTilesMinusOne; i >= 0; --i) {final int tile = (int)((boardConfig >> (i << 2)) & 0xF);if (tilesInSubset[tile]) {hashCode |= i << (tilePositions[tile] << 2);}}return hashCode;}return (int)boardConfig;}private boolean[] computeSubset(final byte dummyValue, final long boardConfig) {final boolean[] tilesInSubset = new boolean[numOfTiles];for (int pos = numOfTiles - 1; pos >= 0; --pos) {final byte tile = (byte)((boardConfig >> (pos << 2)) & 0xF);if (tile != dummyValue && tile != 0) {tilesInSubset[tile] = true;}}return tilesInSubset;}private static byte getArray(final String arrayString, final byte[] tiles,final int numOfTiles) {final StringTokenizer st = new StringTokenizer(arrayString, ",");final int numOfTokens = st.countTokens();// Validate the number of tiles entered.if (numOfTokens < numOfTiles) {System.out.println("Error: Input contains only " + numOfTokens +" of the " + numOfTiles + " tiles.");System.exit(1);} else if (numOfTokens > numOfTiles) {System.out.println("Error: Input exceeds required " +numOfTiles + " tiles.");System.exit(1);}// Create an array of String representations of the tile numbers.final String[] numStrings = new String[numOfTokens];int i = 0;while (st.hasMoreTokens()) {numStrings[i++] = st.nextToken();}// Make sure each string is a number.final int[] tilePositions = new int[numOfTiles];for (i = 0; i < tiles.length; ++i) {tiles[i] = -1;tilePositions[i] = -1;}for (i = 0; i < numStrings.length; ++i) {final String s = numStrings[i];try {final byte tile = Byte.parseByte(s);tiles[i] = tile;tilePositions[tile] = i;} catch (final NumberFormatException nfe) {if (!s.trim().toLowerCase().equals("x")) {System.err.println("Error: Expected integer or 'X' at index " + (i + 1) +", received '" + numStrings[i] + "'.");System.exit(1);}}}byte dummyTile = -1;// Make sure no tile number is missing from the input.for (i = 0; i < numOfTiles; ++i) {if (tilePositions[i] == -1) {if (i == 0) {System.err.println("Error: Tile 0 is missing for input.");System.exit(1);}dummyTile = (byte)i;break;}}// Replace 'X' (-1) tiles with the dummy value.for (i = 0; i < tiles.length; ++i) {if (tiles[i] == -1) {tiles[i] = dummyTile;}}return dummyTile;}public static void main(final String[] args) {if (args.length < 2 || args.length > 3) {System.err.println("Usage: java PatternDatabaseGenerator <num of tiles> <tile order> [filename]");System.exit(1);}int puzzleSize = 0;try {puzzleSize = Integer.parseInt(args[0].trim());if ((puzzleSize != 8) && (puzzleSize != 15)) {System.err.println("Error: Puzzle size must be either 8 or 15.");System.exit(1);}++puzzleSize;} catch (final NumberFormatException nfe) {System.err.println("Error: Puzzle size must be either 8 or 15.");System.exit(1);}final String tileOrder = args[1].trim();final byte[] tiles = new byte[puzzleSize];final byte dummyTile = getArray(tileOrder, tiles, puzzleSize);System.err.println("Using dummy tile: " + dummyTile);String filename = null;if (args.length == 3) {filename = args[2];}new PatternDatabaseGenerator(puzzleSize, Utility.byteArrayToLong(tiles), dummyTile, filename);} }IDA*:第三階段由于使用不相交可加性的靜態模式數據庫，所以不能像第二階段從目標狀態找到初始狀態。
public static int dfs(int step, int h, int las) {if (step + h > bound) return step + h; // 從目標開始找 f(n)剛開始最小 如果有更大的則更新 f(n) 反方向找 // if(layer[h]==-1)layer[h]=step; // if(step>layer[h]+15){ // System.out.printf("enter\n"); // return step+h; // }if (h == 0) { // 到達最終狀態 輸出g(n)即可// System.out.println(step);flg = 1;Rstep = step;return step;}int pos1 = pos;int ret = 127, x = pos1 / side, y = pos1 % side;int dx, dy, tar, ht, temp, i;for (i = 0; i < 4; i++) { //四個方向擴展dx = x + u[i];dy = y + p[i];if (dx < 0 || dy < 0 || dx > side - 1 || dy > side - 1 || !ok(i, las)) continue;tar = (dx * side) + dy; //計算出擴展出的新節點的一維坐標 2,2 2*4+2= 10tmp[pos1] = tmp[tar]; // 0的坐標等于擴展出來的點的坐標 a.mat[10]=11;tmp[tar] = 0;//相當于swap()pos = tar;//如果換一個評估函數呢//階段三 使用不相交模式數據庫得到評估函數 ht值為分為的塊的h的和加起來//ht = getH(tmp);//ht = h - (Math.abs(xx[mat[pos1]] - dx) + Math.abs(yy[mat[pos1]] - dy)) + Math.abs(xx[mat[pos1]] - x) + Math.abs(yy[mat[pos1]] - y);if (step + ht <= bound) {for (int k = 0; k < side * side; k++) {result[step][k] = tmp[k];}//System.out.println(i);if(i==0){redir[step]='r';}else if(i==1){redir[step]='l';}else if(i==2){redir[step]='d';}else{redir[step]='u';}}temp = dfs(step + 1, ht, i);if (flg == 1) return temp;if (ret > temp) ret = temp;tmp[tar] = tmp[pos1];tmp[pos1] = 0;pos = pos1;}return ret;}獲取h值：
static final int[] tilePositions = {-1, 0, 0, 1, 2, 1, 2, 0, 1, 3, 4, 2, 3, 5, 4, 5}; static final int[] tileSubsets = {-1, 1, 0, 0, 0, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 2}; public static int getH(int [] tmp) {int index0 = 0, index1 = 0, index2 = 0;for (int pos = 15; pos >= 0; --pos) {final int tile = tmp[pos];if (tile != 0) {final int subsetNumber = tileSubsets[tile];switch (subsetNumber) {case 2:index2 |= pos << (tilePositions[tile] << 2);break;case 1:index1 |= pos << (tilePositions[tile] << 2);break;default:index0 |= pos << (tilePositions[tile] << 2);break;}}}return PuzzleConfiguration.costTable_15_puzzle_0[index0] +PuzzleConfiguration.costTable_15_puzzle_1[index1] +PuzzleConfiguration.costTable_15_puzzle_2[index2]; }Result:
項目目錄： SearchingAstar: E:\University\AI\SearchingAstar3\SearchingAstar
| 3 | 8, 13, 0, 6, 1, 15, 9, 14, 3, 4, 5, 11, 7, 2, 10, 12 | 52 | 1.045s | |
| 4 | 2,9,5,11, 8,3,4,14, 7,10,1,12, 0,15,6,13 | 51 | 0.070s | |
| 5 | 4,7,0,9,12,10,11,8,14,6,15,1,2,5,3,13 | 56 | 0.028s | |
| 6 | 12, 10, 3, 2, 0, 7, 14, 9, 1, 15, 5, 6, 8, 4, 13, 11 | 57 | 0.180s | |
| 7 | 12, 1, 5, 6, 2, 11, 7, 9, 14, 10, 0, 4, 15, 3, 13, 8 | 50 | 0.009s | |
| 8 | 4, 6, 15, 13, 12, 9, 10, 2, 8, 0, 7, 3, 14, 5, 1, 11 | 61 | 0.987s | |
| 9 | 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0 | 70 | 4.758s | 60s |
Reference resources
（1）Ariel Felner，Richard E. Korf ，Disjoint pattern database heuristics
（2）Ariel Felner，Richard E. Korf，Sarit Hanan，Additive Pattern Database Heuristics
https://blog.csdn.net/u013009575/article/details/17140915
http://www.brian-borowski.com/software/puzzle/
http://www.ise.bgu.ac.il/engineering/upload/4273/naij.pdf
http://www.cnblogs.com/beilin/p/5981483.html
https://www.cnblogs.com/fujudge/p/7398153.html?utm_source=itdadao&utm_medium=referral
https://blog.csdn.net/shen_gan/article/details/8146027
https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/
總結
以上是生活随笔為你收集整理的N-puzzle-Problem的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 向UBOOT 中添加自己的板子
- 下一篇： 解决linux上耳机没有声音