| 查看: 2041 | 回复: 8 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
JUST_ME_ME铁虫 (小有名气)
|
[交流]
关于顶点覆盖算法的一些问题
|
||
|
由于课题需要一直在研究一些关于顶点覆盖的算法，自己也查看文献实践了一些，但发现效果并不是很好，但也拿出来和大家共同分享一下，同时期盼能够各位能给出好的意见。 顶点覆盖是图论中的经典组合优化问题，我所研究的是无向简单图的顶点覆盖。 问题描述如下：图中有n个点（点可以代表事件，代表物体等等），把有关系的点相连形成边，设边数为m；这样就得到一个G（n,m）的无向图，如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。 目前楼主使用了一种比较常用易于理解的算法，最大度贪婪算法。 找到图中度最大的顶点，放入C,删除其以及与其关联的边，形成新的图，再继续以上操作，知道最大度为零，结束。 但结果不是很好，精准度较差，如有研究图论的大师，请跳出来，指点迷津~~ |
回复此楼» 猜你喜欢
292求调剂
已经有8人回复
-
求调剂
已经有4人回复
-
一志愿 西北大学 总分282 英语一62 求调剂
已经有3人回复
-
调剂310
已经有4人回复
-
北科281学硕材料求调剂
已经有16人回复
-
一志愿上海交大生物与医药专硕324分，求调剂
已经有6人回复
-
一志愿哈工大，085400，320，求调剂
已经有4人回复
-
316求调剂
已经有9人回复
-
085600 材料与化工 329分求调剂
已经有8人回复
-
0856求调剂
已经有6人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 有限单群：一段百年征程
已经有11人回复
JUST_ME_ME
铁虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 42.7
- 红花: 1
- 帖子: 106
- 在线: 63.8小时
- 虫号: 3343845
- 注册: 2014-07-29
- 性别: MM
- 专业: 传动机械学
3楼2014-08-05 11:19:13
锐利的碎片
木虫 (正式写手)
star watcher
- 应助: 136 (高中生)
- 金币: 3637.1
- 散金: 252
- 红花: 22
- 帖子: 988
- 在线: 1224.9小时
- 虫号: 961933
- 注册: 2010-03-05
- 专业: 凝聚态物性 II ：电子结构
2楼2014-08-04 21:46:14
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
5