面向超图数据的最大独立集算法

超图是普通图的泛化表示,在许多应用领域都很常见,包括互联网、生物信息学和社交网络等.独立集问题是图分析领域的一个基础性研究问题,传统的独立集算法大多都是针对普通图数据,如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题.针对这一问题,提出一种超图独立集的定义.首先分析超图独立集搜索的两个特性,然后提出一种基于贪心策略的基础算法.接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合,以精确剪枝策略缩小图的规模,以近似剪枝策略加快搜索速度.此外,还提出4种高效的剪枝策略,并对每种剪枝策略进行理论证明.最后,通过在10个真实超图数据集上进行实验,结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.

量子近似优化算法在最大独立集中的应用

最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

基于闭环DNA计算的最大独立集问题的算法

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。

一类求解最大独立集问题的混合神经演化算法

提出一类求解最大独立集问题 (MIS)的混合型神经演化算法 .该算法基于空间剖分与“排除”策略 ,有效综合了神经网络快速收敛及遗传算法稳健全局搜索的特别优点 .与标准遗传算法和神经网络算法相比 ,该算法显示了极高的全局优化性态与计算效率 .

基于Hopneld网络的图的最大团和最大独立集算法

本文应用Hopfield网络,系统地研究了图的最大团和最大独立集问題,通过建立相应的数学理论,改进了这方面已有的工作,并进行了模拟实验,给出了实验研究的结果。

基于PNA的最大独立集问题的DNA计算模型

肤核酸(Peptide Nucleic Acid)是人工合成的拔酸(DNA)的类似物.PNA能够特异地、稳定地与DNA杂交以及其独特的性质,使得PNA广泛应用在分子生物学中.本文提出了一种基于PNA的最大独立集问题的DNA计算模型,利用单链PNA被逐步褪火到单链DNA分子上,解决了一个最大独立集问题的实例.该模型的解空间只有一种类型的DNA分子,计算经m步生物操作产生问题的解(其中m=|E(G)|),最后利用鞭子PCR(whiplash PCR)原理以及凝胶电泳读解.

基于最大独立集的钢种集约问题求解方法

针对炼钢生产中的钢种集约问题,建立了数学模型,并以图论的思路设计了一种基于最大独立集的求解方法.首先基于图论知识,构造了钢种集约问题的图,并证明了最大独立集的独立数是它的主目标的下界;然后对图进行赋权,以实现对次要目标的控制;最后在最大独立集的基础上,采用图分解的方法,对赋权图递归分解来获得优化后的钢种集约方案.选择实际生产数据构造了一些测试案例,对它们进行仿真计算,结果表明所提出的算法明显好于遗传算法;同时分析了图的顶点、密度变化对算法性能的影响,揭示了它们之间的关系.

用神经网络新方法求解图的最大独立集问题

在Hopfield神经网络优化方法的基础上,根据模拟退火算法逃离局部最优解的原理,提出了一种神经网络优化计算的新方法,并用这种方法求解图的最大独立集问题。结果表明,该方法获得最优解比Hopfield神经网络优化算法获得的解要好,且所需时间比模拟退火算法少得多,

最大独立集算法

本文提出了网络中的一种特殊结构──负包络图。原来是它包含了网络的最小截，因而制约了网络的最大流量。研究表明，负包络图也是关于网络最大独立集的充要条件。本文以既有的最大流算法为手段，利用这个充要条件，给出了在偶网络上求最大独立集的有效算法，而且也给出了在奇网络上求最大独立集的递归算法。

一种启发式的分布式最大独立集算法

从最大独立集问题的0-1整数规划数学描述入手,首先针对树图情形提出了一种基本的分布式树(Tree)算法,并证明该算法在树图情形下是最优的,然后将该Tree算法针对一般图情形进行了启发式的修正,得到一种新的分布式修正树(m-Tree)算法。理论分析表明,当图为树或二分图时,m-Tree算法可以简化为基于信用传播(BP)的分布式算法,是对BP算法的一种推广。仿真结果表明,对于树或二分图情形,m-Tree算法与BP算法都能收敛至最优解;对于一般图情形,m-Tree算法的收敛性能与权和性能均远优于BP算法,并且其权和性能接近最优解。

网络分解及最大独立集算法研究(Ⅰ)

本文首先分析了一般网络的结构特征,开发出对任意网络进行变换及分解、且不丢失可行解的新方法。继而发现了网络中具有优化迭代功能的特殊子网络;对其进行了较深入的研究,提出并论证了求最大独立集的充要条件;研制出在网络中系统搜索该特殊子网络的新算法。最后,对算法的有效性及可靠性,进行了较全面的分析论证。研究表明,该算法可在时间复杂性O(|V|5)界内收敛。

求解图的最大独立集的一种算法

如何寻找图的最大独立集这个问题是一个古老的难题。文章从图论的基本概念入手 ,得到了一种基于图的邻接矩阵的寻找图的极大独立集和最大独立集的算法 ,并得到其算法复杂度为 O(nn!/(m!(n - m) !) )

最大独立集在高校排课表系统中的应用

在分析排课系统特征的基础上,利用图论中最大独立集的理论,对排课资源进行合理抽象并建模,实现自动排课的功能要求,并进行算例分析。算例分析表明,该方法解决排课表问题相当实用,而且效率较高。该方法具有效性和可靠性。

一种求解最大独立集的自学习进化算法

为了求解最大独立集问题,通过对求解最大团问题EA/G算法的分析,从初始解选取、种群的构成、遗传策略等方面对EA/G算法进行了改进,提出了自学习进化算法,并在DIMACS基准图上进行了大量的实验.实验结果表明,该算法运算结果比EA/G算法所求结果有很好的改善.

找最大匹配和最大独立集的布尔方法

本文将寻找简单图的最大匹配归结为寻找相应的有约束条件的伪布尔函数的极值,接着将有约束条件的伪布尔函数的极值问题转换为等价的无约束条件的伪布尔函数的极值问题。对于后者,给出了迭代算法及手算实例,最后还讨论了求最大独立集的布尔方法。

随机图的最大独立集

文章主要介绍了用非贪婪算法在由顶点数和基准边密度赋值生成的不同类型的随机图上进行求最大独立集的测试,通过对测试结果的分析得出顶点数、边密度、基准边密度与独立数、运行时间的联系。

关于圆弧图最大独立集的一种最优算法

本文提出了关于圆弧图最大独立集的一种新算法。当图以弧族的形式给出时,时间和空间复杂性为O(n.logn),O(n)。如果这些弧的端点已排序,则需O(n)时间。此算法时间和空间都是最优的且在常数因子内完成。

寻找最大独立集的算法

提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向.

基于DNA自组装模型解决图的最大独立集问题

为了寻找图的最大独立集问题,先利用DNA自组装模型解决可满足性问题,再把最大独立集问题转化为可满足性问题,从而解决最大独立集问题。整个过程只用到凝胶电泳操作,在很大程度上减少了误差。

边带权最大独立集问题及其近似算法

区别于传统对带权最大独立集问题的研完,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性。并且通过对问题结构的研完,给出了一个近似度为1/「(Δ′+1)/3」的近似算法,Δ′为图中点的最大度数。