2019-04-23

N-puzzle Problem

N-Puzzle Problem

[TOC]

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:

1556368035445

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上。

First phase：

所需解决样例以及最多时间：

对于以下两个实例，均能够在1秒之类解出

1556377705625

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) 的好坏直接影响评估函数的好坏。

流程图：

//N-puzzle-Problem\

1556381217714

从初始状态出发 =>经过一系列中间状态 =>最终到达目标状态（或者无法到达）。

该算法用于经过中间状态时候的行进策略（其中的中间状态或者由题目给出，或者在前边已经推导得出）。

优点：与广度优先搜索策略和深度优先搜索策略相比，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 frontier
			if (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

No	Initial State	Steps	Time	Limited Time
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阶的，能够在与老师程序同级别的时间内，解决相同的问题实例。

1556382042355

1556382108542

对于以上后面几个初始状态，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函数中调用：

1 2	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 为1
	if(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= 10
			mat[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

No	Initial State	Steps	Time	Limited Time
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分钟，不过这个时间肯定也不是我们所能接受的，我们需要的是在一分钟内

1556378270793

、

对于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、非可加性的模式数据库

1556464725925

图显示了十五个拼图拼贴的子集，称为边缘拼贴。对于给定状态，使边缘拼贴到其目标位置所需的最小移动次数（包括其他拼块的所需移动）是解决整个拼图所需的移动次数的下限。

与其他瓦片的位置无关。

因此，我们可以预先计算所有这些值，将它们存储在内存中，并在搜索过程中查找它们。由于有七个边缘拼贴和一个空白，以及十六个不同的位置，边缘拼贴和空白的可能排列总数为16！/（16-8）！= 518,918,400。

对于每个排列，我们存储将数字图块和空白移动到其目标位置所需的移动次数，这需要不到一个字节。因此，我们可以将整个模式数据库表存储在少于495兆字节的内存中。

存储表后，我们使用IDA *搜索特定问题实例的最佳解决方案。在生成每个状态时，使用数字图块和空白的位置来计算图案数据库中的索引，并且使用相应的条目，即解决数字图块和空白所需的移动的数量，作为该状态的启发式值。

使用这种模式数据库，Culberson和Schaeffer将生成的节点数量减少了346倍，并将运行时间缩短了6倍，与曼哈顿距离相比[1]。将此与另一个模式数据库相结合，并将两个数据库值的最大值作为整体启发式值，将生成的节点减少大约一千，将运行时间减少十二。

局限：

非加性模式数据库的主要限制是它们无法解决更大的问题。例如，由于二十四个拼图包含25个不同的位置，一个覆盖n个拼贴和空白的模式数据库需要25！/（25 - n - 1）！条目。仅有六个图块和空白的数据库将需要超过24亿个条目。此外，来自仅六个瓦片的数据库的值将小于所有瓦片的曼哈顿距离。对于多个数据库，允许组合它们的最佳方法是获取其值的最大值，即使这些图块组是不相交的。原因是非加性模式数据库值包括解决模式切片所需的所有移动，包括其他切片的移动

可改进：

我们希望能够在不违反可接受性的情况下对其值进行求和，以获得更准确的启发式，而不是采用最大的不同模式数据库值。这是不相交模式数据库的主要思想。

4、不相交的模式数据库（可加性的）

为了构建滑动拼图的不相交模式数据库，我们将拼贴划分为不相交的组，这样任何拼贴都不属于多个组。然后，我们预先计算每组中瓦片最小移动次数的表格，这些移动是将这些瓦片移动到其目标位置所需的。我们称这些表为一组，每组一个瓦片，一个不相交的模式数据库，或简称为adisjoint数据库。然后，给定搜索中的特定状态，对于每组图块，我们使用这些图块的位置来计算相应表格中的索引，检索解决该组中图块所需的移动次数，然后将每个组的值相加，以计算给定状态的整体启发式。该值至少与曼哈顿距离一样大，并且通常更大，因为它考虑了同一组中的切片之间的交互。

上述不相交数据库和非附加数据库之间的关键区别在于，非加法数据库包括解决图案图块所需的所有移动，包括不在图案集中的图块移动。结果，给定两个这样的数据库，即使它们的区块之间没有重叠，我们也只能将这两个值中的最大值作为可接受的启发式，因为在一个数据库中计数的移动可能会移动另一个数据库中的区块，因此这些举动将被计算两次。在不相交的数据库中，我们只计算组中切片的移动。

这两种类型的数据库之间的第二个区别是我们的不相交数据库不考虑空白位置，减小它们的大小。一个不相交的数据库包含了解决一组图块所需的最小移动量，对于所有可能的空白位置。

该搜索的状态由所讨论的图块的位置和空白的位置唯一地确定，并且仅计算感兴趣的图块的移动。由于滑动拼图拼图的操作员是可逆的，我们可以从其目标位置开始对每个拼贴执行单个搜索，并记录将拼块移动到每个其他位置需要多少移动。对所有图块执行此操作会生成一组表格，这些表格为每个图块的每个可能位置提供距其目标位置的曼哈顿距离。

对于每个图块，我们可以使用上述广度搜索来自动计算将图块从任何位置移动到其目标位置所需的最小移动次数的表格。这样的一组表格将包含从每个位置到其目标位置的每个瓦片的曼哈顿距离。然后，给定一个特定的状态，我们只需在相应的表中查找每个图块的位置并对结果值求和，从而计算曼哈顿距离的总和。

因此我们可以将曼哈顿距离相加以获得可接受的启发式

作为一般规则，在对图块进行分区时，我们希望将目标状态中彼此靠近的图块组合在一起，因为这些图块将彼此交互最多。

1556466424757

1556466472252

第一行给出了曼哈顿距离启发式的结果。

第二行是通过线性冲突增强的曼哈顿距离。

第三行表示启发式，它是图4左侧所示的七和八数据库值的总和

第四行表示通过从第三行的启发式开始计算的启发式。然后，我们计算图4右侧所示的七和八数据库值的总和。最后，整体启发式是这两个总和中的最大值。

第一个数据列显示了启发函数在1000个初始状态下的平均值。第二列给出了每个问题实例生成的平均节点数，以找到第一个最优解。第三列显示算法的平均速度，以每秒节点数为单位，, on a 440 MegaHertz Sun Ultra10 workstation. 。第四列表示找到第一个最佳解决方案的平均运行时间（以秒为单位）。最后一列给出了生成的平均节点数，以找到问题实例的所有最优解。

使用[12]中开发的分析结果，我们可以预测，单独使用曼哈顿距离解决二十四难题每个问题平均需要大约5万年！对于10,000个初始状态的随机样本，曼哈顿平均距离是76.078个移动，而对于我们的不相交数据库启发式，它是81.607个移动。

采用其最大值来组合来自不同模式数据库的启发式算法。这是最通用的方法，因为任何两个可接受的启发式方法的最大值始终是另一个可接受的启发式方法。我们引入了不相交模式数据库，以允许将来自不同数据库的值相加，从而产生更准确的启发式值。不相交的模式数据库将子目标集划分为不相交的组，然后将解决每个组中所有子目标的成本加在一起。这要求组不相交，并且单个运算符仅影响单个组中的子目标。例如，在滑动拼图游戏中，每个操作员仅移动一个拼贴。这与获取不同值的最大值一样有效，但更准确，并且仍然可以接受。

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= 10
			tmp[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

No	Initial State	Steps	Time	Limited Time
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）Richard E. Korf a,∗, Ariel Felner b ，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

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