本人实力有限，这道题也是半靠题解，半靠自己写出来的，但看了题解其实和抄没什么区别(╥﹏╥)

所以这篇题解就不讲具体的代码实现了，因为官方的题解不是非常详细，所以写一点心得给初接触IDA*的萌新(比如我(´;ω;`))

默认读者了解dfs，不会的可以去恶补一下

首先，IDA*实际上是dfs的变种，dfs是很好实现的，但缺点也很明显，2MB的栈空间明显不够用啊！所以，存在两种针对dfs的优化方式，一种是剪枝，另一种就是限制递归深度，这里我们着重介绍限制递归深度的方法

迭代加深搜索

很多时候，dfs会爆栈的重要原因是——在一棵树上吊死，如果解不在那个分叉下，且数据规模比较大，就很容易爆栈，那其实我们可以结合一下广搜和深搜的优点，我们可以限制一个深度，深搜不准越过那个深度，转而搜索其他分叉,对应着题解的这一段

    if(g+h > maxdeep) {
        return false;
    }

平凡的迭代加深是从1开始，每次+1，爆栈的风险确实是大大降低了，但是效率明显很低，如何解决呢？答案是IDA*，IDA*增加了一个估值函数，判断最小深度大概是多少，即深度搜索的最低成本，这个值可以不用太精确，但分析时我们更加倾向于较大的那一个数，因为效率更高，不用频繁搜索，题解利用断点数来估值，其实也可以用不在原来位置上的数的个数，效率可能会有细微差别

离散化

离散化这一块，可能有些人摸不着头脑，但其实我们只要关注到断点数的统计，自然很容易知道

if(abs(state[i] - state[i+1]) != 1) {
            breakpoints++;
}

离散化的意义在于将可能间隔很大，但实际上是紧紧相连的数显性化（比如12，56，8790，6000，对于断点数来说，这和1，2，4，3没有本质上的区别）从而方便了程序的实现

dfs的细节

for(int k = 2;k<=n;k++) {
        if(k == prev_filp) continue;
        vector<int> next_state = filp(state,k);
        if(dfs(next_state,g+1,k)) {
            return true;
        }
    }

这一段是dfs的核心代码，有人可能对prev_filp不解，这里算是一个坑，不能连续反转一个位置多次，不仅无意义，还会陷入死循环，做反转类型的题目时尤其要注意

本篇严格来说并不是题解，而是对官方题解的补充说明，建议配合官方题解食用！