把迭代加深理解错了 自己写了半天也没写对

所谓迭代加深，就是在深度无上限的情况下，先预估一个深度（尽量小）进行搜索，如果没有找到解，再逐步放大深度搜索。这种方法虽然会导致重复的遍历 某些结点，但是由于搜索的复杂度是呈指数级别增加的，所以对于下一层搜索，前面的工作可以忽略不计，因而不会导致时间上的亏空。

IDA*就是一个加了层数限制depth的DFS，超过了限制就不在搜索下去，如果在当前层数没有搜到目标状态，就加大层数限制depth，这里还只是一个IDA算法，并不是A*的。当然我们可以用A*的估计函数去剪枝，如果当前深度d+h()>depth的时候就可以不再搜索下去了，这样就是IDA*了。

具体 代码里有注释

 

1 #include 
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 int a[25]; 8 int p[8] = {
    6,7,8,11,12,15,16,17};//中间8个所对应的序号 9 int rev[8] = {
    5,4,7,6,1,0,3,2};//A-F B-E...反着移动10 int v,ans[110];11 int po[8][7] = {
    0,2,6,11,15,20,22,12             1,3,8,12,17,21,23,13             10,9,8,7,6,5,4,14             19,18,17,16,15,14,13,15             23,21,17,12,8,3,1,16             22,20,15,11,6,2,0,17             13,14,15,16,17,18,19,18             4,5,6,7,8,9,10};//8种操作的原始顺序 对应ABCDEFGH19 void change(int k)//操作一次的结果20 {21     int i,y = a[po[k][0]];22     for(i = 0 ; i < 6 ; i++)23     a[po[k][i]] = a[po[k][i+1]];24     a[po[k][6]] = y;25 }26 int fdep()//这个是简单的估计下还需要搜得层数 假如中间已经有5个相同的了 那最少还要移3次27 {28     int i,x[4] = {
    0,0,0,0};29     for(i = 0 ; i < 8 ; i++)30     x[a[p[i]]]++;31     int an=0;32     for(i = 1 ; i < 4 ; i++)33     an = max(an,x[i]);34     return 8-an;35 }36 int dfs(int depth)37 {38     int i,tt;39     for(i = 0 ; i < 8 ; i++)40     {41         change(i);//操作42         tt = fdep();43         if(tt==0)//已经到达目的解44         {45             ans[depth] = i;46             return 1;47         }48         if(depth+tt