算法

流网络的最大流与最小割

流网络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… 阅读全文

贪心法与拟阵的贪心算法

贪心法 贪心法和分治法、动态规划一样，也属于分治策略这个大框架。先简单回顾分治法和动态规划，两者在求解子问题时，都要先解出其依赖的所有“子子问题”，然后基于此得到当前子问题的解。而贪心算法在求解子问题时，则是先做“目前看来最优的选择”，然后再求解子问题。这意味着贪心算法在不知道“子子问题”的解的情况下求出了“部分解”。那么对于原问题，除了要存在分治算法和动态规划算法(最优子结构)，还要有“更强的性质”才能有贪心算法，称为贪心选择性。 经典的(01)背包问题是没有贪心选择性质的，如果以“每次取价值最大的物品”的策略求解，得到的解可能不是总价值最大的解，并且也没有其他的贪心策略能求解。但如果背包里的物品是可分割的(这时也称为部分背包问题)，就是能取物品的2%、0.3%，那么上述贪心策略就能找到最优解，也就是说部分背包问题具有贪心选择性质，这是个很显然的结论不需要证明。这里稍微提一个细节，计算机是不好直接处理无理数小数和循环小数的，但把有理数用二元组表示就能解决这个问题，而由于解的每一项都能写成关于输入的算数表达式，所以只要输入都是有理数那么这个问题就好用计算机直接求解。… 阅读全文

最大流问题的预流推进方法

Goldberg-Tarjan方法 Ford-Fulkerson方法是所有增广路算法的基础，Goldberg-Tarjan方法则是基于预流的算法的基础，定义了“推送”与“重贴高度标签”两个重要操作，故也称“推送-重贴标签”方法。下面给出需要的概念与定义： 1) 预流：流网络上的预流与流非常相似，其唯一区别在于任意顶点的总流入可大于等于总流出。所以流是预流的特例，任意顶点的总流入等于总流出的预流即是合法的流。算法将通过不断的调整预流使其变为合法的最大流； 2) 超额流：给定流网络与预流，任意顶点的超额流为总流入减总流出； 3) 溢出点：除了源与汇，总流入大于总流出的顶点称为溢出点； 4) 残存网络：流网络与其上的一个预流，可以和流一样的给定一个残存网络； 5) 高度函数：给定流网络\(G=(V,E)\)的源与汇为\(s\)与\(t\)，其上有预流为\(f\)，\(f\)给定了预流残存网络\(G_f=(V,E_f)\)。如果非负整数函数\(h\)满足\(h(s)=|V|,h(t)=0\)，且对于\((u,v)\in… 阅读全文

二分图的最大匹配与最小点覆盖

无向图的覆盖集 点覆盖：无向图的点覆盖是顶点集的子集，边集中的每个边都至少有1个端点位于点覆盖； 点覆盖数：点覆盖中的元素数目； 最小点覆盖：元素数目最小的点覆盖； 边覆盖：无向图的边覆盖是边集的子集，顶点集中的每个顶点都为边覆盖中至少1个边的端点； 边覆盖数：边覆盖中的元素数目； 极小边覆盖：若一个边覆盖的任何真子集都不是边覆盖，则称其为极小边覆盖。这里考虑关于无向图\(G=(V,E)\)的两种情况，一种是存在边集\(S_1 = \{ (u,v) ~|~ v\in V-\{u\}\}\)，其中\(|S_1|=|V|-1\)。另一种是存在边集\(S_2\)中每个边的每个端点只出现1次，其中\(|S_2|=\frac{|V|}{2}\)。这两种边集显然可以出现在同个无向图中，其都是极小边覆盖。 最小边覆盖：元素数目最小的边覆盖，根据极小边覆盖的定义，最小边覆盖一定属于极小边覆盖；… 阅读全文

单模匹配问题与KMP算法

单模匹配 字符串是一个序列，序列的每个下标对应一个字符，单模匹配指在字符串A(目标串)中查找字符串B(模式串)，若A中包含B则返回B首次出现时的首字母下标。朴素算法的流程是首先B对齐A首位，然后逐位比较字符，若某位匹配失败则退出，然后将B对齐A的第二位…重复上述步骤。该算法的代价为\(O(ab)\)。 Python def bruteFind(target, pattern): offset = 0 while 1: if offset+len(pattern) > len(target): return -1 for i in range(len(pattern)): if target[i+offset] != pattern[i]: offset += 1 break else: return offset 1234567891011… 阅读全文

最大流与最大二分匹配

基于最大流的算法定义\(G’=(V’,E’)\)为二分图\(G=(V,E)\)与其顶点划分\((L,R)\)所给定的流网络，其中\(V’=V\bigcup \{s,t\}\)，即源\(s\)与汇\(t\)是不属于\(V\)的新顶点。横跨\((L,R)\)的无向边(所有\(E\))是\(E’\)中\(L\)到\(R\)的有向边，\(E’\)需额外加入\(s\)到\(L\)所有节点的边，\(R\)所有节点到\(t\)的边。流网络的每个边的容量都是1，定义1值流\(f\in \{0,1\}\)，给出关于\(G\)与\(G’\)的关键引理： a) \(G\)存在匹配\(M\)，则\(G’\)存在1值流\(f\)，其中\(|f|=|M|\)；… 阅读全文
滚动至顶部