Tag Archives: Algorithm

Sparse Table

ST表，全称 SparseTable，也叫做稀疏表。是用来解决区间和和区间最大最小值问题的一种工具。其实推广开来，其可以用来解决任何可重复贡献（associative）问题。 使用条件 可重复贡献问题 ST表要求其处理的问题必须具有“可重复贡献”这一特征。具体是什么意思呢？ 假设有操作F，使得其满足下列关系: 则称F符合可重复贡献问题的特征。 如图，不难发现max()最大值函数就符合可重复贡献问题的特征；读者可以自行验证，sum()，min()等函数都符合这个特征，这也证明了ST表可以解决最大最小值以及区间和等问题。 元数据可不能改变噢 在使用ST表解决问题时，我们必须确保所有的查询结束前，ST表所对应的元数据都不改变。 有些数据结构（比如线段树）在元数据更新之后（比如原来的数组中，某个数值由3变成了5），可以有对应的事件复杂度比较低的方法对结构进行更新，以达到一边更新一边查询的效果。ST表则无法提供类似的方法，所以确保你的问题中没有要求在查询期间动态调整元数据的要求。 SparseTable意义与使用 接下来，我们采用由表及里的过程，先了解ST表的意义以及使用方法，之后再来说明如何生成ST表。 一些准备——向下取整的Log2函数 由于SparseTable的特性，无论是根据数据生成ST表，还是得到ST表后对数据进行查询，都会比较频繁的用到向下取整的log2函数，所以特地说明。我们对于向下取整的log2运算稍加分析，可以得到log2(x)向下取整的具体意义是： 对于某一个数N，返回可能的最大的数字n，使得2的n次方小于等于N，且2的n+1次方必定大于N。 比如对于7，log2(7)向下取整为2，2的2次方不超过7，但可以保证2的3次方一定大于7（8>7）。 了解了这个之后，让我们来看看SparseTable如何快速解决规模庞大的可重复贡献问题吧~ ST表中数据的意义 我们接下来选择一个经典的可重复贡献问题——区间最大值问题，作为示例。 假设我们有一个数组 {3, 2, 1, 4, 5, 9, 7}, 其数据元素个数为7，要求必须在非常低的事件复杂度内，查询某个特定区间（比如从下标0到下标5）的最大值。此时，如果直接循环求解，会导致复杂度随着查询区间长度不断增高，这就是ST表登场的时候啦。 如上图，对数组进行处理之后，就可以得到下方的二维数组，也就是我们大名鼎鼎的SparseTable——ST表。那么问题来了，图中ST表中的数据，到底具有什么含义呢？ 首先需要知道的是，ST表正常情况下使用一个二维数组st[idx][pow]来储存。下面对这个二维数组每一个位置元素的意义做出解释： 例如，对于区间最大值问题，假设原数组为arr，处理后得到的ST表中，st[1][2] = 5，则说明：原数组，从下标为1开始，长度为2^2=4的区间内，最大值是5。 特定区间的查询 知道了ST表的数据的意义，我们就可以着手解决特定区间查询问题。 这里需要注意的是，虽然ST表可以解决不同的可重复贡献问题，但是其在面对不同的可重复贡献问题时，最优查询方式可能有一定的区别。接下来，我们先通过上方的“区间最大值”例子，介绍一下区间最值问题的ST表查询。 合适的长度 首先，为了降低时间复杂度，我们希望用尽可能少的区间查询来拼凑出完整答案。可以证明，在ST表处理区间最值问题时，无论区间长度位置，我们都可以用ST表支持的两个区间，拼接出答案。比如对于区间(1, 6)，可以由区间(1, 4)和区间(3, 6)区间的结果再求最值得到。对于“最值”问题，我们只需要保证选择的区间完整覆盖住所求区间，且不超过所求区间即可，而这多个区间允许有重复部分。 同时，为了保证所用区间尽可能少，每个区间就要尽可能大。这个时候，上方说到的log2向下取整计算就派上用场了。由于ST表代表的区间长度只能是2的n次方倍，所以，不超过区间范围的区间，其最长长度就是log(区间长度)向下取整。 比如对于(1,6)区间进行最值计算，log2(6)向下取整=2。说明只需要在合适的位置，用两个长度为2^2=4的区间覆盖即可。这代表了，我们要取的数据肯定在ST[idx][2]内——我们确定了pow。 合适的位置 我们已经知道了，只要位置安排合理，我们肯定能用两个长度为4的区间覆盖住(1, 6)，那么这两个区间的位置，应该如何选择呢？ 思考之后发现，我们肯定希望： 如上图，最终，我们可以得到： 我们对这两个区间的最大值再求一次最大值即可，最终答案为max(5, 9) = 9。 如果用ST表来计算，运算过程如下： 是时候该自己实现ST表啦Continue reading “Sparse Table”

Bellman Ford Shortest Path

开始之前 本Blog之前已经介绍过一种单源最短路算法——Dijkstra算法。但Dijkstra算法也有着自己的缺点，其中最明显的问题就是无法处理带负权边的图，其原因与其算法中包含的贪心原理有关。 而接下来介绍的算法，则拥有处理负权边的能力，该算法就是Bellman Ford单源最短路算法。该算法的核心思想是，对图中的每条边，都进行足够次数的Relaxation（松弛）操作，从而逐步推导出每个点距离出发点都最短路径长度。 关于Bellman Ford算法的原理和代码实现，网络中已有大量优秀的资料，这里便不再说明算法本身的详细工作流程。接下来着重说明一些Bellman Ford算法中一些限制条件，及其相关的一些理解。 Bellman Ford算法特性 当出现负权回路时… 在通过Bellman Ford算法计算单源最短路时，会要求所计算的图中不得存在权值为负值的回路。这个限制相对较好理解，下面举一个简单的例子。 如图，图中的A->B->C->A便是一个负权回路。而假设我们现在需要以A点作为出发点计算最短距离，请问A->D的最短距离应该是多少？不难发现这里出现了死循环。我们可以从原点出发，不停的走A->B->C->A这条路，每循环一次，我们距离出发点的距离就会越来越小。这也就意味着，只要我们的路径不断的在负权回路中重复足够多次，每一个点距离出发点的距离都可以认为是无穷小，这显然是不合理的。 负权回路对于图来说是存在特殊意义的，比如在经济学的部分领域中，“负权回路”是一个非常具有吸引力的词，因为可能代表着可持续的收益链，也可以代表着套利的机会，但Bellman Ford不认这些，在单元最短路算法的世界中，我们暂且不接受“套利机会”的存在。也就是说我们不允许待处理的图中出现负权回路，以此来保证计算结果是有意义的。 对于Bellman Ford算法的一些理解 迭代次数的理解 Bellman Ford算法的核心思想，在于每迭代一次，就对所有边进行遍历，并执行Relaxation操作。这里不难发现，迭代k次时，得到的结果，可以保证至少是路径条数为k时的最优解。 为什么说是至少呢，因为其遍历的结果可能跟边遍历的顺序有关，如下图： 如图，我们发现对于图中的无向图，如果从左边的边开始遍历，实际上遍历一次之后我们就已经得到了最优解。而如果从右边开始遍历，我们就需要遍历3次才能得到最优解。 按照这个思路理解，不难推出，遍历k次时，得到的答案，只能保证，至少是路径条数为k限制下的最优解。 这里对路径条数做出说明，一个路径由多个边组成，上方所说的“路径条数”，指的是对于某条路径，其经过的边的个数的和。 为什么迭代次数等于点的个数？ 上方我们已经论述了迭代次数k的意义，迭代k次时，得到的结果至少是路径条数k情况下的最优解，部分点的数据可能比会更优，但对于所有的点，只能保证其为路径条数k情况下的最优解。 那么我们到底需要迭代几次呢？根据定义，我们将问题转换成为：对于一个无向图，其某个点A到某个点B的全局最优路径中，最多可能经过几条边。 经过思考之后发现，最坏情况下，最优路径将会不重复的经过所有点。接下来对这个结论进行简单的说明： 首先是经过所有点。如果我们想要强迫最优路径经过尽可能多的点，最坏的情况之一，便是这个图形成了一个没有分叉的纯线性结构（就像上方对于迭代次数解释时所用图一样，每两个点用一条边链接，总边数为点数-1），这样从最左边到最右边的点，最优路径边毋庸置疑是经过所有的点。 其次是不重复。为什么我们可以确保最优路径中不会重复经过同一个点呢？这从某个角度上来说得益于算法前面的一个前提条件——不允许负权回路。想象一下，如果路径重复经过了同一个点，说明这个路径必定存在一段回路（从重复点出发，经过某个路径，又回到重复点）。而此时如果这个回路确定不是负权回路，那么说明如果跳过这段回路，我们可以得到一个权重更短的路径，反向说明了目前的路径不是最优路径。因而可以确定，如果一个路径被确定为最优路径，且该图中没有负权回路，那么这个路径绝对不会重复经过同一个点。 说明完毕，接下来让我们看看这两个结论，不难发现，不重复经过所有点，那么对于一个点个数为N的图，符合条件的路径，最长只能是N-1（因为一旦大于N-1，说明必定要产生回路，与条件冲突），所以最终确定，如果需要得到全局最优，其最少迭代次数为N-1。 综上所述，容易得到，算法的时间复杂度为O(N*M)。其中，N为点的个数，M为边的个数。 为什么它能攻克负权边？ 在Dijkstra算法的文章中，笔者提到了一个观点，Dijkstra的核心是基于贪心的，而贪心带来了局部最优解这一隐患。带着这个角度再来看Bellman Ford算法，是否有一种熟悉的感觉？Bellman Ford算法的每次迭代都基于上一次的迭代结果。先知道路径条数1情况下的最优解，再根据此状态推出条数2情况下的解，以此类推最终得到路径条数为N-1时的最优解（也就是全局最优解），是不是有点「动态规划」的味道了呢？正是借助这这种工作模式，不像Dijkstra算法一样看到一点点甜头就着急的把点Close掉，Bellman Ford拥有了不被眼前甜美假象迷惑的能力，坚持着自己的本分，不断想着正确的道路一步步迈进，最终终于得到了令人满意的结果。 相关链接 GeeksForGeeks Bellman Ford算法介绍（英文） 「编程笔记」Dijkstra算法为什么无法处理带有负权边的图

Why Dijkstra Can’t Deal with Negative Weight

前言 Dijkstra算法是一种可以计算有向或无向图中单源最短路的算法。其工作模式与图的BFS（广度优先遍历）有些相似，通过类似于广度遍历的方式，逐渐从某个设定好的起点向外推进，一步步的计算出所有点到该点的距离。 本文不过多介绍Dijkstra单源最短路算法本身，如果仍然没有掌握该算法，可以先自行了解该算法的工作模式。下面提供一些可供参考的资料： 知乎：通俗易懂理解——dijkstra算法求最短路径 负权边对于Dijkstra算法的影响 Dijkstra算法工作模式 要了解该影响，首先需要明确Dijkstra算法的工作模式。其维护两个点集合。一个是“仍未确定最优解的点（S）”，一个是“已经确定最优解的点（U）”。且有一个重点：在算法工作期间内，如果某点被认为已经得到最优解，则该点会被从S移动到U，可以认为，从此以后该点已经被Closed（关闭），即解已经确定，且不容被更改。 为了方便，我们称在S中的点为opening vertex，U中的点为closed vertex 当图中出现负权边… 了解这一点后，让我们来看看下面这个图片示例，看看当负权边出现在图中时，可能会对算法造成什么影响： 如上图，假设我们尝试使用Dijkstra算法，计算该图中各个点距离C点的距离。 图中，绿色的点为closed vertex，白色的点为opening vertex，点上方的方框代表该点的，实时更新的计算距离。 1：算法首先锁定C点，将C点到C点的距离标记为0，并认定为最优解，然后根据C点尝试更新与其相连的opening vertex的距离（这里为A，B点，得到更新后距离是为1和5）。 2：剩余的opening vertex中，A距离出发点（C点）最小，距离为1，故锁定A点，（注意：锁定A点说明算法认为A点的最优解就是1，且之后算法也不可能再次更新A点的距离值，因为A点已经为Closed状态了），同时，锁定A点之后，再次更新与A点相连的opening vertex的值（与A点相连的点有B和C，但因为C点为closed vertex，故仅仅尝试更新B点的值），计算得到B点最新距离为min(5, 1+(-10)) = -9 3：最后，锁定B点，算法计算完成。 上方便是Dijkstra算法在示例图中的运行步骤和结果。不难发现，算法对于A点的最短距离出现了计算失误：实际上，A点的最短距离走法并不是C->A (1)，而是C->B->A (-5)。 怎会如此？ 分析之后可以发现，Dijkstra算法的核心，就在于每次都选择S集合中距离最小的点，并将其锁定，再通过这个点进一步更新其他点的距离。但为什么Dijkstra认为S集合中目前距离最小的点就是最优解呢？有没有可能从其他的点出发可以得到更小的距离呢？ 比如在上述的示例图中，锁定C点后，算法认为A点的距离是1，B点的距离是5，所以A点的距离为1一定是最优解。那么有没有可能实际上1并不是C到A的最优解，我们通过B点走其他的路径最终可以得到更小的解呢？ 答案是，当边的权值非负时，不可能，当边的权值存在负值时，则有可能。 当权值非负时，B点已经离出发点有5点的距离，所以所有从出发点出发经B点的路径，其长度必定大于等于5，但是当权值存在负数的时候，这一点就无法确定，经过B点的路径如果后续经过负权边，其路径长度总和也有可能再次小于5，此时，我们就无法确定C->A的1距离一定是最优解了，因为我完全有可能经由B路径得到一条总距离小于1的路径到达A。 上方的论证可能并不全面和严谨，不能作为Dijkstra算法相关特性的严格证明，但对我们进一步理解Dijkstra算法有着一些帮助。 一些有趣的说法 不难发现，实际上Dijkstra算法的设计和「贪心」有着很大的联系，实际上在S集合中选点就是一种贪心的行为。而我们都知道贪心算法的局限性，就是在部分情况下，其可能陷入局部最优解。而我们可以认为，当Dijkstra遇上负权边，就导致了其中贪心部分陷入了局部最优解（只考虑眼前的最短边（比如在5和10两条边中毫不犹豫的选择5），而忽略了目前看似落后的边未来的长期收益（比如那条权值为10的边链接的点，接下来将经过一条绝对值非常大的负权边-10000之类的），这也警示我们不要贪图眼前的小利，眼光应当长远（雾 如果我就是想拿下负权边呢？ 噢亲爱的读者，相信我，不止你一个人有这种想法；实际上上百年前就已经有两名小伙想要拿下他，他们的名字分别是Richard Bellman 和Lester Ford Jr，接下来，就是Bellman Ford算法的表演时间了。 如果你对与这个Bellman Ford算法感兴趣，可以在互联网上找到很多关于这个算法的优质教程，其通过一次次迭代，对边进行Relaxation操作，实现了对于单源最短路径的求解，在本Blog的另外一篇文章「编程笔记」关于Bellman Ford单源最短路算法 中，也对这个算法做出了一些讨论，希望能对您产生一些帮助和启发。