JONY

贪心法与拟阵的贪心算法

贪心法 贪心法和分治法、动态规划一样，也属于分治策略这个大框架。先简单回顾分治法和动态规划，两者在求解子问题时，都要先解出其依赖的所有“子子问题”，然后基于此得到当前子问题的解。而贪心算法在求解子问题时，则是先做“目前看来最优的选择”，然后再求解子问题。这意味着贪心算法在不知道“子子问题”的解的情况下求出了“部分解”。那么对于原问题，除了要存在分治算法和动态规划算法(最优子结构)，还要有“更强的性质”才能有贪心算法，称为贪心选择性。 经典的(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|\)；… 阅读全文

活动选择问题

活动选择问题问题可表述为“设\(S[0,1…n]\)为‘活动’的序列，每个‘活动’有开始、结束时间，\(S\)已按结束时间升序排序。规定所有‘活动’独占同一个教室，求出\(S\)中的‘活动’最多能安排多少个”。上图是其中一种\(S\)的例子。 设\(L\)是一个最优活动安排序列(已排序)。任取\(L[k]\)，并用其划分序列\(L_1 = L[0,…,k-1],L_2=L[k+1,…]\)。然后设\(s_1\)是“\(L[k]\)开始前结束的\(S\)中的所有活动”，\(s_2\)是“\(L[k]\)结束后开始的\(S\)中的所有活动”。可发现如果把\(s_1,s_2\)作为原问题的输入，则\(L_1,L_2\)必可分别作为最优活动安排序列，否则\(L\)本身就不是原问题的最优解了。然后任取\(L_1[k_1]\)……可以发现上述结论是递归的。然后用这个性质去找最优解，先回到原问题上，其任意最优活动安排序列都符合“空序列,包含\(S[0]\),包含\(S[1]\),包含\(S[2]\)…”中的至少一种，如果符合的是空序列，那么解就是0，否则就遍历这些元素，设每次遍历到的元素是\(x\)，然后用其划分\(S\)为“\(x\)开始前结束的\(S\)中的所有活动”，“\(x\)结束后开始的\(S\)中的所有活动”这两个序列，然后分别递归的求出它们的解并计做\(c_1,c_2\)，然后求出\(c=c_1+1+c_2\)，即放入\(x\)后的总活动数。每次遍历都会求一次\(c\)，其中最大的那个就是解。… 阅读全文

哈夫曼编码

字符编码编码指把相同信息在不同的形式间转化，例如把图片储存为像素(x,y,r,g,b)，把直角坐标方程改写为极坐标方程，把26个字母用26个二进制数表示，把明文转为密码和密文等等。无论信息形式如何变化，它们依然是同样的信息。字符编码研究如何用二进制形式表示某种语言的字符，其可被分类为定长编码与变长编码。基础ASCII码是种定长编码，无论是英文逗号、空格、回车、换行甚至响铃都有自己的ASCII码。其定长策略是在所有二进制数(编码)前补0，保证每个编码都是7-Bit。强国官方编码GB18030是种变长编码，其有1/2/4字节三种长度，1字节长度的是ASCII的超集，2字节长度的是GBK的超集，4字节长度的是其他新加入的生僻的中文字符与中文符号。   前缀编码对任意字符串的任意前缀编码方案，每个字符的编码都不是其他编码的前缀。任何前缀编码方案都可用二叉树(如上图)表示，其非叶节点的左/右边表示0/1，从根节点出发可根据编码方案“生成”编码树。由于前缀码间互不为前缀，故字符不会出现在非叶节点，故叶节点必为被编码字符本身。对字符串\(S\)与其前缀编码二叉树\(T\)，设\(f(c)\)为字符\(c\)的出现次数，\(d(c)\)为字符\(c\)在前缀编码二叉树的深度，编码二叉树所对应的代价为\(B(T)=\sum… 阅读全文

多模匹配问题与AC自动机

多模匹配与AC自动机 多模匹配指“给定单个目标串与多个模式串，确定所有模式串在目标串中的所有出现位置”，相比单模匹配的“单个模式串，首次出现”，多模匹配明显更抽象和复杂（我的看法是AC自动机比KMP难一些）。这里把目标串和模式串分别计为\(t\)和\(p_1,p_2…\)，还是老样子先简单的找一个多模匹配的朴素算法如下。 1）从\(t\)的第1位字符开始，与模式串\(p_1\)逐位对齐比较，匹配成功则记录\(p_1\)在第1位出现1次； 2）从\(t\)的第1位字符开始，与模式串\(p_2\)逐位对齐比较，匹配成功则记录\(p_2\)在第1位出现1次； … n）从\(t\)的第2位字符开始，与模式串\(p_1\)逐位对齐比较，匹配成功则记录\(p_1\)在第2位出现1次； …… 阅读全文

编辑距离与最小编辑距离问题

编辑距离模型 给出3种编辑距离模型中对“编辑”操作的定义： 1) Levenshtein距离：允许“替换1个字符、任意位置删1个字符、任意位置插1个字符”，权重都是1； 2) LCS距离(最长公共子序列距离)：允许“任意位置删1个字符、任意位置插1个字符”，权重都是1； 3) Hamming距离：允许“替换1个字符”，权重都是1（两串长度不同时其Hamming距离是无穷）； 所有编辑距离模型对“距离”的定义都是“将\(s_1\)通过模型允许的操作转化为\(s_2\)所耗费的权重”，那么最小编辑距离的定义就是“将\(s_1\)通过模型允许的操作转化为\(s_2\)需要的最小权重”。可以发现“最小编辑距离”是一类定量刻画字符串“相似度”的方案，其通过“编辑复杂程度”刻画“相似度”。 另外，最小编辑距离之所以称为“距离”是因为上述3个模型所定义的最小编辑距离满足数学上距离空间(度量空间)的性质。比如设\(L(s_1,s_2)\)为\(s_1\)到\(s_2\)的最小Levenshtein距离，其满足如下度量空间性质：… 阅读全文
滚动至顶部