ida*
算法简介
ida*算法是对迭代加深搜索的优化，是dfs与估计函数的完美结合。避免了广度优先搜索算法占用搜索空间太大的缺点，也减少了深度优先搜索算法的盲目性。它通过设置一个搜索过程中的最大深度，当此状态距离目标状态超过此深度时，便不去搜索。这样便进行了剪枝。ida*的初始深度是起始状态到目标状态的估计距离。随着搜索深入调整这个最大深度值，但这个并不像迭代加深搜索每次只能加一，其增量视具体情况而定。ida总的来说省去了a\的判重时间和空间以及存储当前状态的堆，因此空间效率很高。
主要运用场合和思路
ida*算法就是基于迭代加深的a*算法。其最典型的应用就是八数码问题和十五数码问题。由于改成了深度优先的方式，与a*比起来，ida*更实用，其不需要判重，也不需要排序，并且空间需求减少。 ida*算法着重的部分就是：首先将初始状态节点的h值设为maxh，然后进行深度优先搜索，在搜索的过程中忽略所有h大于maxh的节点；如果没有找到最终的解，则加大这个maxh，再重复上述搜索过程，直到找到一个解。在保证h的计算满足a*算法的要求下，这样找到的解一定是最优的。
POJ 2286
题意：一个矩型的棋盘，上面有1、2、3各8个，要求通过8种操作使得最后中间的八个格子数字相同。
解题思路：ida*搜索，首先，每个格子有三种状态，总共有3^24种状态，即使通过1、2、3都只有8个排除一些内存也是不够的，相反，此题给了15s的时限，便可以用时间效率不如bfs，但是空间上完爆bfs的ida*了。
- 记录八种旋转的改变数组位置，然后在设定的depth范围内dfs。
- 两个剪枝：a)当前操作是上一次操作的逆操作。b)当前状态最好情况也无法在depth之内完成任务，即使中间8个格子中最多的数字在最好情况下凑成目标态也超过了depth。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int rot[8][7]=
{
0,2,6,11,15,20,22,//A
1,3,8,12,17,21,23,//B
10,9,8,7,6,5,4,//C
19,18,17,16,15,14,13,//D
23,21,17,12,8,3,1,//E
22,20,15,11,6,2,0,//F
13,14,15,16,17,18,19,//G
4,5,6,7,8,9,10//H
};
int res[]={5,4,7,6,1,0,3,2};
int depth;
bool check(char s[])
{
char ch=s[6];
for(int i=0;i<3;i++)
if(ch!=s[i+6]||ch!=s[15+i])
return false;
return ch==s[11]&&ch==s[12];
}
void rotate(int k,char s[])
{
char ch=s[rot[k][0]];
for(int i=0;i<6;i++)
s[rot[k][i]]=s[rot[k][i+1]];
s[rot[k][6]]=ch;
}
bool IDAstar(int k,char st[],char op[],int la)
{
int cnt[4];
cnt[1]=cnt[2]=cnt[3]=0;
for(int i=0;i<3;i++)
cnt[st[i+6]-'0']++,cnt[st[15+i]-'0']++;
cnt[st[11]-'0']++,cnt[st[12]-'0']++;
cnt[0]=max(max(cnt[1],cnt[2]),cnt[3]);
if(k+8-cnt[0]>=depth)
return false;
for(int i=0;i<8;i++)
{
if(la!=-1&&res[i]==la)
continue;
op[k]='A'+i;
rotate(i,st);
if(check(st))
{
op[k+1]='\0';
return true;
}
else if(IDAstar(k+1,st,op,i))
return true;
rotate(res[i],st);
}
return false;
}
int main()
{
char ch;
while(scanf(" %c",&ch),ch!='0')
{
char st[25];
st[0]=ch;
for(int i=1;i<24;i++)
scanf(" %c",&st[i]);
depth=1;
if(check(st))
{
printf("No moves needed\n%c\n",st[6]);
}
else
{
char op[200];
op[0]='\0';
while(!IDAstar(0,st,op,-1))
depth++;
printf("%s\n%c\n",op,st[6]);
}
}
return 0;
}
POJ 1077
比较典型的八数码问题
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
void initial(int *maze,int &space)
{
char grid;
for(int i=0; i<9; i++)
{
cin>>grid;
if(grid!='x')maze[i]=grid-'1'+1;
else
{
space=i;
maze[i]=9;
}
}
}
bool isResolve(int *maze,int space)
{
int s=abs(double(2-space/3))+abs(double(2-space%3));
for(int i=0; i<9; i++)
{
for(int j=0; j<i; j++)
{
if(maze[i]>maze[j])s++;
}
}
if(s&1)return false;
else return true;
}
int h(int *maze)
{
int h=0;
for(int i=0; i<9; i++)
{
if(maze[i]!=9) h+=abs(double((maze[i]-1)/3-i/3))+abs(double( (maze[i]-1)%3-i%3));
}
return h;
}
int next[9][4]=
{
{-1,3,1,-1},
{0,4,2,-1},
{1,5,-1,-1},
{-1,6,4,0},
{3,7,5,1},
{4,8,-1,2},
{-1,-1,7,3},
{6,-1,8,4},
{7,-1,-1,5}
};
bool isAns(int *maze)
{
for(int i=0; i<8; i++)if(maze[i+1]-maze[i]!=1)return false;
return true;
}
int pathLimit;
int path[362890],pathLen;
bool IDAStar(int *maze,int len,int space)
{
if(len==pathLimit)
{
if(isAns(maze))
{
pathLen=len;
return true;
}
return false;
}
for(int i=0; i<4; i++)
{
if(next[space][i]!=-1)
{
if(len>0&&abs(double(i-path[len-1]))==2)continue;//!!不考虑相反的方向
swap(maze[space],maze[next[space][i]]);
path[len]=i;
if(h(maze)+len<=pathLimit&&IDAStar(maze,len+1,next[space][i]))
return true;
swap(maze[space],maze[next[space][i]]);
}
}
return false;
}
char dir[4]= {'l','d','r','u'};
void output()
{
for(int i=0; i<pathLen; i++)
{
switch(path[i])
{
case 0:
cout<<'l';
break;
case 1:
cout<<'d';
break;
case 2:
cout<<'r';
break;
case 3:
cout<<'u';
}
}
}
int main()
{
int maze[9],space;
initial(maze,space);
pathLimit=h(maze);
if(isResolve(maze,space))
{
while(!IDAStar(maze,0,space))pathLimit++;
output();
}
else cout<<"unsolvable";
cout<<endl;
return 0;
}
hdu1043
跟上一道题目很类似，也是八数码问题，此问题还有一种解法就是康拓展开
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int MAXN=1000000;//最多是9!/2
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//康拖展开判重
// 0!1!2!3! 4! 5! 6! 7! 8! 9!
bool vis[MAXN];//标记
string path[MAXN];//记录路径
int cantor(int s[])//康拖展开求该序列的hash值
{
int sum=0;
for(int i=0;i<9;i++)
{
int num=0;
for(int j=i+1;j<9;j++)
if(s[j]<s[i])num++;
sum+=(num*fac[9-i-1]);
}
return sum+1;
}
struct Node
{
int s[9];
int loc;//“0”的位置
int status;//康拖展开的hash值
string path;//路径
};
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//u,d,l,r
char indexs[5]="durl";//和上面的要相反，因为是反向搜索
int aim=46234;//123456780对应的康拖展开的hash值
void bfs()
{
memset(vis,false,sizeof(vis));
Node cur,next;
for(int i=0;i<8;i++)cur.s[i]=i+1;
cur.s[8]=0;
cur.loc=8;
cur.status=aim;
cur.path="";
queue<Node>q;
q.push(cur);
path[aim]="";
while(!q.empty())
{
cur=q.front();
q.pop();
int x=cur.loc/3;
int y=cur.loc%3;
for(int i=0;i<4;i++)
{
int tx=x+move[i][0];
int ty=y+move[i][1];
if(tx<0||tx>2||ty<0||ty>2)continue;
next=cur;
next.loc=tx*3+ty;
next.s[cur.loc]=next.s[next.loc];
next.s[next.loc]=0;
next.status=cantor(next.s);
if(!vis[next.status])
{
vis[next.status]=true;
next.path=indexs[i]+next.path;
q.push(next);
path[next.status]=next.path;
}
}
}
}
int main()
{
char ch;
Node cur;
bfs();
while(cin>>ch)
{
if(ch=='x') {cur.s[0]=0;cur.loc=0;}
else cur.s[0]=ch-'0';
for(int i=1;i<9;i++)
{
cin>>ch;
if(ch=='x')
{
cur.s[i]=0;
cur.loc=i;
}
else cur.s[i]=ch-'0';
}
cur.status=cantor(cur.s);
if(vis[cur.status])
{
cout<<path[cur.status]<<endl;
}
else cout<<"unsolvable"<<endl;
}
return 0;
}