| 查看: 1870 | 回复: 8 | |||
JUST_ME_ME铁虫 (小有名气)
|
[交流]
关于顶点覆盖算法的一些问题
|
|
由于课题需要一直在研究一些关于顶点覆盖的算法，自己也查看文献实践了一些，但发现效果并不是很好，但也拿出来和大家共同分享一下，同时期盼能够各位能给出好的意见。 顶点覆盖是图论中的经典组合优化问题，我所研究的是无向简单图的顶点覆盖。 问题描述如下：图中有n个点（点可以代表事件，代表物体等等），把有关系的点相连形成边，设边数为m；这样就得到一个G（n,m）的无向图，如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。 目前楼主使用了一种比较常用易于理解的算法，最大度贪婪算法。 找到图中度最大的顶点，放入C,删除其以及与其关联的边，形成新的图，再继续以上操作，知道最大度为零，结束。 但结果不是很好，精准度较差，如有研究图论的大师，请跳出来，指点迷津~~ |
回复此楼» 猜你喜欢
请问哪里可以有青B申请的本子可以借鉴一下。
已经有4人回复
-
真诚求助：手里的省社科项目结项要求主持人一篇中文核心，有什么渠道能发核心吗
已经有6人回复
-
孩子确诊有中度注意力缺陷
已经有14人回复
-
三甲基碘化亚砜的氧化反应
已经有4人回复
-
请问下大家为什么这个铃木偶联几乎不反应呢
已经有5人回复
-
请问有评职称，把科研教学业绩算分排序的高校吗
已经有5人回复
-
2025冷门绝学什么时候出结果
已经有3人回复
-
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入
已经有4人回复
-
康复大学泰山学者周祺惠团队招收博士研究生
已经有6人回复
-
AI论文写作工具：是科研加速器还是学术作弊器？
已经有3人回复
» 本主题相关价值贴推荐，对您同样有帮助:
有限单群：一段百年征程
已经有11人回复
锐利的碎片
木虫 (正式写手)
star watcher
- 应助: 136 (高中生)
- 金币: 3637.1
- 散金: 252
- 红花: 22
- 帖子: 988
- 在线: 1224.9小时
- 虫号: 961933
- 注册: 2010-03-05
- 专业: 凝聚态物性 II ：电子结构
2楼2014-08-04 21:46:14
JUST_ME_ME
铁虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 42.7
- 红花: 1
- 帖子: 106
- 在线: 63.8小时
- 虫号: 3343845
- 注册: 2014-07-29
- 性别: MM
- 专业: 传动机械学
3楼2014-08-05 11:19:13
4楼2014-08-05 20:31:19
JUST_ME_ME
铁虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 42.7
- 红花: 1
- 帖子: 106
- 在线: 63.8小时
- 虫号: 3343845
- 注册: 2014-07-29
- 性别: MM
- 专业: 传动机械学
5楼2014-08-06 15:21:20
6楼2014-08-06 16:30:58
JUST_ME_ME
铁虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 42.7
- 红花: 1
- 帖子: 106
- 在线: 63.8小时
- 虫号: 3343845
- 注册: 2014-07-29
- 性别: MM
- 专业: 传动机械学
7楼2014-08-07 16:09:21
Macer3
铜虫 (初入文坛)
- 应助: 2 (幼儿园)
- 金币: 481.3
- 散金: 100
- 帖子: 43
- 在线: 20.2小时
- 虫号: 3235666
- 注册: 2014-05-26
- 性别: GG
- 专业: 交通工程
8楼2014-08-08 23:08:31
Macer3
铜虫 (初入文坛)
- 应助: 2 (幼儿园)
- 金币: 481.3
- 散金: 100
- 帖子: 43
- 在线: 20.2小时
- 虫号: 3235666
- 注册: 2014-05-26
- 性别: GG
- 专业: 交通工程
9楼2014-08-23 06:54:44