srcmini
NP完全问题实例分析
本文概述 简化和分解 NP完全问题的例子 判定问题L为NP-Hard 对于所有L’NP, L’≤pL。 定义：如果L是NP完全的, 则 LϵNP和 对于某些已知的NP完全问题L, L’≤pL。给定这个正式...
算法设计与分析 第11页
多项式时间验证
本文概述 哈密顿循环问题： P和NP类的关系 简化 多项式时间减少 在讨论NP完全问题的类别之前, 必须先介绍验证算法的概念。 许多问题很难解决, 但是它们具有以下特性：如果提供了解决方案, 则很容易对解决方案进行身份验证。 哈密顿...
算法复杂度分类
NP类问题的定义问题：-所有基于决策的问题的集合进入了NP问题的划分中, 这些问题无法在多项式时间内解决或产生输出, 但需要在多项式时间内进行验证。 NP类包含P类作为子集。 NP问题难以解决。 注意：-术语“ NP”并不表示“非多项式”。...
图论：合并网络
合并网络是可以将两个排序的输入序列合并为一个排序的输出序列的网络。我们使用BITONIC-SORTER [n]创建合并网络MERGER [n]。 合并网络基于以下假设： 给定两个排序的序列, 如果我们颠倒第二个序列的顺序, 然后连接两个序列...
双调的排序网络
单调增加然后单调减少, 或者单调减少然后单调增加的序列称为双音序列。例如：序列（2、5、6、9、3、1）和（8、7、5、2、4、6）都是双声的。双音分类器是一个比较网络, 可对0和1的双音序列进行分类。 Half-Cleaner：双音速分选...
图论：比较网络
比较网络由电线和比较器组成。比较器是具有两个输入x和y以及两个输出x’和y’的设备, 其中 x’=最小值（x, y）y’=最大值（x, y） 在“比较网络”中, 输入出现在左侧, 输出出现在右...
图论：最大二分匹配
二分图是其顶点可以分为两个独立的集合L和R的图, 这样每个边（u, v）要么连接从L到R的顶点, 要么连接从R到L的顶点。换句话说, 对于每个边（u, v）u∈L和v∈L。我们也可以说不存在连接相同集合的顶点的边。 匹配是一个二部图, 它是...
Ford-folkerson算法
最初, 值的流为0。找到一些扩充路径p, 并通过剩余容量cf（p）在p的每个边缘上增加流f。当不存在增加路径时, 流量f为最大流量。 示例：每个定向边都标记有容量。使用Ford-Fulkerson算法查找最大流量。 解：每个部分的左侧显示带...
图论：网络流量问题
最明显的流网络问题如下： 问题1：给定一个流量网络G =（V, E）, 最大流量问题是找到一个最大值的流量。 问题2：多个源和汇的最大流量问题与最大流量问题类似, 不同之处在于, 有一组{s1, s2, s3 ……....
图论之流网络和流
流动网络是用于对物料流动建模的有向图。有两个不同的顶点。一种是以一定的稳定速率生产物料的源, 另一种是以相同的恒定速度消耗物料的水槽。材料在系统中任何标记处的流动是元件移动的速率。 可以使用流动网络对一些现实生活中的问题进行建模, 例如液体...