搜索 - AcWing

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

搜索

作者：

生在逢时 , 2022-06-28 19:31:19 , 所有人可见 , 阅读 255

1

2

bfs

5、双端队列搜索

175.电路维修 https://www.acwing.com/problem/content/description/177/
作者：小呆呆 (要求及删)
与堆优化Dijkstra 一样，必须在出队时才知道每个点最终的最小值，而和一般的bfs不一样，原因是如下图所示

6、BFS + 优先队列优化

P3956 [NOIP2017 普及组] 棋盘 https://www.luogu.com.cn/problem/P3956

为什么经典的走迷宫模型可以直接普通队列 BFS ？

不难得出：在这样的 BFS 中，每一次扩展的代价都相等且为正数，后进入队列的状态一定不如先进入队列的状态优（先进入队列的状态的代价 ≤ 后进入队列的状态的代价）。

基于这样的单调性，我们可以得出：第一次访问到某一个状态时，一定是这个状态的最优情况。

这是一个贪心思想。我们把这种思想应用到更具有普遍性的情况中：代价不一定相等。

优先队列( Dijkstra )
我们只要满足每一次都从状态队列中取出最小代价的状态，即可满足第一次访问最优性。优先队列可以实现这种操作。时间复杂度 O(nlogn) 。

7、双向BFS

190.字串变换 https://www.acwing.com/problem/content/192/
*不能每次扩展一个点交替搜索(每次扩展一层)

8、A*

178.第K短路 https://www.acwing.com/problem/content/180/
179.八数码 https://www.acwing.com/problem/content/description/181/

/*
A* 应用场景:
起点→终点的最短距离
状态空间 >> 1e10 
启发函数减小搜索空间

A*算法:
while(q.size())
    t ← 优先队列的队头  小根堆
        当终点第一次出队时 break;
        从起点到当前点的真实距离 d_real
        从当前点到终点的估计距离 d_estimate
        选择一个估计距离最小的点 min(d_estimate)
    for j in ne[t]:
        将邻边入队

A*算法条件:
估计距离<=真实距离
d[state] + f[state] = 起点到state的真实距离 + state到终点的估计距离=估计距离
                                                                       ^
d[state] + g[state] = 起点到state的真实距离 + state到终点的真实距离=真实距离

一定是有解才有 d[i]   >= d[最优] = d[u]+f[u]
        f[u] >= 0

证明终点第一次出队列即最优解

    1 假设终点第一次出队列时不是最优 
      则说明当前队列中存在点u
         有 d[估计]< d[真实]
      d[u] + f[u] <= d[u] + g[u] = d[队头终点]
      即队列中存在比d[终点]小的值,
    2 但我们维护的是一个小根堆,没有比d[队头终点]小的d[u],矛盾

    证毕

A* 不用判重
以边权都为1为例
  A o→o→o
    ↑   ↓
  S o→o→o→o→o→o→o T
      B
dist[A] = dist[S]+1 + f[A] = 7
dist[B] = dist[S]+1 + f[B] = 5
则会优先从B这条路走到T
B走到T后再从A这条路走到T

作者：仅存老实人
链接：https://www.acwing.com/solution/content/21233/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。