 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 9 | 1/1 | 返回列表 |
| 查看: 2036 | 回復(fù): 8 | |||
JUST_ME_ME鐵蟲 (小有名氣)
|
[交流]
關(guān)于頂點(diǎn)覆蓋算法的一些問題
|
|
由于課題需要一直在研究一些關(guān)于頂點(diǎn)覆蓋的算法，自己也查看文獻(xiàn)實(shí)踐了一些，但發(fā)現(xiàn)效果并不是很好，但也拿出來和大家共同分享一下，同時(shí)期盼能夠各位能給出好的意見。 頂點(diǎn)覆蓋是圖論中的經(jīng)典組合優(yōu)化問題，我所研究的是無向簡(jiǎn)單圖的頂點(diǎn)覆蓋。 問題描述如下：圖中有n個(gè)點(diǎn)（點(diǎn)可以代表事件，代表物體等等），把有關(guān)系的點(diǎn)相連形成邊，設(shè)邊數(shù)為m；這樣就得到一個(gè)G（n,m）的無向圖，如何求得元素最少的集合C使得其內(nèi)包含的點(diǎn)可以覆蓋整個(gè)圖是問題的關(guān)鍵。 目前樓主使用了一種比較常用易于理解的算法，最大度貪婪算法。 找到圖中度最大的頂點(diǎn)，放入C,刪除其以及與其關(guān)聯(lián)的邊，形成新的圖，再繼續(xù)以上操作，知道最大度為零，結(jié)束。 但結(jié)果不是很好，精準(zhǔn)度較差，如有研究圖論的大師，請(qǐng)?zhí)鰜�，指點(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-一志愿中國農(nóng)業(yè)大學(xué)-求調(diào)劑
已經(jīng)有12人回復(fù)
-
求材料，環(huá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ù)
銳利的碎片
木蟲 (正式寫手)
star watcher
- 應(yīng)助: 136 (高中生)
- 金幣: 3637.1
- 散金: 252
- 紅花: 22
- 帖子: 988
- 在線: 1224.9小時(shí)
- 蟲號(hào): 961933
- 注冊(cè): 2010-03-05
- 專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)
2樓2014-08-04 21:46:14
JUST_ME_ME
鐵蟲 (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 42.7
- 紅花: 1
- 帖子: 106
- 在線: 63.8小時(shí)
- 蟲號(hào): 3343845
- 注冊(cè): 2014-07-29
- 性別: MM
- 專業(yè): 傳動(dòng)機(jī)械學(xué)
3樓2014-08-05 11:19:13
4樓2014-08-05 20:31:19
JUST_ME_ME
鐵蟲 (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 42.7
- 紅花: 1
- 帖子: 106
- 在線: 63.8小時(shí)
- 蟲號(hào): 3343845
- 注冊(cè): 2014-07-29
- 性別: MM
- 專業(yè): 傳動(dòng)機(jī)械學(xué)
5樓2014-08-06 15:21:20
6樓2014-08-06 16:30:58
JUST_ME_ME
鐵蟲 (小有名氣)
- 應(yīng)助: 0 (幼兒園)
- 金幣: 42.7
- 紅花: 1
- 帖子: 106
- 在線: 63.8小時(shí)
- 蟲號(hào): 3343845
- 注冊(cè): 2014-07-29
- 性別: MM
- 專業(yè): 傳動(dòng)機(jī)械學(xué)
7樓2014-08-07 16:09:21
Macer3
銅蟲 (初入文壇)
- 應(yīng)助: 2 (幼兒園)
- 金幣: 481.3
- 散金: 100
- 帖子: 43
- 在線: 20.2小時(shí)
- 蟲號(hào): 3235666
- 注冊(cè): 2014-05-26
- 性別: GG
- 專業(yè): 交通工程
8樓2014-08-08 23:08:31
Macer3
銅蟲 (初入文壇)
- 應(yīng)助: 2 (幼兒園)
- 金幣: 481.3
- 散金: 100
- 帖子: 43
- 在線: 20.2小時(shí)
- 蟲號(hào): 3235666
- 注冊(cè): 2014-05-26
- 性別: GG
- 專業(yè): 交通工程
★
小木蟲: 金幣+0.5, 給個(gè)紅包，謝謝回帖
小木蟲: 金幣+0.5, 給個(gè)紅包，謝謝回帖
|
好吧，我算出來了，用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ā)表 | |
|---|---|---|---|---|
|
[考研] 361求調(diào)劑 +3 | Glack 2026-03-22 | 3/150 |
|
|---|---|---|---|---|
|
|
[考研] 265求調(diào)劑 +10 | 梁梁校校 2026-03-17 | 10/500 |
|
|
|
[考研] 一志愿武理材料工程348求調(diào)劑 +6 | ￣^￣゜汗 2026-03-19 | 9/450 |
|
|
|
[考研] 336求調(diào)劑 +4 | 收到VS 2026-03-20 | 4/200 |
|
|
[考研] 考研化學(xué)308分求調(diào)劑 +7 | 你好明天你好 2026-03-23 | 8/400 |
|
|
|
[考研] 0854電子信息求調(diào)劑 324 +3 | Promise-jyl 2026-03-23 | 3/150 |
|
|
|
[考研] 291求調(diào)劑 +5 | 孅華 2026-03-22 | 5/250 |
|
|
|
[考研] 280分求調(diào)劑 一志愿085802 +4 | PUMPT 2026-03-22 | 7/350 |
|
|
|
[考研] 287求調(diào)劑 +8 | 晨昏線與星海 2026-03-19 | 9/450 |
|
|
|
[考研] 324求調(diào)劑 +6 | lucky呀呀呀鴨 2026-03-20 | 6/300 |
|
|
|
[考研] 289求調(diào)劑 +7 | 懷瑾握瑜l 2026-03-20 | 7/350 |
|
|
|
[考研] 286求調(diào)劑 +10 | Faune 2026-03-21 | 10/500 |
|
|
|
[考研] 一志愿重慶大學(xué)085700資源與環(huán)境總分308求調(diào)劑 +7 | 墨墨漠 2026-03-20 | 7/350 |
|
|
|
[考研] 085700資源與環(huán)境308求調(diào)劑 +12 | 墨墨漠 2026-03-18 | 13/650 |
|
|
|
[考研] 一志愿華南師大 070300（化學(xué)）304分求調(diào)劑 +3 | 0703武芊慧雪304 2026-03-18 | 3/150 |
|
|
|
[考研] 一志愿 南京航空航天大學(xué)大學(xué) ，080500材料科學(xué)與工程學(xué)碩 +5 | @taotao 2026-03-20 | 5/250 |
|
|
|
[考研] 261求B區(qū)調(diào)劑，科研經(jīng)歷豐富 +3 | 牛奶很忙 2026-03-20 | 4/200 |
|
|
|
[論文投稿]
申請(qǐng)回稿延期一個(gè)月，編輯同意了。但系統(tǒng)上的時(shí)間沒變，給編輯又寫郵件了，沒回復(fù)
 10+3
|
wangf9518 2026-03-17 | 4/200 |
|
|
|
[考研] 材料學(xué)碩318求調(diào)劑 +5 | February_Feb 2026-03-19 | 5/250 |
|
|
|
[考研] 本科鄭州大學(xué)物理學(xué)院，一志愿華科070200學(xué)碩，346求調(diào)劑 +4 | 我不是一根蔥 2026-03-18 | 4/200 |
|