 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 2035 | 回復(fù): 8 | |||
JUST_ME_ME鐵蟲(chóng) (小有名氣)
|
[交流]
關(guān)于頂點(diǎn)覆蓋算法的一些問(wèn)題
|
|
由于課題需要一直在研究一些關(guān)于頂點(diǎn)覆蓋的算法，自己也查看文獻(xiàn)實(shí)踐了一些，但發(fā)現(xiàn)效果并不是很好，但也拿出來(lái)和大家共同分享一下，同時(shí)期盼能夠各位能給出好的意見(jiàn)。 頂點(diǎn)覆蓋是圖論中的經(jīng)典組合優(yōu)化問(wèn)題，我所研究的是無(wú)向簡(jiǎn)單圖的頂點(diǎn)覆蓋。 問(wèn)題描述如下：圖中有n個(gè)點(diǎn)（點(diǎn)可以代表事件，代表物體等等），把有關(guān)系的點(diǎn)相連形成邊，設(shè)邊數(shù)為m；這樣就得到一個(gè)G（n,m）的無(wú)向圖，如何求得元素最少的集合C使得其內(nèi)包含的點(diǎn)可以覆蓋整個(gè)圖是問(wèn)題的關(guān)鍵。 目前樓主使用了一種比較常用易于理解的算法，最大度貪婪算法。 找到圖中度最大的頂點(diǎn)，放入C,刪除其以及與其關(guān)聯(lián)的邊，形成新的圖，再繼續(xù)以上操作，知道最大度為零，結(jié)束。 但結(jié)果不是很好，精準(zhǔn)度較差，如有研究圖論的大師，請(qǐng)?zhí)鰜?lái)，指點(diǎn)迷津~~ |
回復(fù)此樓» 猜你喜歡
284求調(diào)劑
已經(jīng)有10人回復(fù)
-
一志愿山東大學(xué)藥學(xué)學(xué)碩求調(diào)劑
已經(jīng)有4人回復(fù)
-
07化學(xué)280分求調(diào)劑
已經(jīng)有4人回復(fù)
-
298-一志愿中國(guó)農(nóng)業(yè)大學(xué)-求調(diào)劑
已經(jīng)有12人回復(fù)
-
求材料，環(huán)境專(zhuān)業(yè)調(diào)劑
已經(jīng)有3人回復(fù)
-
335求調(diào)劑
已經(jīng)有5人回復(fù)
-
求調(diào)劑
已經(jīng)有7人回復(fù)
-
一志愿吉大化學(xué)322求調(diào)劑
已經(jīng)有4人回復(fù)
-
環(huán)境學(xué)碩288求調(diào)劑
已經(jīng)有8人回復(fù)
-
341求調(diào)劑(一志愿湖南大學(xué)070300)
已經(jīng)有6人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 有限單群：一段百年征程
已經(jīng)有11人回復(fù)
銳利的碎片
木蟲(chóng) (正式寫(xiě)手)
star watcher
- 應(yīng)助: 136 (高中生)
- 金幣: 3637.1
- 散金: 252
- 紅花: 22
- 帖子: 988
- 在線: 1224.9小時(shí)
- 蟲(chóng)號(hào): 961933
- 注冊(cè): 2010-03-05
- 專(zhuān)業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)
2樓2014-08-04 21:46:14
JUST_ME_ME
鐵蟲(chóng) (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 42.7
- 紅花: 1
- 帖子: 106
- 在線: 63.8小時(shí)
- 蟲(chóng)號(hào): 3343845
- 注冊(cè): 2014-07-29
- 性別: MM
- 專(zhuān)業(yè): 傳動(dòng)機(jī)械學(xué)
3樓2014-08-05 11:19:13
4樓2014-08-05 20:31:19
JUST_ME_ME
鐵蟲(chóng) (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 42.7
- 紅花: 1
- 帖子: 106
- 在線: 63.8小時(shí)
- 蟲(chóng)號(hào): 3343845
- 注冊(cè): 2014-07-29
- 性別: MM
- 專(zhuān)業(yè): 傳動(dòng)機(jī)械學(xué)
5樓2014-08-06 15:21:20
6樓2014-08-06 16:30:58
JUST_ME_ME
鐵蟲(chóng) (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 42.7
- 紅花: 1
- 帖子: 106
- 在線: 63.8小時(shí)
- 蟲(chóng)號(hào): 3343845
- 注冊(cè): 2014-07-29
- 性別: MM
- 專(zhuān)業(yè): 傳動(dòng)機(jī)械學(xué)
7樓2014-08-07 16:09:21
Macer3
銅蟲(chóng) (初入文壇)
- 應(yīng)助: 2 (幼兒園)
- 金幣: 481.3
- 散金: 100
- 帖子: 43
- 在線: 20.2小時(shí)
- 蟲(chóng)號(hào): 3235666
- 注冊(cè): 2014-05-26
- 性別: GG
- 專(zhuān)業(yè): 交通工程
8樓2014-08-08 23:08:31
Macer3
銅蟲(chóng) (初入文壇)
- 應(yīng)助: 2 (幼兒園)
- 金幣: 481.3
- 散金: 100
- 帖子: 43
- 在線: 20.2小時(shí)
- 蟲(chóng)號(hào): 3235666
- 注冊(cè): 2014-05-26
- 性別: GG
- 專(zhuān)業(yè): 交通工程
★
小木蟲(chóng): 金幣+0.5, 給個(gè)紅包，謝謝回帖
小木蟲(chóng): 金幣+0.5, 給個(gè)紅包，謝謝回帖
|
好吧，我算出來(lái)了，用0-1規(guī)劃。 目標(biāo)min=sum（v）， st. A’*v>=1 v為頂點(diǎn)構(gòu)成的0—1列向量，0表示不選該點(diǎn)，1表示選中該點(diǎn)。A 為關(guān)聯(lián)矩陣的轉(zhuǎn)置（注意，不是鄰接矩陣）。用lingo很好解的，100個(gè)頂點(diǎn)不在話下。如果想加快一點(diǎn)速度可以再加一些簡(jiǎn)單的限制范圍的約束。 [ 發(fā)自手機(jī)版 http://www.gaoyang168.com/3g ] |
9樓2014-08-23 06:54:44
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 JUST_ME_ME 的主題更新
| 9 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 284求調(diào)劑 +3 | yanzhixue111 2026-03-23 | 6/300 |
|
|---|---|---|---|---|
|
[考研] 生物學(xué)學(xué)碩求調(diào)劑 +4 | 小羊睡著了? 2026-03-23 | 4/200 |
|
|
|
[考研] 一志愿重慶大學(xué)085700資源與環(huán)境，總分308求調(diào)劑 +7 | 墨墨漠 2026-03-23 | 8/400 |
|
|
|
[考研]
 材料與化工考研調(diào)劑
+4
|
孅華 2026-03-22 | 4/200 |
|
|
|
[考研] 求老師收我 +3 | zzh16938784 2026-03-23 | 3/150 |
|
|
|
[考研] 298求調(diào)劑 +8 | 上岸6666@ 2026-03-20 | 8/400 |
|
|
|
[考研] 323求調(diào)劑 +6 | 洼小桶 2026-03-18 | 6/300 |
|
|
|
[考研] 求調(diào)劑 +7 | Auroracx 2026-03-22 | 7/350 |
|
|
|
[考博] 招收博士1-2人 +3 | QGZDSYS 2026-03-18 | 4/200 |
|
|
|
[考研] 求調(diào)劑 +4 | 要好好無(wú)聊 2026-03-21 | 4/200 |
|
|
|
[考研] 266求調(diào)劑 +3 | 哇呼哼呼哼 2026-03-20 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +3 | 白QF 2026-03-21 | 3/150 |
|
|
|
[考研] 332求調(diào)劑 +3 | 鳳凰院丁真 2026-03-20 | 3/150 |
|
|
|
[考研] 265求調(diào)劑 +3 | Jack?k?y 2026-03-17 | 3/150 |
|
|
|
[考研] 083200學(xué)碩321分一志愿暨南大學(xué)求調(diào)劑 +3 | innocenceF 2026-03-17 | 3/150 |
|
|
|
[考研] 304求調(diào)劑 +6 | 曼殊2266 2026-03-18 | 6/300 |
|
|
|
[考研] 中南大學(xué)化學(xué)學(xué)碩337求調(diào)劑 +3 | niko- 2026-03-19 | 6/300 |
|
|
|
[考研] 求調(diào)劑一志愿南京航空航天大學(xué)289分 +3 | @taotao 2026-03-19 | 3/150 |
|
|
|
[考研] 261求B區(qū)調(diào)劑，科研經(jīng)歷豐富 +3 | 牛奶很忙 2026-03-20 | 4/200 |
|
|
|
[考博] 申博26年 +3 | 八6八68 2026-03-19 | 3/150 |
|