24小时热门版块排行榜    

查看: 2547  |  回复: 8
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

JUST_ME_ME

铁虫 (小有名气)

[交流] 关于顶点覆盖算法的一些问题

由于课题需要一直在研究一些关于顶点覆盖的算法,自己也查看文献实践了一些,但发现效果并不是很好,但也拿出来和大家共同分享一下,同时期盼能够各位能给出好的意见。
             顶点覆盖是图论中的经典组合优化问题,我所研究的是无向简单图的顶点覆盖。
            问题描述如下:图中有n个点(点可以代表事件,代表物体等等),把有关系的点相连形成边,设边数为m;这样就得到一个G(n,m)的无向图,如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。
           目前楼主使用了一种比较常用易于理解的算法,最大度贪婪算法。
          找到图中度最大的顶点,放入C,删除其以及与其关联的边,形成新的图,再继续以上操作,知道最大度为零,结束。
          但结果不是很好,精准度较差,如有研究图论的大师,请跳出来,指点迷津~~
回复此楼
tobebetter
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

JUST_ME_ME

铁虫 (小有名气)

引用回帖:
2楼: Originally posted by 锐利的碎片 at 2014-08-04 21:46:14
我记得这是NP完备的,应该只有近似算法。

近似算法和启发算法适用,我选的是最大度贪婪算法,计算结果不堪入目的说,100的顶点要找第91个才能全部覆盖。。
tobebetter
3楼2014-08-05 11:19:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 9 个回答

锐利的碎片

木虫 (正式写手)

star watcher

★ ★
小木虫: 金币+0.5, 给个红包,谢谢回帖
jjdg: 金币+1, 感谢参与 2014-08-05 07:23:36
我记得这是NP完备的,应该只有近似算法。
2楼2014-08-04 21:46:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hc315

铁虫 (小有名气)

★
小木虫: 金币+0.5, 给个红包,谢谢回帖
求优化解,随便抓出一个智能算法都可以做
4楼2014-08-05 20:31:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

JUST_ME_ME

铁虫 (小有名气)

引用回帖:
4楼: Originally posted by hc315 at 2014-08-05 20:31:19
求优化解,随便抓出一个智能算法都可以做

用c实现智能算法会不会很难?
tobebetter
5楼2014-08-06 15:21:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[论文投稿] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-19 00:17 by Equinoxhua
[教师之家] 征友后感触 +5 重新启 2026-11-17 6/300 2026-11-18 21:22 by tjutjulee
[教师之家] 为了不被淘汰,必须要开始第三次奋斗了 +4 lice_1987 2026-11-15 6/300 2026-11-18 21:19 by tjutjulee
[找工作] 售SCI一区T0P文章,我:8.O.55.1.O54,科目全,可伽急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-18 14:51 by UPDUsNlULsJZ
[考研] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 SX5mJmPWDfOO 2026-11-13 4/200 2026-11-18 13:55 by UPDUsNlULsJZ
[考博] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-18 13:22 by UPDUsNlULsJZ
[论文投稿] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-18 11:43 by Z1pODz48hoDV
[硕博家园] 售SCI一区文章,我:8.O.551.O.5.4,科目全,可伽急 +5 XJXMuRjD7cK7 2026-11-13 5/250 2026-11-18 11:32 by Z1pODz48hoDV
[考研] 售SCI一区文章,我:8.O.55.1.O.54,科目齐全,可伽急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-18 11:21 by Z1pODz48hoDV
[考博] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-18 10:37 by Z1pODz48hoDV
[硕博家园] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 7/350 2026-11-18 09:09 by Z1pODz48hoDV
[考研] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 uKOSCocCb6Fm 2026-11-12 9/450 2026-11-18 09:06 by Equinoxhua
[公派出国] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 8/400 2026-11-18 08:58 by Z1pODz48hoDV
[硕博家园] 售SCI文章,我:8O.5.5.1O.54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 10/500 2026-11-16 22:49 by Equinoxhua
[考博] 27年药学 考博申请 +4 。12345 2026-11-14 5/250 2026-11-16 19:52 by 0611517sll
[硕博家园] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-16 11:06 by K7HMGGdOpylw
[公派出国] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-15 08:29 by xSrQNSSjcgoX
[硕博家园] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +4 XJXMuRjD7cK7 2026-11-13 4/200 2026-11-15 06:50 by xSrQNSSjcgoX
[考博] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +3 uKOSCocCb6Fm 2026-11-12 7/350 2026-11-15 03:32 by xSrQNSSjcgoX
[论文投稿] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-12 10/500 2026-11-15 02:15 by xSrQNSSjcgoX
信息提示
请填处理意见