关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法,蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

基于蚁群算法求解最大团问题

最大团问题是一种典型的NP完全问题, 是图论中一个经典的组合优化问题.研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法.通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷.仿真实验表明,图中的顶点数较多时,也取得了较好的结果.     

最大团问题研究进展及算法测试标准

定义了最大团问题,分析和研究了使用启发式算法求解最大团问题的进展,介绍了当前求解最大团问题的典型启发式算法,最后给出了测试这些启发式算法性能的测试基准图.     

启发式算法求解最大团问题研究

最大团问题(maximum clique problem,MCP)是图论中的一个经典组合优化问题,也是一类NP完全问题,在国际上已有广泛地研究,国内研究刚刚起步.给出了最大团问题的基本定义和其数学描述;阐述了该问题的研究进展;分析和研究了求解该问题的各种典型启发式算法,包括算法的介绍、算法求解最大团问题的基本思路、特点及性能;最后介绍了测试这些启发式算法性能的测试基准图.     

最大团问题的改进蚁群算法求解

为了更好的解决最大团问题,提出一种改进的蚁群算法。通过提取图的顶点信息,将图用信息素模型来表示;根据最大团问题的约束条件利用蚁群构造极大团,并进行实时的全局信息素更新和局部信息素更新,直到找到最大团。实验结果表明,算法能较好的实现最大团问题,算法性能高于通用的蚁群算法。     

一种基于匹配交叉求解最大团问题的Memetic算法

针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,提出一种新的基于匹配交叉的Memetic算法.该算法提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值.通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式.在40个最大团问题标准算例上的测试结果表明,新算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法.     

最大团问题降阶算法

最大团问题是找出给定图中的一个最大结点子集合,使得子集合中的任意两点之间都有边相连,最大团问题是一个著名的NP-难题,在很多领域中都有着广泛的应用.本文在研究最大团问题数学性质的基础上给出该问题的一个初步降阶方法;在初步降阶的基础上给出一个求解最大团问题的上、下界方法;最后将降阶方法和上下界方法结合起来形成一个全新的降阶算法,该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.在文中还介绍了本算法和其它各类算法的优缺点,最后通过多个示例来进一步说明算法的原理及应用情况.     

一种求解最大团问题的并行交叉熵算法

为了提高交叉熵算法求解最大团问题(maximum clique problem,MCP)的性能,提出一种领导者-跟随者协作求解的并行策略来实现交叉熵算法,从而达到减少计算时间和保障解的质量这两方面的平衡.算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务.采用了OpenMPI在MIMD平台上实现了该算法,并应用到MCP基准测试问题上.加速比和效率分析结果表明,算法具有很好的加速比和效率.而与其它几种当前最好的启发式算法相比,结果表明算法相对于基于种群的启发式算法有一定的性能改善.     

最大团问题的加权分治算法

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为[O(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。     

顶点编码方法对最大团算法影响的研究

最大团算法是基于图数据挖掘的一个重要算法,提高最大团算法效率是研究的重点。以一个典型的精确求解最大团算法为基础,分析了两种顶点编码方法对最大团算法的影响,并在随机图上做了对比实验,验证了在不改变算法的前提下,通过改变顶点编码方法也可以提高最大团算法效率的结论。     

A Neural Algorithm for the Maximum Clique Problem: Analysis,Experiments, and Circuit Implementation

{In this paper we design and analyze a neural approximation algorithm for the Maximum Clique problem. This algorithm, having as input an arbitrary undirected graph G = \langle V, E\rangle , constructs a finite sequence of Hopfield networks such that the attractor of the last network in the sequence represents a maximal clique of G . We prove that D(G) ⋅ |E ^{\rm c} | , where D(G) = max _{{i,j}\notin E} \min{d _i , d _j } , d _i is the degree of the vertex i of G , and |E ^{\rm c} | denotes the cardinality of the set of edges in the complement graph, is an upper bound to the number of the networks in the sequence. Some experiments made on the second DIMACS benchmark and on random graphs show that: 1. The quality of the solutions found by the algorithm is satisfactory. 2. The theoretical upper bound D(G) ⋅ |E ^{\rm c} | is quite pessimistic. For random graphs we propose an empirical formula that gives a better estimate of the number of networks in the sequence. Moreover, thanks to the simplicity of the algorithm, we are able to design a uniform family of circuits of small size (\approx 10n ² log ₂ n ) that implements it. The circuit, which solves the problems for graphs of at most 32 vertices, has then been programmed on FPGAs (Field Programmable Gate Arrays). An analysis in terms of size and time complexity is given. Received November 10, 1998; revised December 2000.     

一种求解最大团问题的自适应过滤局部搜索算法

提出了一种求解最大团问题的自适应过滤局部搜索算法AF-RLS(adaptive filtered-reactive local search).该算法通过构建独立集约束,优选出有希望的邻域移动方向来提高局部搜索趋向最优解的概率;并在比较分析两种不同逃逸策略的逃逸能力和逃逸代价的基础上,提出了基于问题解空间结构自适应设置...     

图的最大团与最大独立集粘贴DNA计算模型

粘贴模型(stickermodel)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.     

基于三角环的顶点着色问题解法

图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集。     

一种最大团问题的Tile自组装高效模型

Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现：模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n~2n,求解成功率由0.5n0增加至0.5n~0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.     

一种改进的最大团问题DNA计算机算法

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n）,同时文中算法还具有高效的空间利用率及容错能力的优点．