JONY

数据结构的扩张

数据结构的扩张 由于数据结构理论已经很成熟，标准数据结构在性能与抽象上往往没有太大改动空间。所以在需要更多功能的数据结构时，往往只需找到相关的标准数据结构作为基础，然后在其上存储额外变量、构造额外运算。这样的流程就称为“数据结构的扩张”，数据结构的扩张往往不是一个单纯的数据结构与算法的问题，其还包含了一定的程序设计、面向对象设计方面的考量。下文将以广泛作为标准结构的红黑树为例，研究2种红黑树的扩张。数据结构的扩张可分为如下步骤： 1) 根据问题选择标准数据结构作为基础结构； 2) 确定基础结构上需额外维护的附加信息； 3) 验证基础结构上的运算能否维护附加信息； 4) 构造新的运算； 下面是之前写过的红黑树代码，用它作为面向对象编程的父类/基类，之后会用面向对象的继承来实现红黑树的扩张。 Python class Nil:… 阅读全文

数据结构的持久化

可持久化数据结构 可持久化数据结构上的运算在修改自身时(比如插入、删除这样的运算)，会先记录一个改变前的状态作为历史版本，这个历史版本往往是可继续查阅和修改的。可持久化数据结构按“持久化程度”可分2大类： 1) 部分持久化数据结构：所有历史版本都可供查询，但只能基于最新版本修改数据； 2) 完全可持久化数据结构：所有历史版本都可查询修改； 通常来说设计可持久化数据结构的主要思想是“拷贝部分原有内容+复用部分原有内容”。所以可持久化数据结构的空间复杂度会介于“非可持久化数据结构”和“每次修改前完整克隆当前版本”这两种情况之间。下面就来讨论如何基于Treap构建可持久化的平衡树，这里需要引入一个称为无旋Treap的数据结构，因为“可持久化+旋转”比较难一起处理。   无旋Treap  (a)   (b)… 阅读全文

带权无向连通图的最小生成树

最小生成树网络是边有权重的无向连通图，最小生成树(MST)通常指无负权边的网络中，总边权和最小的生成树。MST有许多实际应用，如“已知任意城市间的距离，用总距离最短的公路连通所有城市”、“用最少长度的导线短接电路板的若干个点”。求MST的一般算法是Kruskal算法与Prim算法，其都为典型的贪心算法。给出几个较直观的引理： 1）包含网络全部顶点的无环连通图是该图的生成树 2）生成树的边数是顶点数-1。 3）生成树添加任意一条边后必然形成环。 4）若一个网络仅包含一个环，删除环上任意一边可得该网络的生成树。   Kruskal算法（并查集优化） 算法逻辑流程如下： 1）初始化含网络G所有顶点，但无边的子图G’，此时顶点就是连通分量。 2）从G中找权值最小（先把边权排序记录），且可连接G’某两个连通分量的边，将该边取出加入G’。… 阅读全文

带权有向图的单源最短路径

单源最短路径单源最短路：对有向图\(G=(V,E)\)，边权\(w(E)\)，源点\(s \in V\)。求\(s\)到\(V\)任意顶点的最短路。 最优子结构：若\(s-a-…-b-t\)为\(s\)到\(t\)的一个最短路，则上述\(a-…-b\)必为\(a\)到\(b\)的一个最短路。 负权环路：求最短路时需考虑边权函数\(w(E)\)为负值时的一般化情景。若\(s\)到\(v\)的所有路径中存在负权重环路，由于可在环路上任意的刷低权重所以\(\delta(s,v)=-\infty\)。但本文将讨论的算法并不会去处理这种情况，只能接收从原点到目标点的所有路径中不存在负权重环路的图。本文认为这种情况下的最短路无意义。 一般环路：负权环路的情况已经被排除，正权环路显然不可能出现在任何最短路径的结果中。最后剩下0权重环路情况，若其出现在某个最短路径中出现0权重环路，那么必然可以从该最短路径中“删去”环路得到同样权重的路径。综上可以认为求所有路径中的最短路径可以转化为求所有无环路径中的最短路径。… 阅读全文

差分约束问题的单源最短路解法

线性规划与差分约束一般形式的线性规划问题可用矩阵来表述，而差分约束为线性规划的特例，其可用有向图表示。给出相关定义： 1) 线性规划：给定\(m\times n\)矩阵\(A\)、\(m\)维向量\(b\)、\(n\)维向量\(c\)。求在\(Ax \leq b\)约束下使\(\sum  c_ix_i\)取最大值的\(n\)维向量\(x\)； 2) 差分约束：若矩阵\(A\)每行是仅有1个-1、仅有1个1、其余都为0的，且\(x\)仅需满足\(Ax \leq b\)约束即可； 3) 差分约束图：用有向图\(G\)的边\((v_i,v_j)\)与权重\(w(v_i,v_j)\)表示\(x_j – x_i \leq w(v_i,v_j)\)，则\(G\)可表示给定差分约束，再在\(G\)加入\(v_0\)顶点得到\(G’\)，规定\(v_0\)仅有直达其他所有顶点的0权重边。\(G’\)为差分约束图，\(G’\)与\(G\)的解等价；… 阅读全文

带权有向图的全源最短路径

全源最短路径 全源最短路径问题是指给定带权有向图，求任意两点\(u,v\)从\(u\)到\(v\)的最短路径”。可把该问题直接作为\(|V|\)个单源最短路径问题，使用Dijkstra算法(二叉堆)的代价为\(O(|V||E|lg|V|)\)，Bellman-Ford算法的代价为\(O(|V|^2|E|)\)，对于稠密图二者的代价可分别写成\(O(|V|^{3}lg|V|)\)与\(O(|V|^4)\)。本文将讨论专门用于解决全源最短路问题的算法，这些算法大多基于邻接矩阵讨论，且不允许存在任何负权环路的。下面给出相关定义： 1) 带权邻接矩阵：带权有向图\(G=(V,E)\)与其权重可被\(|V|\times |V|\)的矩阵\(W\)描述。其中\(W_{ij}\)表示图边\((i,j)\)的权重，并且当\(i=j\)时有\(W_{ij}=0\)，当图边\((i,j)\)不存在时有\(W_{ij}=\infty\)；… 阅读全文

流网络的最大流与最小割

流网络1) 流网络是附加了条件的带权重(容量)的有向图\(G=(V,E)\)，其附加条件与附加定义如下： 源与汇：给定\(G\)的同时需给定源\(s\)与汇\(t\)两个特殊顶点； 边与容量：给定\(G\)的边\((u,v)\)的同时需给定边容量\(c(u,v) > 0\)，并且边集必须满足： i. 不允许反向边(若\((u,v)\in E\)则\((v,u)\notin E\))； ii. \(s\)仅有入边且\(t\)仅有出边； iii. 任意\(v \in V-\{s,t\}\)从\(s\)可达\(v\)且从\(v\)可达\(t\)； iv. 除\(s\)以外每个顶点至少有一条入边故\(|E| \geq |V| – 1\)； 2) 流是函数\(\{ f(u,v) | (u,v)\in E \}\)，流可定义于流网络与残存网络。其附加条件与附加定义如下：… 阅读全文

比较排序（未完成）

比较排序排序算法(sorting)是一类非常重要的基础算法，高德纳在其著作《计算机程序设计艺术》的第3卷专门讨论排序与查找。排序算法一般被分为比较排序(comparison sort)与非比较排序两类来研究，其中比较排序是通过两两比较元素最终得到排序的算法。在设计实际应用的排序算法时通常会关注如下特性： 1）稳定性：比较结果相等的元素能够保持原本的次序； 2）原地性(in-place)：能够在原数据结构上完成排序而不是创建新数据结构存储排序结果；     对于实际应用中的比较排序程序，会根据问题规模选择算法、根据内存限制考虑利用外存、做并行计算(排序网络)等，这里不考虑。排序算法通常会尽量满足如下特性： 1）稳定：相等的元素维持原来的次序； 2）原地排序：在原存储结构（比如数组）上完成排序，而不是用新对象存储结果；… 阅读全文

选择问题

选择问题 选择问题是求集合的第\(k\)小(第\(k\)大)元素。具体可表述为“给定乱序序列，求其递减排序序列中，下标为\(k-1\)的元素”。最容易想到的是直接用\(O(nlgn)\)分治排序对整个序列排序，另一种思路是遍历\(k\)次序列，每轮都求一个最大值的下标，每轮求的时候都避开之前已求出的下标，这样代价是\(O(nk)\)，如果\(k\)是常数就是\(O(n)\)，但如果\(k\)和\(n\)同阶就是\(O(n^2)\)。 这里看一种基于快速排序的算法，快速排序每次递归都会把序列分为左右两半，右半边的任意元素都大于等于左半边的任意元素。这时如果分别记录左半边和右半边的长度，就能确定第\(k\)小元素是在左半边还是右半边。接下来就不用像快排那样分别递归左半边和右半边，只需要递归两者中的其中一个。递归前需要把\(k\)换算，转换成表示“子问题”中的第\(k’\)小元素。… 阅读全文

最大流问题的增广路方法

Ford-Fulkerson方法有流网络\(G=(V,E)\)，其容量\(c\)(默认整数)、流\(f\)、源点\(s\)与汇点\(t\)。\(G\)与\(f\)给定\(G_f\)与\(c_f\)。则有步骤： 1) 遍历\((u,v) \in E\)，初始化流变量\((u,v).f=0\)； 2) 若当前\(G_f\)中存在某个增广路\(p\)则继续迭代，否则停机； 3) 求出增广路容量\(c_f(p)=min\{c_f(u,v)|(u,v) \in p\}\)； 4) 遍历\((u,v) \in p\)，若\((u,v)\in E\)，\((u,v).f+=c_f(p)\)，否则\((v,u).f-=c_f(p)\)，返回(2)； 其之所以不称为算法是因为(2)未有细节，算法与代价无法确定，但可验证其正确性。设每次(2)结束后发现某个\(G_f\)的增广路\(p\)，\(f\)更新为\((f\uparrow… 阅读全文
滚动至顶部