智能搜索算法求解最大团问题研究

最大团问题MCP(Maximum Clique Problem)在国外得到了广泛的研究,在国内刚起步,是一类NP完全问题。传统的确定性算法不能有效地进行求解。定义了MCP;介绍了使用启发式算法求解MCP的研究进展;综述了几种典型的智能搜索算法;分析了使用这些典型算法求解MCP的基本思想;研究了这些智能算法在求解MCP时的特点及性能。

维普资讯 http://www.1mpi.com

第2 5卷第 5期 20 0 8年 5月

计算机应用与软件 Co u e mp t rAppi ai n n fwa e l to s a d Sot r c

Vo . 5 No 5 12 . M a 00 v2 8

智能搜索算法求解最大团问题研究 周旭东王丽爱陈峻 (扬州大学信息学院江苏扬州 2 50 ) 20 9 江苏南京 20 9 ) 10 3 (南京大学软件新技术国家重点实验室

摘要

最大团问题 MC ( xm m Ciu r l在国外得到了广泛的研究,国内刚起步,一类 N P Maiu l ePo e q b m)在是 P完全问题。传统的确

定性算法不能有效地进行求解。定义了MC; P介绍了使用启发式算法求解 M P的研究进展; C综述了几种典型的智能搜索算法;分析 了使用这些典型算法求解 MC P的基本思想;究了这些智能算法在求解 MC研 P时的特点及性能。 关键词最大团问题启发式算法智能搜索算法

S TUDY oN SoLVI NG CP M BY NTELLI I GENT SEARCH ALGoRI THM Zh u Xu n o do g W a g Lii n a Che ng _ n Li

( oeeo nom t n Y nzo nvrt,agh u25 0 Jagu C ia C lg fr ai,aghuU i sy Y nzo 2 0 9,ins, hn ) l fI o ei。 N t n l e a oe S taeTcnl y N ni nvnt Ni i 103,in s,hn ) ( ai a yL bo vl o w r ehoo, aj g U i i tj g2 0 9 Ja gt C ia o K fN f g n e y, n n i

A s at b t c r

MC sa P C m l epo l ie u i bo db t n C ia h sac s s r d s h a io a d tr n t P a n N— o pe rbe i w d l s de a ra u i hn e ee rhj t t t .A et dt nl ee ae t m s yt d t r u a e t r i mi

l o hms c nn ts l e M CP e e tv l hi a e n r d ce h veo me to i g h u si lo t m o s le M CP n x r s e n o ag rt i a o ov f ci

ey,t s p p rito u st e de l p n fusn e r tc ag r h t ov i i a d e p e s sa —

v r iw o o y ia n el e ts ac g r h swela n y e h a i p r a h o s a pi ai n h r i n e o a c so eve n s me tp c lit l g n e rh a o t msa l sa a z st e b sc a p o c n i p l t .T etat a d p r r n e f i l i l t c o s f m t s n el n g rt m so ovng M CP r ic s e s we1 he e it lge ta o h n s li i l i we e d s u s d a l.

K y rs ewod

Maiu l u rbe ( P Hert l rh Itlgn sac grh x m m c q epol i m MC ) u sca oi m ne i t erha o tms ii g t le l i

(顶点增多和边密度变大 )确定性算法显得无能为力,,不能有

0引言 最大团问题是现实世界中的一类真实问题,实践中有非在

效解决这些 N P完全问题,型地体现是运行时间过长。因此,典 目前确定性算法主要用于求解顶点数相对较少,密度相对较低 的图的最大团。

常广泛的应用…,用领域有市场分析、案的选择、号传应方信

针对上述情况,在上世纪八十年代末,人们开始采用启发式算法求解最大团,提出了各种各样的启发式算法,并且取得了很令人满意的效果,时间上,在由于采用了启发式信息,启发式算法的运算时间与确定性算法的运算时间之比会随着图的顶点、 密度的增加,变得越来越小。唯一的缺点是不一定能找到最优值,有时只能找到近优值。 启发式算法的出现给求解顶点多、密度高的图的最大团问题带来了希望,并且经过这十几年的发展,取得了长足的进步。 大部分确定性算法所不能解决的图,启发式算法都得到了有用效的解决。人们对启发式算法关注程度越来越高。 当前求解最大团问题的启发式算法基于以下几类:局部搜

输、计算机视觉、故障诊断等。传统的确定性算法不能有效地进 行求解,因此提出了各种各样的启发式算法。目前国内通过启发式算法求解最大团问题的

研究还处于初期阶段。

1最大团问题定义 1 1最大团问题的基本定义 . 对于给定图 G=( E,中,, )其 V={,,}图 G的顶点 1… n是集, V E×V是图 G的边集。图 G的团就是一两两之间有边的

顶点集合。如果一个团不被其它任一团所包含,即它不是其它 任一团的真子集,则称该团为图 G的极大团。顶点最多的极大团,称之为图 G的最大团。最大团问题的目标就是要找到给定 图的最大团。

索启发式算法,智能搜索算法,于连续的启发式算法等。本文基 重点讲述使用智能搜索算法求解最大团问题。

最大团问题也被称为最大独立集问题,独立集指的是两两

2智能搜索算法求解最大团问题 智能搜索算法主要有遗传算法、禁忌算法、模拟退火算法、 神经网络等。 收稿日期:0 6一O 20 9一O。国家自然科学基金 ( 07 0 2; 6 64 3 1 )国家科

顶点之间没有边的顶点集合。顶点最多的独立集就是最大独立 集。如果 C是图 G的最大团,么 C也是 G那的最大独立集。

1 2最大团问题研究进展 . 15 97年, aa H r R s首次提出求解最大团问题的确定性 r v和 os

算法,随后,研究者们提出各种各样的确定性算法来求解最大团问题。但随着研究的深入,到的问题复杂度越来越高遇

技攻关项目( 0 3 A 1A一1; 2 0 B 64 4)江苏省自然科学基金 ( K 0 5 7) B 2 00。 4周旭东,硕士,主研领域: b搜索, We智能算法, gn。 A et

智能搜索算法求解最大团问题研究

Word文档免费下载Word文档免费下载:智能搜索算法求解最大团问题研究 (共1页,当前第1页)

你可能喜欢

  • 移动方案
  • 人工智能算法
  • 群体智能算法
  • 智能天线算法
  • 智能优化算法
  • 线性系统稳定性
  • ARM嵌入式
  • 自动控制原理第二章

智能搜索算法求解最大团问题研究相关文档

最新文档

返回顶部