终于，在学习了完深搜和广搜、Dijkstra、二叉堆和优先队列以及A*算法之后，可以看一下IDA*算法了。因为求解4x4的拼图游戏所要搜素的节点数很大，所以应该采用IDA*算法，而3x3的拼图游戏则可以采用A*算法。
IDA*算法是A*的一个变形，和A*算法不同的是他不保存之前的搜索状态(意味着同一个节点可能会被搜索多次)，它的搜索效率会稍微低于A*算法。笔者对于IDA*的翻译是迭代深度的A*算法，它是一种有信息提示的搜索(informed search)，但其实现思想是基于无信息提示的IDDFS(iterative deepening depth-first search)。
下面先来讨论IDDFS,再来实现基于IDDFS的IDA*。
打开维基百科,发现没有中文版的介绍。于是笔者只能用咱的蹩脚英语翻译一下了：
<译>Iterative deepening depth-first search (IDDFS)是一个反复调用depth-limited search的状态空间搜索策略，每次迭代都会增加深度限制直到d(d为深度最浅的可行解对应的深度)。IDDFS等同于广度优先搜索，但是它需要更少的内存开销。每次迭代它会以深度优先搜索的顺序来访问节点，但是总体的累积效果还是广度优先搜索的。
好了，有点乱哈，一下BFS一下DFS的。咱还是不翻译了，这么说吧，我们可以把一次深度优先搜索看做一个深度为n的搜索单元，这个搜索单元是基于上级的广度优先搜索的。然后该深度n会在每次迭代是不断加深，直到找到可行解为止。因为深度优先是不存储"备选节点“的，于是整个IDDFS的内存开销不大，又因为搜索的上层控制是广度优先搜索，于是整个IDDFS等同于广度优先搜索。IDDFS集合了DFS和BFS两者的优点，其空间复杂度是O(bd),时间复杂度是O(b^d)。感兴趣的朋友可以查看笔者的另一篇文章：IDDFS(Iterative deepening depth-first search)的Java实现
现在来说一下IDA*，设想有这样的一个场景，有老板A和员工B，老板A有一个拼图游戏需要求解，老板观察了一下问题，根据问题的manhattan距离得到了一个可能的最小步骤解n。于是把员工B叫过来，说你给我在n步之内解出题目。于是员工B开始解题，他的方法很简单采用深搜的方法搜索所有符合该manhattan距离限制的解，此时，可能当员工B遍历了所以的结果后还是没有找到可行解，于是他只能把这个结果和老板A说了，老板A看了以后，允许解题步骤限制+1，然后员工B在以这个n+1的步骤限制，从头开始做一个遍历，可能他还没有找到可行解，他就会再去找老板，老板说再加1吧，如此循环，直到员工B求得可行解。
实现代码：
package com.wly.algorithmbase.search;
/**
* IDA*求解15puzzle问题
* IDA*整合了IDDFS和A*算法。其中IDDFS控制了求解过程中的内存开销，A*算法意味着"启发式"搜索。
* IDA*可以理解成迭代深度的A*算法，其中这里的"深度"指的是问题的解的"假定损耗"。
* 使"假定损耗"不断迭代增加，检验是否能在"假定损耗"的前提找到可行解，如果不行的话，就继续迭代。
* 这里和A*算法不同的是没有开放列表，由于采用了IDDFS的策略，IDA*是深度优先搜索的，故此没有开放列表。
* 可是求解15Puzzle时，使用的基于"深搜"的IDA*竟然不回溯的，这真是很奇怪啊!
* 因为在求解15puzzle问题之前，必须使用一定的判断依据来论证问题的可解性，故此在问题可解的前提下使用
* IDA*求解问题总是可以得到一个可行解的(只不过这个可行解可能不是最优解而已)。
* @author wly
* @date 2013-12-20
*
*/
public class IDAStarAlgorithm {
//分别代表左、上、右、下四个移动方向的操作数
private int[] up = {-1,0};
private int[] down = {1,0};
private int[] left = {0,-1};
private int[] right = {0,1};
/**注意，这里UP和DOWN，LEFT和RIGHT必须是两两相对的，因为后面代码中使用
* ((dPrev != dCurr) && (dPrev%2 == dCurr%2))来判断前后两个移动方向是否相反
*/
private final int UP = 0;
private final int DOWN = 2;
private final int LEFT = 1;
private final int RIGHT = 3;
private int SIZE;
//各个目标点坐标
private int[][] targetPoints;
//用于记录移动步骤，存储0,1,2,3,对应上，下，左，右
private static int[] moves = new int[100000];
private static long ans = 0;; //当前迭代的"设想代价"
//目标状态
private static int[][] tState = {
{1 ,2 ,3 ,4 } ,
{5 ,6 ,7 ,8 } ,
{9 ,10,11,12} ,
{13,14,15,0 }
};
private static int[][] sState = {
{2 ,10 ,3 ,4 } ,
{1 ,0,6 ,8 } ,
{5 ,14,7,11} ,
{9,13,15,12 }
};
//初始状态
// private static int[][] sState = {
// {12,1 ,10,2 } ,
// {7 ,11,4 ,14} ,
// {5 ,0 ,9 ,15} ,
// {8 ,13,6 ,3}
// };
private static int blank_row,blank_column;
public IDAStarAlgorithm(int[][] state) {
SIZE = state.length;
targetPoints = new int[SIZE * SIZE][2];
this.sState = state;
//得到空格坐标
for(int i=0;i
targetPoints[state[blank_row1][blank_column1]][0]) {
h1 = h - 1;
} else if(direction == UP && blank_row1
< targetPoints[state[blank_row1][blank_column1]][0]){
h1 = h - 1;
} else if(direction == RIGHT && blank_column1
> targetPoints[state[blank_row1][blank_column1]][1]) {
h1 = h - 1;
} else if(direction == LEFT && blank_column1
< targetPoints[state[blank_row1][blank_column1]][1]) {
h1 = h - 1;
} else { //这种情况发生在当前移动位置已经处于最后位置，此时向任意方向的移动都会使得估价函数值变大
h1 = h + 1;
}
if(h1+dep+1>ans) { //剪枝
continue;
}
moves[dep] = direction;
//迭代深度求解
if(solve(state2, blank_row1, blank_column1, dep+1, direction, h1)) {
return true;
}
}