应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » C/C++ » 关于顶点覆盖算法的一些问题
北京石油化工学院2026年研究生招生接收调剂公告
91/1返回列表
查看: 2059  |  回复: 8
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

JUST_ME_ME

铁虫 (小有名气)

[交流] 关于顶点覆盖算法的一些问题

由于课题需要一直在研究一些关于顶点覆盖的算法，自己也查看文献实践了一些，但发现效果并不是很好，但也拿出来和大家共同分享一下，同时期盼能够各位能给出好的意见。
             顶点覆盖是图论中的经典组合优化问题，我所研究的是无向简单图的顶点覆盖。
            问题描述如下：图中有n个点（点可以代表事件，代表物体等等），把有关系的点相连形成边，设边数为m；这样就得到一个G（n,m）的无向图，如何求得元素最少的集合C使得其内包含的点可以覆盖整个图是问题的关键。
           目前楼主使用了一种比较常用易于理解的算法，最大度贪婪算法。
          找到图中度最大的顶点，放入C,删除其以及与其关联的边，形成新的图，再继续以上操作，知道最大度为零，结束。
          但结果不是很好，精准度较差，如有研究图论的大师，请跳出来，指点迷津~~
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
tobebetter
1楼 2014-08-04 18:44:41
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

锐利的碎片

木虫 (正式写手)

star watcher
★ ★
小木虫: 金币+0.5, 给个红包，谢谢回帖
jjdg: 金币+1, 感谢参与 2014-08-05 07:23:36
我记得这是NP完备的，应该只有近似算法。
赞一下(1人) 回复此楼
2楼2014-08-04 21:46:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

JUST_ME_ME

铁虫 (小有名气)
引用回帖:
2楼: Originally posted by 锐利的碎片 at 2014-08-04 21:46:14
我记得这是NP完备的，应该只有近似算法。

近似算法和启发算法适用，我选的是最大度贪婪算法，计算结果不堪入目的说，100的顶点要找第91个才能全部覆盖。。
赞一下(2人) 回复此楼
tobebetter
3楼2014-08-05 11:19:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hc315

铁虫 (小有名气)
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
求优化解，随便抓出一个智能算法都可以做
赞一下 回复此楼
4楼2014-08-05 20:31:19
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

JUST_ME_ME

铁虫 (小有名气)
引用回帖:
4楼: Originally posted by hc315 at 2014-08-05 20:31:19
求优化解，随便抓出一个智能算法都可以做

用c实现智能算法会不会很难？
赞一下 回复此楼
tobebetter
5楼2014-08-06 15:21:20
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hc315

铁虫 (小有名气)
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
引用回帖:
5楼: Originally posted by JUST_ME_ME at 2014-08-06 15:21:20
用c实现智能算法会不会很难？...

没啥难度，只不过比matlab多敲些代码罢了
赞一下 回复此楼
6楼2014-08-06 16:30:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

JUST_ME_ME

铁虫 (小有名气)
引用回帖:
6楼: Originally posted by hc315 at 2014-08-06 16:30:58
没啥难度，只不过比matlab多敲些代码罢了...

大师，给指条路吧~~~~~~~~~~~~~~
赞一下 回复此楼
tobebetter
7楼2014-08-07 16:09:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

Macer3

铜虫 (初入文坛)
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
内容已删除
回复此楼
8楼2014-08-08 23:08:31
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

Macer3

铜虫 (初入文坛)
★
小木虫: 金币+0.5, 给个红包，谢谢回帖
好吧，我算出来了，用0-1规划。
目标min=sum（v），
st.   A’*v>=1   
v为顶点构成的0—1列向量，0表示不选该点，1表示选中该点。A 为关联矩阵的转置（注意，不是邻接矩阵）。用lingo很好解的，100个顶点不在话下。如果想加快一点速度可以再加一些简单的限制范围的约束。

[ 发自手机版 http://muchong.com/3g ]
赞一下 回复此楼
9楼2014-08-23 06:54:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 JUST_ME_ME 的主题更新
91/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 一志愿 南京航空航天大学 ，080500材料科学与工程学硕 +4 @taotao 2026-03-30 4/200 2026-03-31 04:04 by zhyzzh
[考研] 083000学硕274求调剂 +10 Li李鱼 2026-03-26 10/500 2026-03-31 03:31 by 蒙奇奇521
[考研] 求调剂，一志愿 南京航空航天大学 ，080500材料科学与工程学硕，总分289分 +9 @taotao 2026-03-29 9/450 2026-03-30 22:29 by 我是小康
[考研] 291求调剂 +8 Y-cap 2026-03-29 11/550 2026-03-30 21:03 by Y-cap
[考研] 292求调剂 +13 是妍子也是研子 2026-03-30 13/650 2026-03-30 18:01 by 小徐0109
[考研] 334分 一志愿武理 材料求调剂 +16 李李不服输 2026-03-26 16/800 2026-03-30 17:47 by wangjy2002
[考研] 310求调剂 +10 争取九点睡 2026-03-30 10/500 2026-03-30 16:45 by ztnimte
[考研] 求调剂323材料与化工 +10 1124361 2026-03-24 10/500 2026-03-30 16:26 by 690616278
[考研] 348求调剂 +6 小懒虫不懒了 2026-03-28 6/300 2026-03-30 10:29 by Evan_Liu
[考研] 337求调剂 +6 《树》 2026-03-29 6/300 2026-03-30 10:15 by herarysara
[考研] 求调剂 +10 张zz111 2026-03-27 11/550 2026-03-30 09:17 by 无际的草原
[考研] 材料与化工304求B区调剂 +4 邱gl 2026-03-26 7/350 2026-03-30 08:39 by 探123
[考研] 290求调剂 +3 dfffsar 2026-03-29 3/150 2026-03-29 22:38 by 毛毛毛阿莫2
[考研] 一志愿南昌大学324求调剂 +5 hanamiko 2026-03-29 5/250 2026-03-29 16:46 by 学员8dgXkO
[考研] 340求调剂 +6 Amber00 2026-03-26 6/300 2026-03-29 12:06 by 无际的草原
[考研] 343求调剂 +6 爱羁绊 2026-03-29 6/300 2026-03-29 12:00 by 无际的草原
[考研] 348求调剂 +4 小懒虫不懒了 2026-03-27 5/250 2026-03-27 12:47 by 果果妈咪
[考研] 机械学硕总分317求调剂！！！！ +4 Acaciad 2026-03-25 4/200 2026-03-25 19:59 by hanserlol
[考研] 考研一志愿苏州大学初始315（英一）求调剂 +3 sbdksD 2026-03-24 4/200 2026-03-25 18:16 by xcjcqu
[考研] 293求调剂 +7 加一一九 2026-03-24 7/350 2026-03-25 12:02 by userper
信息提示
关闭
请填处理意见
关闭