双向搜索
这种优化可以显著降低时间空间复杂度，分为两类：
双向宽搜
相当于同时从起点和终点跑普通宽搜，两边各自扩展自己的层级。关键是要实时检查两边探索到的状态是否有交集，一旦发现交集状态就说明找到了连接路径，可以立即停止。
双向深搜
主要解决状态空间巨大的问题。思路是：
- 把问题状态空间分成两半
- 对每半单独跑DFS搜索
- 把所有合法答案分别存入两个数组
- 最后用二分查找/双指针拼出最终答案
A*算法
这是启发式的智能搜索，核心在于它的估价函数：
如果去掉估价函数 \(h(n)\)，它就退化成了普通的Dijkstra
算法运行时同时考虑：
1.从起点到当前的实际代价 \(g(n)\)
2.到目标的预估代价 \(h(n)\)
优先扩展 \(f(n) = g(n) + h(n)\) 最小的状态
为什么高效？
普通搜索是"盲目"的，而好的估价函数像指路明灯，引导算法避开死胡同直奔目标。注意 \(h(n)\)必须是乐观估计才能保证找到最优解
迭代加深搜索
专门解决这种困境：答案可能在浅层，但错误分支又深又长
核心操作：
1. 先限制深度跑DFS
2. 如果没找到答案，深度+1
3. 重新开始DFS
循环直到找到答案
优势：
像宽搜一样能找到最浅解
像深搜一样省内存
避免陷在错误分支做无用功
代价：
浅层节点会被重复搜索，但这点额外开销通常是值得的
附上模板代码
双向dfs：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200000005;
int g[70],ans=-1e9,n,w,k,cnt,a[N],half;
void dfs1(int x,int t){if(x==half){a[++cnt]=t;return;}dfs1(x+1,t);if(t+g[x]<=w){dfs1(x+1,t+g[x]);}
}
void sovle(int val){int l=1,r=cnt;int ww=w-val;while(l<r){int mid=(l+r+1)>>1;if(a[mid]<=ww){l=mid;}else{r=mid-1;}}ans=max(a[l]+val,ans);
}
void dfs2(int x,int t){if(x==n+1){sovle(t);return;}dfs2(x+1,t);if(t+g[x]<=w){dfs2(x+1,t+g[x]);}
}
signed main(){cin>>w>>n;for(int i=1;i<=n;i++){cin>>g[i];} sort(g+1,g+n+1,greater<int>());half=(n>>1)+3;dfs1(1,0);sort(a+1,a+cnt+1);cnt=unique(a+1,a+cnt+1)-(a+1); dfs2(half,0); cout<<ans;return 0;
}双向宽搜
#include <bits/stdc++.h>
using namespace std;
int s,e=123804765;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<int>q;
map<int,int>vis;
map<int,int>ans;
int a[100][100];
int main(){cin>>s;if(s==e){cout<<0;return 0;}q.push(s);q.push(e);vis[s]=1;vis[e]=2;ans[s]=0;ans[e]=1;while(!q.empty()){int fx,fy; int front,end=q.front();q.pop();front=end; for(int i=3;i>=1;i--){for(int j=3;j>=1;j--){a[i][j]=front%10,front/=10;if(a[i][j]==0) fx=i,fy=j;}}for(int i=0;i<4;i++){int xx=fx+dx[i];int yy=fy+dy[i];if(xx>=1&&xx<=3&&yy>=1&&yy<=3){swap(a[fx][fy],a[xx][yy]);front=0;for(int j=1;j<=3;j++){for(int k=1;k<=3;k++){front=front*10+a[j][k];}}if(vis[front]==vis[end]){swap(a[fx][fy],a[xx][yy]);continue;}if(vis[front]+vis[end]==3){cout<<ans[front]+ans[end]<<"\n";return 0;}ans[front]=ans[end]+1;vis[front]=vis[end];q.push(front);swap(a[fx][fy],a[xx][yy]);} }} return 0;
}迭代加深
#include <bits/stdc++.h>
using namespace std;
int mapp[10][10];
int t,sx,sy;
int dx[8]={-2,-2,-1,1,-1,1,2,2};
int dy[8]={-1,1,2, 2,-2,-2,-1,1};
int to[20][20]={{0,0,0,0,0,0},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,2,1,1},{0,0,0,0,0,1},{0,0,0,0,0,0},
};
int pd(){int sum=0;for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){if(mapp[i][j]!=to[i][j]){sum++; }}} return sum;
}
bool fl;
void dfs(int k,int x,int y,int dep,int last){if(k==dep+1){if(pd()==0){fl=1;}return;} for(int i=0;i<8;i++){if(i==7-last) continue;int xx=x+dx[i];int yy=y+dy[i];if(xx<1||yy<1||xx>5||yy>5) continue;swap(mapp[xx][yy],mapp[x][y]);if(k+(pd()+1)/2<=dep){dfs(k+1,xx,yy,dep,i);}swap(mapp[xx][yy],mapp[x][y]);}
}
int main(){cin>>t;char ch;while(t--){memset(mapp,0,sizeof(mapp));fl=0;for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){cin>>ch;if(ch=='*'){mapp[i][j]=2; sx=i,sy=j;}else{mapp[i][j]=ch-'0';}}}if(pd()==0){cout<<"0\n";continue; } for(int i=1;i<=15;i++){dfs(1,sx,sy,i,-1);if(fl){cout<<i<<"\n"; break; } } if(!fl){cout<<"-1\n";}}return 0;
}