| 查看: 1990 | 回复: 8 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
JUST_ME_ME铁虫 (小有名气)
|
[交流]
关于顶点覆盖算法的一些问题
|
||
|
由于课题需要一直在研究一些关于顶点覆盖的算法，自己也查看文献实践了一些，但发现效果并不是很好，但也拿出来和大家共同分享一下，同时期盼能够各位能给出好的意见。 顶点覆盖是图论中的经典组合优化问题，我所研究的是无向简单图的顶点覆盖。 问题描述如下：图中有n个点（点可以代表事件，代表物体等等），把有关系的点相连形成边，设边数为m；这样就得到一个G（n,m）的无向图，如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。 目前楼主使用了一种比较常用易于理解的算法，最大度贪婪算法。 找到图中度最大的顶点，放入C,删除其以及与其关联的边，形成新的图，再继续以上操作，知道最大度为零，结束。 但结果不是很好，精准度较差，如有研究图论的大师，请跳出来，指点迷津~~ |
回复此楼» 猜你喜欢
遇见不省心的家人很难过
已经有18人回复
-
退学或坚持读
已经有25人回复
-
博士延得我，科研能力直往上蹿
已经有4人回复
-
免疫学博士有名额，速联系
已经有14人回复
-
面上基金申报没有其他的参与者成吗
已经有4人回复
-
多组分精馏求助
已经有6人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 有限单群：一段百年征程
已经有11人回复
JUST_ME_ME
铁虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 42.7
- 红花: 1
- 帖子: 106
- 在线: 63.8小时
- 虫号: 3343845
- 注册: 2014-07-29
- 性别: MM
- 专业: 传动机械学
7楼2014-08-07 16:09:21
锐利的碎片
木虫 (正式写手)
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