笑枕晚风の小站

参考《算法竞赛进阶指南》、AcWing题库 IDA* 在上一节中我们提到, A∗A^{\ast}A∗ 算法本质上是带有估价函数的优先队列 BFSB F SBFS 算法。故 A∗A^{\ast}A∗ 算法有一个显而易见的缺点, 就是需要维护一个二叉堆 (优先队列) 来存储状态及其估价, 耗费空间较大, 并且对堆进行一次操作也要花费 O(log⁡N)\mathrm{O}(\log N)O(logN) 的时间。 我们也提到了 A∗A^{\ast}A∗ 算法的关键在于设计估价函数。既然估价函数与优先队列 BFS 结合可以产生 A∗A^{\ast}A∗ 算法, 那么估价函数能否与 DFS 结合呢? 当然, DFS 也有一个缺点, 就是一旦估价出现失误, 容易向下递归深入一个不能产生最优解的分支, 浪费许多时间。综合以上讨论, 我们最终选择把估价函数与迭代加深的 DFS 算法相结合。请读者回忆迭代加深 DFS 算法。该算法限定一个深度, 在不超过该深度的前提下执行 DFS, 若找不到解就扩大深度限制, 重新进行搜索。 我们设计一个估价函数, 估算从每个状态到目标状态需要的步数。当然, 与 A∗ ...

参考《算法竞赛进阶指南》、AcWing题库 A* 在探讨 A∗A^{\ast}A∗ 算法之前, 我们先来回顾一下优先队列 BFS 算法。该算法维护了一个优先队列 (二叉堆), 不断从堆中取出 “当前代价最小” 的状态 (堆顶) 进行扩展。每个状态第一次从堆中被取出时, 就得到了从初态到该状态的最小代价。 如果给定一个 “目标状态”, 需要求出从初态到目标状态的最小代价, 那么优先队列 BFS 的这个 “优先策略” 显然是不完善的。一个状态的当前代价最小, 只能说明从起始状态到该状态的代价很小, 而在未来的搜索中, 从该状态到目标状态可能会花费很大的代价。另外一些状态虽然当前代价略大, 但是未来到目标状态的代价可能会很小, 于是从起始状态到目标状态的总代价反而更优。优先队列 BFS 会优先选择前者的分支, 导致求出最优解的搜索量增大。比如在优先队列 BFS 的示意图中, 产生最优解的搜索路径 (5+2+1)(5+2+1)(5+2+1) 的后半部分就很晩才得以扩展。 为了提高搜索效率, 我们很自然地想到, 可以对未来可能产生的代价进行预估。详细地讲, 我们设计一个 “估价函数”, 以任 ...

参考《算法竞赛进阶指南》、AcWing题库 双端队列BFS 在最基本的广度优先搜索中, 每次沿着分支的扩展都记为 “一步”, 我们通过逐层搜索, 解决了求从起始状态到每个状态的最少步数的问题。这其实等价于在一张边权均为 1 的图上执行广度优先遍历, 求出每个点相对于起点的最短距离 (层次)。在树与图的遍历中我们曾讨论过这个问题, 并得到了 “队列中的状态的层数满足两段性和单调性” 的结论。从而我们可以知道, 每个状态在第一次被访问并入队时, 计算出的步数即为所求。 然而, 如果图上的边权不全是 1 呢? 换句话说, 如果每次扩展都有各自不同的 “代价", 我们想求出起始状态到每个状态的最小代价, 应该怎么办呢? 我们不妨先来讨论图上的边权要么是 1、要么是 0 的情况。 175. 电路维修 题目描述 达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。 翰翰的家里有一辆飞行车。 有一天飞行车的电路板突然出现了故障，导致无法启动。 电路板的整体结构是一个 RRR 行 CCC 列的网格（R,C≤500R,C≤500R,C≤500） ...

参考《算法竞赛进阶指南》、AcWing题库 剪枝 剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故被称为 “剪枝”。在深度优先搜索中，有以下几类常见的剪枝方法： 优化搜索顺序： 在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。优先搜索分支较少的节点。例如： (1) 在上一节的“小猫爬山”问题中，把小猫按照重量递减的顺序进行搜索。 (2) 在上一节的“Sudoku" 问题中，优先搜索“能填的合法数字“最少的位置。 排除等效冗余 在搜索过程中, 如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的, 那么只需要对其中的一条分支执行搜索。我们会在 “Sticks" 问题中看到该剪枝的应用。 另外, 就如我们在 “Sudoku” 问题中提出的, 一定要避免重叠、 混淆 “层次”与 “分支”, 避免遍历若干棵覆盖同一状态空间的等效搜索树。 可行性剪枝 在搜索过程中, 及时对当前状态进行检查, 如果发现分支已经无法到达递 ...

参考《算法竞赛进阶指南》、AcWing题库 深度优先搜索 深度优先搜索 (DFS, Depth First Search), 顾名思义, 就是按照深度优先的顺序对 “问题状态空间” 进行搜索的算法。在基本算法中, 我们多次把一个问题的求解看作对问题状态空间的遍历与映射。我们可以进一步把 “问题空间” 类比为一张图, 其中的状态类比为节点, 状态之间的联系与可达性就用图中的边来表示, 那么使用深度优先搜索算法求解问题, 就相当于在一张图上进行深度优先遍历。 深度优先搜索与 “递归” 和 “栈” 密切相关。我们倾向于认为 “递归” 是与递推相对的一种单纯的遍历方法, 除了搜索之外, 还有许多算法都可以用递归实现。而 “深搜” 是一类包括遍历形式、状态记录与检索、剪枝优化等算法整体设计的统称。 在研究深度优先搜索算法之前, 我们先来定义该过程产生的 “搜索树” 结构。在对图进行深度优先遍历处于点 xxx 时, 对于某些边 (x,y)(x, y)(x,y) , yyy 是一个尚未访问过的节点, 程序从 xxx 成功进入了更深层的对 yyy 的递归; 对于另外的一些边 (x,y)(x, y ...

参考《算法竞赛进阶指南》、AcWing题库 树与图最常见的存储方式就是使用一个邻接表保存它们的边集。除非特殊声明, 默认给定 NNN 个点的树或图时, 其节点编号均为 1∼N1 \sim N1∼N, 无向图中的边看作成对出现的双向边, 树看作一张具有 N−1N-1N−1 条边的无向图, 它们的边都存 储在一个邻接表中, 邻接表以 head 数组为表头, 使用 ver 和 edge 数组分别存储边的终点和权值, 使用 next 数组模拟链表指针 (就像我们在链表与邻接表中讲解邻接表时所给出的代码那样)。 树与图的深度优先遍历, 树的 DFS 序、深度和重心 深度优先遍历 深度优先遍历, 就是在每个点 xxx 上面对多条分支时, 任意选一条边走下去, 执行递归, 直至回溯到点 xxx 后, 再考虑走向其他的边, 如下图所示。 根据上面提到的存储方式，我们可以采用下面的代码，调用 dfs(1)\mathrm{dfs}(1)dfs(1), 对一 张图进行深度优先遍历。 123456789// 深度优先遍历框架void dfs(int x) { v[x] = 1; //记录点x被 ...

参考《算法竞赛进阶指南》、AcWing题库 广度优先搜索 在树与图的遍历中, 我们介绍了图的广度优先遍历, 在深度优先搜索节中, 我们又定义了深度优先搜索过程产生的 “搜索树” 结构。如果我们把问题状态空间类比成一张图, 那么广度优先搜索就相当于对这张图的广度优先遍历。类似地, 我们依然借助一个队列来实现广度优先搜索, 起初, 队列中仅包含起始状态。在广度优先搜索的过程中, 我们不断从队头取出状态, 对于该状态面临的所有分支, 把沿着每条分支到达的下一个状态 (如果尚未访问过或者能够被更新成更优的解) 插入队尾。重复执行上述过程直到队列为空。 172. 立体推箱子（走地图） 题目描述 立体推箱子是一个风靡世界的小游戏。 游戏地图是一个 NNN 行 MMM 列的矩阵，每个位置可能是硬地（用 . 表示）、易碎地面（用 E 表示）、禁地（用 # 表示）、起点（用 X 表示）或终点（用 O 表示）。 你的任务是操作一个 1×1×21×1×21×1×2 的长方体。 这个长方体在地面上有两种放置形式，“立”在地面上（1×11×11×1 的面接触地面）或者“躺”在地面上（1×21×21×2 的面 ...

参考《算法竞赛进阶指南》、AcWing题库 在上一节末尾我们给出了动态规划的一个经典模型 F[i]=min⁡L(i)≤j≤R(i){F[j]+F[i]=\min _{L(i) \leq j \leq R(i)}\{F[j]+F[i]=minL(i)≤j≤R(i)​{F[j]+ val⁡(i,j)}\operatorname{val}(i, j)\}val(i,j)}, 并总结了单调队列优化的基本条件一一多项式 val⁡(i,j)\operatorname{val}(i, j)val(i,j) 的每一项仅与 iii 和 jjj 中的一个有关。在本节中, 我们将讨论多项式 val⁡(i,j)\operatorname{val}(i, j)val(i,j) 包含 i,ji, ji,j 的乘积项, 即存在一个同时与 iii 和 jjj 有关的部分时, 该如何进行优化。 300. 任务安排1 题目描述 有 NNN 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。 机器会把这 NNN 个任务分成若干批，每一批包含连续的若干个任务。 从时刻 000 开始，任务被分批加工，执行第 ii ...

参考《算法竞赛进阶指南》、AcWing题库 单调队列优化DP “单调栈” 和 “单调队列” 这两种思想的本质都是借助单调性, 及时排除不可能的决策, 保持候选集合的高度有效性和秩序性。仔细回顾 “最大子序和” 这道例题, 该问题的答案可以形式化表述为: ans=max⁡1≤i≤N{S[i]−min⁡i−M≤j≤i−1{S[j]}}a n s=\max _{1 \leq i \leq N}\left\{S[i]-\min _{i-M \leq j \leq i-1}\{S[j]\}\right\} ans=1≤i≤Nmax​{S[i]−i−M≤j≤i−1min​{S[j]}} 此处的 iii 非常类似于动态规划的 “状态”, jjj 则类似于动态规划的 “决策”。我们从小到大枚举每个 i∈[1,N]i \in[1, N]i∈[1,N], 当 iii 增大 1 时, jjj 的取值范围 [i−M,i−1][i-M, i-1][i−M,i−1] 的上、下界同时增大 1 , 变为 [i−M+1,i][i-M+1, i][i−M+1,i] 。这意味着不仅有一个新的决策 j=ij=ij=i 进 ...

参考《算法竞赛进阶指南》、AcWing题库 队列 队列是一种 “先进先出” 的线性数据结构。一般来讲, 元素从右端进入队列 (入队), 从左端离开队列 (出队)。于是我们称队列的左端为队头, 右端为队尾。可以在 C++\mathrm{C}++C++ 中用一个数组和两个变量 (记录队头和队尾的位置) 来实现队列结构。 元素进行多次入队、出队后, 用于实现队列结构的数组的开头部分空间就会被严重浪费, 所以我们经常将其优化为 “循环队列”, 也就是把队列看作一个首尾相接的环, 只要队列中的元素个数在任意时刻都不超过环长, 那么随着入队和出队操作的进行, 存储元素的那一段位置就像沿着环不停地移动, 重复利用着历史上曾被占用过的空间。 C++ STL 中的 queue 就是一个循环队列, 也是我们在代码中最常见的队列实现方式。 队列还有很多变体。例如两端都能插入或取出元素的双端队列 (C++ STL deque), 给每个元素附带一个评估值、出队时取出估值最大的、等价于一个二叉堆的优先队列 (C++STL priority_queue)。队列也是实现广度优先搜索的基本结构。 132. 小组 ...