引入：之前介绍了A算法，可以解决八数码问题，但是在练题的时候发现，P2324 [SCOI2005] 骑士精神这个题思路几乎与八数码相同，但是由于三宫格变成五宫格，用bfs的话空间复杂度非常高，且15深度下就有\(8^{15}\)种状态，用A-star复杂度高且需要存储所有开放节点，所以IDA算法应运而生啦，下面为大家详细介绍IDA*算法~~
介绍
IDA（迭代加深A）是一种基于启发式搜索的算法，结合了A算法和迭代加深深度优先搜索的优点，通过多次执行有深度限制的深度优先搜索来寻找目标，每次搜索的深度限制都会增加，直到找到目标为止，与传统的迭代加深不同的是，IDA在每次搜索中都使用启发式函数\(h(n)\)来剪枝，之探索“有潜力”找到目标的路径。
核心思想
DA通过迭代加深的方式控制搜索深度，结合A算法的启发式函数来指导搜索方向，避免盲目扩展节点，从而在保证最优解的同时减少内存占用。其核心特点是：
-
启发式函数：使用启发式函数 \(h(n)\) 估计从当前节点到目标节点的代价，结合已知代价 g(n)，计算总代价 \(f(n)=g(n)+h(n)\)。
-
迭代加深：设置一个代价阈值（threshold），只搜索\(f(n)\) 不超过阈值的节点。如果未找到目标，增加阈值并重新搜索。
-
深度优先搜索：在每次迭代中，IDA*使用深度优先搜索（DFS）来探索节点，减少内存占用。
算法步骤
1、初始化：
-
设置初始节点和目标节点。
-
计算初始节点的 \(f(n)=g(n)+h(n)\)，其中 \(g(n)\) 是从起点到当前节点的实际代价，\(h(n)\) 是启发式估计代价。
-
设置初始阈值（通常为初始节点的 \(f(n)\)）。
2、深度优先搜索：
-
使用DFS探索节点，但只扩展 f(n)≤ 当前阈值的节点。
-
如果找到目标节点，返回最优路径。
-
如果搜索受限（即 \(f(n)\) 超过阈值），记录超出阈值的最小 \(f(n)\) 值作为下一次迭代的候选阈值。
3、更新阈值：
-
如果未找到目标，更新阈值为上一步记录的最小超出值。
-
清空搜索栈，重新开始新一轮DFS。
4、重复：
- 重复步骤2和3，直到找到目标节点或确认无解。
例题_【洛谷】P2324 [SCOI2005] 骑士精神
题目分析
在 5×5 的棋盘上，有 12 个白色骑士（0）和 12 个黑色骑士（1），以及一个空位（）。骑士可以按照国际象棋规则移动（"日"字型移动），目标是通过最少的移动步数将棋盘变为特定目标状态，当步数超过15步时判定为-1无解。
解题思路
典型的A问题，但是A又不能完全解决问题，因为题目要求了15步内完成，所以本题使用IDA算法来解决。首先设置迭代加深，最大深度设置为15步，然后传入dfs中进行搜索，枚举8哥方向，生成新状态，利用A启发式搜索来剪枝，即设置启发式函数\(h(n)\)，判断剩余步骤内是否可能找到解，以此剪枝即可。
完整代码示例
#include<iostream>
#include<algorithm>
using namespace std;struct matrix{int a[7][7];
}start_state, goal_state;const int dx[8] = { 1, 1, -1, -1, 2, 2, -2, -2};
const int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};int stx, sty;
int success;void init_goal() {goal_state.a[1][1] = 1;goal_state.a[1][2] = 1;goal_state.a[1][3] = 1;goal_state.a[1][4] = 1;goal_state.a[1][5] = 1;goal_state.a[2][1] = 0;goal_state.a[2][2] = 1;goal_state.a[2][3] = 1;goal_state.a[2][4] = 1;goal_state.a[2][5] = 1;goal_state.a[3][1] = 0;goal_state.a[3][2] = 0;goal_state.a[3][3] = 2;goal_state.a[3][4] = 1;goal_state.a[3][5] = 1;goal_state.a[4][1] = 0;goal_state.a[4][2] = 0;goal_state.a[4][3] = 0;goal_state.a[4][4] = 0;goal_state.a[4][5] = 1;goal_state.a[5][1] = 0;goal_state.a[5][2] = 0;goal_state.a[5][3] = 0;goal_state.a[5][4] = 0;goal_state.a[5][5] = 0;
}int h(const matrix &mat) {int cnt = 0;for(int i = 1; i <= 5; i++) {for(int j = 1; j <= 5; j++) {if(mat.a[i][j] != goal_state.a[i][j]) {cnt++;//启发函数，用于判断当前状态中与目标函数位置不同的个数}}}return cnt;
}void dfs(int dep, int x, int y, int maxdep, matrix &mat) {if(dep == maxdep) {if(!h(mat)) {success = 1;}return;}//判断当前深度为迭代深度时，若达到目标状态，则标记成功并返回for(int i = 0; i < 8; i++) {//遍历8个方向int xx = x + dx[i];int yy = y + dy[i];if(x >= 1 && x <= 5 && y >= 1 && y <= 5){//判断下标合法swap(mat.a[x][y], mat.a[xx][yy]);// 交换位置//剪枝if(h(mat)+dep<=maxdep) {//启发函数小于最大深度，则说明可能有解 所以继续搜dfs(dep+1,xx,yy,maxdep,mat);}//由于我们在定启发函数时 预测步数一定≤实际所需步数，所以当出现预测步数已经下已经不合理了，那么实际步数一定不合理，所以无需再搜索。//swap(mat.a[x][y],mat.a[xx][yy]);//将位置复原if(success) {return;}//若以找到解 则直接返回，无需遍历下一个方向}}
}int main() {init_goal();//初始化目标矩阵int T;cin >> T;while(T--) {success = 0;//结果初始化for(int i = 1; i <= 5; i++) {for(int j = 1; j <= 5; j++) {char ch;cin >> ch;//输入初始状态if(ch == '*') {start_state.a[i][j] = 2;//空格位置的‘*’用2代替，将数组定义为int类型，便于后续使用stx = i;sty = j;} else {start_state.a[i][j] = ch - '0';}}}if(!h(start_state)) {cout << "0" << endl;continue;}//看初始状态与目标状态是否相同，是则无需继续 直接输出int flag=0;//标记是否找到解//迭代加深搜索，共15步for(int maxdep = 1; maxdep <= 15; maxdep++) {matrix temp = start_state;//将当前状态传入算法dfs(0, stx, sty, maxdep, temp);//四个参数分别为 深度，当前状态中空格的横坐标，纵坐标，最大深度（用于判断是否超过15步），以及当前状态if(success) {cout << maxdep << endl;flag=1;break;//若有解，则输出当前深度，即达到目标状态的所需步数，比标记flag为1}}if(flag==0)//若flag最终依然为0，则说明没有找到解，输出-1；cout << "-1" << endl;}return 0;
}