bfs
迭代加深
限制搜索深度的dfs，一种用dfs方式实现的，本质为bfs的算法
优点：相比bfs的去重，减少了空间复杂度
结构：
IDDFS(u,d) if d>设定深度 return else for each edge (u,v) IDDFS(v,d+1) return
A*
一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。
特点：估值函数
f(n) = g(n) + h(n)
算法中的距离估算值与实际值越接近，最终搜索速度越快。
其实bfs就是一种特殊的A*算法
IDA*
A*和IDDFS的结合
总深度（现深度+估值深度）优先，空间消耗少
实例：luogu-P1379
1//bfs
#include<cstdio> #include<cstdlib> #include<queue> #include<map> using namespace std; int s,ed=123804765; map <int,int> step; queue <int> q; int py[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int main() { scanf("%d",&s); step[s]=0; q.push(s); if(s==ed) { printf("0 "); return 0; } while(!q.empty() ) { int n=q.front() ,st=step[n]; q.pop() ; int cp[4][4],posx=0,posy=0; for(int i=3;i>0;i--) for(int j=3;j>0;j--) { cp[i][j]=n%10,n/=10; if(!cp[i][j]) posx=i,posy=j; } for(int i=0;i<4;i++) { int nx=posx+py[i][0],ny=posy+py[i][1]; if(!nx || !ny || nx>3 || ny>3) continue; swap(cp[posx][posy],cp[nx][ny]); n=0; for(int i=1;i<4;i++) for(int j=1;j<4;j++) n=(n<<1)+(n<<3)+cp[i][j]; if(!step.count(n) ) { step[n]=st+1,q.push(n) ; if(n==ed) { printf("%d ",step[n]); return 0; } } swap(cp[posx][posy],cp[nx][ny]); } } return 0; }
2//迭代加深
//本题的情况总数略大，无法申请int //只能用set/map //或者用迭代加深法，用dfs的形式实现bfs #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int t0; int s[4][4],ed[4][4]={ 0,0,0,0, 0,1,2,3, 0,8,0,4, 0,7,6,5 }; bool check() { for(int i=1;i<4;i++) for(int j=1;j<4;j++) if(s[i][j]!=ed[i][j]) return false; return true; } int bs=-1;//步数，即深度限制//开始为-1,因为第一步也需要验证 int py[4][2]={{0,1},{-1,0},{1,0},{0,-1}}; void IDDFS(int x,int y,int st,int pre)//迭代加深易错点：pre的记录！！！ { if(st>bs) return ; if(st==bs) if(check()) { printf("%d ",bs); exit(0); } else return ; for(int i=0;i<4;i++) { int nx=x+py[i][0]; int ny=y+py[i][1]; if(!nx || !ny || nx>3 || ny>3) continue; if(pre+i==3) continue;//左右，上下，就算重复 swap(s[nx][ny],s[x][y]); IDDFS(nx,ny,st+1,i); swap(s[nx][ny],s[x][y]); } } int main() { scanf("%d",&t0); int posx,posy; for(int i=8;i>=0;i--) { if(t0%10==0) posx=i/3+1,posy=i%3+1; s[i/3+1][i%3+1]=t0%10,t0/=10; } while(1) ++bs,IDDFS(posx,posy,0,-1); return 0; }
3//IDA*
int bs=-1;//步数，即深度限制//开始为-1,因为第一步也需要验证 bool esti(int stt)//这里的stt算是估的小了一个 { int cnt=0; for(int i=1;i<4;i++) for(int j=1;j<4;j++) if(s[i][j]!=ed[i][j]) cnt++; if(cnt+stt > bs) return false;//PAAAAAAAA //至今不知道为什么 else return true; } int py[4][2]={{0,1},{-1,0},{1,0},{0,-1}}; void IDDFS(int x,int y,int st,int pre)//迭代加深易错点：pre的记录！！！ { if(st>bs) return ; if(st==bs) if(check()) { printf("%d ",bs); exit(0); } else return ; for(int i=0;i<4;i++) { int nx=x+py[i][0]; int ny=y+py[i][1]; if(!nx || !ny || nx>3 || ny>3) continue; if(pre+i==3) continue;//左右，上下，就算重复 swap(s[nx][ny],s[x][y]); if(esti(st) ) IDDFS(nx,ny,st+1,i); swap(s[nx][ny],s[x][y]); } }
dfs
结构：
void f() { if(符合边界条件) { return; } f(); }
回溯法
void DFS(int 当前状态) { if(当前状态为边界状态) { 记录或输出 return; } for(i=0;i<n;i++) //横向遍历解答树所有子节点 { //扩展出一个子状态。 修改了全局变量 if(子状态满足约束条件) { dfs(子状态) } 恢复全局变量//回溯部分 } }
附加优化角度：
dfs:
顺序 对象
等效冗余
可行性 最优性
记忆化
bfs:
去重
双向宽搜
01图的deque搜索