| 查看: 1904 | 回复: 8 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
JUST_ME_ME铁虫 (小有名气)
|
[交流]
关于顶点覆盖算法的一些问题
|
||
|
由于课题需要一直在研究一些关于顶点覆盖的算法，自己也查看文献实践了一些，但发现效果并不是很好，但也拿出来和大家共同分享一下，同时期盼能够各位能给出好的意见。 顶点覆盖是图论中的经典组合优化问题，我所研究的是无向简单图的顶点覆盖。 问题描述如下：图中有n个点（点可以代表事件，代表物体等等），把有关系的点相连形成边，设边数为m；这样就得到一个G（n,m）的无向图，如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。 目前楼主使用了一种比较常用易于理解的算法，最大度贪婪算法。 找到图中度最大的顶点，放入C,删除其以及与其关联的边，形成新的图，再继续以上操作，知道最大度为零，结束。 但结果不是很好，精准度较差，如有研究图论的大师，请跳出来，指点迷津~~ |
回复此楼» 猜你喜欢
写了一篇“相变储能技术在冷库中应用”的论文，论文内容以实验为主，投什么期刊合适？
已经有5人回复
-
带资进组求博导收留
已经有10人回复
-
最近几年招的学生写论文不引自己组发的文章
已经有11人回复
-
需要合成515-64-0，50g，能接单的留言
已经有3人回复
-
中科院杭州医学所招收博士生一名（生物分析化学、药物递送）
已经有3人回复
-
临港实验室与上科大联培博士招生1名
已经有8人回复
-
想换工作。大多数高校都是 评职称时 认可5年内在原单位取得的成果吗？
已经有4人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 有限单群：一段百年征程
已经有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