| 查看: 2038 | 回复: 8 | |||
JUST_ME_ME铁虫 (小有名气)
|
[交流]
关于顶点覆盖算法的一些问题
|
|
由于课题需要一直在研究一些关于顶点覆盖的算法，自己也查看文献实践了一些，但发现效果并不是很好，但也拿出来和大家共同分享一下，同时期盼能够各位能给出好的意见。 顶点覆盖是图论中的经典组合优化问题，我所研究的是无向简单图的顶点覆盖。 问题描述如下：图中有n个点（点可以代表事件，代表物体等等），把有关系的点相连形成边，设边数为m；这样就得到一个G（n,m）的无向图，如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。 目前楼主使用了一种比较常用易于理解的算法，最大度贪婪算法。 找到图中度最大的顶点，放入C,删除其以及与其关联的边，形成新的图，再继续以上操作，知道最大度为零，结束。 但结果不是很好，精准度较差，如有研究图论的大师，请跳出来，指点迷津~~ |
回复此楼» 猜你喜欢
总分293求调剂
已经有5人回复
-
335分 | 材料与化工专硕 | GPA 4.07 | 有科研经历
已经有6人回复
-
289求调剂
已经有14人回复
-
085600 材料与化工 329分求调剂
已经有6人回复
-
化学工程085602 305分求调剂
已经有9人回复
-
312求调剂
已经有7人回复
-
308求调剂
已经有5人回复
-
292求调剂
已经有7人回复
-
309求调剂
已经有4人回复
-
08工学调剂
已经有18人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 有限单群：一段百年征程
已经有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
5