把迭代加深理解错了 自己写了半天也没写对
所谓迭代加深，就是在深度无上限的情况下，先预估一个深度（尽量小）进行搜索，如果没有找到解，再逐步放大深度搜索。这种方法虽然会导致重复的遍历 某些结点，但是由于搜索的复杂度是呈指数级别增加的，所以对于下一层搜索，前面的工作可以忽略不计，因而不会导致时间上的亏空。
IDA*就是一个加了层数限制depth的DFS，超过了限制就不在搜索下去，如果在当前层数没有搜到目标状态，就加大层数限制depth，这里还只是一个IDA算法，并不是A*的。当然我们可以用A*的估计函数去剪枝，如果当前深度d+h()>depth的时候就可以不再搜索下去了，这样就是IDA*了。
具体 代码里有注释
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int a[];
int p[] = {,,,,,,,};//中间8个所对应的序号
int rev[] = {,,,,,,,};//A-F B-E...反着移动
int v,ans[];
int po[][] = {,,,,,,,
,,,,,,,
,,,,,,,
,,,,,,,
,,,,,,,
,,,,,,,
,,,,,,,
,,,,,,};//8种操作的原始顺序 对应ABCDEFGH
void change(int k)//操作一次的结果
{
int i,y = a[po[k][]];
for(i = ; i < ; i++)
a[po[k][i]] = a[po[k][i+]];
a[po[k][]] = y;
}
int fdep()//这个是简单的估计下还需要搜得层数 假如中间已经有5个相同的了 那最少还要移3次
{
int i,x[] = {,,,};
for(i = ; i < ; i++)
x[a[p[i]]]++;
int an=;
for(i = ; i < ; i++)
an = max(an,x[i]);
return -an;
}
int dfs(int depth)
{
int i,tt;
for(i = ; i < ; i++)
{
change(i);//操作
tt = fdep();
if(tt==)//已经到达目的解
{
ans[depth] = i;
return ;
}
if(depth+tt<v)//如果没有超过层数限制
{
ans[depth] = i;
if(dfs(depth+))
return ;
}
change(rev[i]);//撤销操作
}
return ;
}
int main()
{
int i;
while(scanf("%d",&a[])&&a[])
{
for(i = ; i < ; i++)
scanf("%d",&a[i]);
if(fdep()==)
{
puts("No moves needed");
printf("%d\n",a[]);//这里不要忘了输出
continue;
}
v = ;
while(!dfs())
{
v++;
}
for(i = ; i < v ; i++)
printf("%c",ans[i]+'A');
puts("");
printf("%d\n",a[]);
}
return ;
}