IDDFS
某些问题搜索时可能会存在搜索很深却得不到最优解的情况。
设置一个深度约束，当搜索深度达到约束值却还没找到可行解时结束搜索。
如果我们在一个深度约束下没有搜索到答案，那么答案一定在更深的位置，把约束深度调整到更深，直到搜索到答案为止。
对当前的情况通过一个乐观估计函数进行预估，如果发现即使在最好的情况下搜索到当前的最深深度限制也没办法得到答案，就及时剪枝。
Bidirectional BFS
双向 BFS 就是用两个队列，一个队列保存从起点开始向后搜索的状态，另一个保存从终点开始向前搜索的状态，每个状态包含到达该状态的步数，两边相交时答案相加。
交替逐层扩展优化：由于两端扩展节点个数可能差别很大，所以每次选择节点个数少的队列进行扩展。
Deque BFS
双端队列 BFS：https://www.cnblogs.com/greyqz/p/11862967.html
A* search
定义一个估价函数 (f(x))，则 (f(x)=g(x)+h(x))。其中，(f(x)) 指我们估计答案的价值，而 (g(x)) 是实际值，(h(x)) 是我们的预测。
在 DFS 上加入一个判断：当 (g(x)+h(x)) 劣于较优解时剪枝。
一种具有 (f(x)=g(x)+h(x)) 策略的启发式算法能成为 A* 算法的充分条件是：
- 搜索树上存在着从起始点到终了点的最优路径。
- 问题域是有限的。
- 所有结点的子结点的搜索代价值 (>0)。
- (h(x) le h^ast (x)) （(h^ast (x)) 为实际问题的代价值）。
例：求 S 到 T 的第 K 短路。
思路：
(1) 将有向图的所有边反向，以原终点T为源点，求解T到所有点的最短距离。
(2) 新建一个优先队列，将源点S加入到队列中。
(3) 从优先级队列中弹出f(p)最小的点p，如果点p就是T，则计算T出队的次数。如果当前为T的第K次出队，则当前路径的长度就是S到T的第K短路的长度，算法结束；否则遍历与p相连的所有的边，将扩展出的到p的邻接点信息加入到优先队列。
— Z_Mendez
int head[1005], nex[100005], to[100005], w[100005]; // 正向前向星邻接表
int rhead[1005], rnex[100005], rto[100005], rw[100005]; // 反向前向星邻接表
int h[1005]; bool v[1005];
priority_queue<node> q; // 预处理 h(x) 用
struct star {
int t, g, f;
bool operator < (const star& A) const {return f>A.f || f==A.f && g>A.g; }
};
priority_queue<star> Q; // A* 用
// 读入数据时建立正反向邻接表
// 预处理 h(x), Dijkstra 算法
memset(h, 0x3f, sizeof h);
q.push((node) {T, h[T]=0});
while (!q.empty()) {
register node now=q.top(); q.pop();
if (v[now.t]) continue; v[now.t]=true;
for (int i=rhead[now.t]; i; i=rnex[i])
if (now.d+rw[i] < h[rto[i]])
h[rto[i]] = now.d + rw[i], q.push((node) {rto[i], h[rto[i]]});
}
// A*：启发式 Dijkstra 算法
if (S==T) ++K; // 不出家门不叫最短路
if (h[S]==0x3f3f3f3f) {printf("-1
"); return 0; } // 不存在答案
Q.push((star) {S, 0, h[S]});
register int cnt=0;
while (!Q.empty()) {
register star now=Q.top(); Q.pop();
if (now.t==T) if (++cnt>=K) {printf("%d
", ans=now.g); return 0; } // 找到答案即退出
for (int i=head[now.t]; i; i=nex[i])
Q.push((star) {to[i], now.g+w[i], now.g+w[i]+h[to[i]]});
}
printf("-1
"); // 找不到答案