 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 查看: 1215 | 回復(fù): 15 | ||
[求助]
萬能的小木蟲，幫幫我吧， 一個(gè)類似 terminal Steiner tree problem問題
|
|
有一個(gè)無向圖G(v,e),假設(shè)有V有100個(gè)頂點(diǎn)。 我現(xiàn)在給定一個(gè)n,比如10， 那么，以葉子節(jié)點(diǎn)建立一個(gè)子圖，子圖是以V中任意n個(gè)葉子連接建立的最小生成樹。 請問建立這個(gè)最小生成樹問題是不是一個(gè)NP hard問題，有沒有相關(guān)的NP問題，用以證明。 查了些文獻(xiàn)，似乎是一個(gè) terminal Steiner tree problem，但區(qū)別是那個(gè)頂點(diǎn)的子集是給定的，而我這個(gè)問題只是確定數(shù)量。這個(gè)更不一定，是不是可以這樣說，他那個(gè)是np, 我這個(gè)就更是np了，假如葉子有m個(gè)點(diǎn)，就是多了Cm,n倍而已。 [ Last edited by zhangwzh on 2012-7-25 at 10:54 ] |
回復(fù)此樓» 猜你喜歡
271材料工程求調(diào)劑
已經(jīng)有5人回復(fù)
-
281求調(diào)劑（0805）
已經(jīng)有16人回復(fù)
-
304求調(diào)劑
已經(jīng)有6人回復(fù)
-
材料工程專碩調(diào)劑
已經(jīng)有6人回復(fù)
-
一志愿天大材料與化工（085600）總分338
已經(jīng)有4人回復(fù)
-
085700資源與環(huán)境308求調(diào)劑
已經(jīng)有3人回復(fù)
-
求材料調(diào)劑
已經(jīng)有8人回復(fù)
-
294求調(diào)劑材料與化工專碩
已經(jīng)有5人回復(fù)
-
一志愿華中科技大學(xué)，080502，354分求調(diào)劑
已經(jīng)有4人回復(fù)
-
一志愿吉林大學(xué)材料學(xué)碩321求調(diào)劑
已經(jīng)有6人回復(fù)
dybo
木蟲 (正式寫手)
- 應(yīng)助: 8 (幼兒園)
- 金幣: 5500.2
- 散金: 134
- 紅花: 43
- 帖子: 625
- 在線: 239.9小時(shí)
- 蟲號: 897154
- 注冊: 2009-11-08
- 性別: GG
- 專業(yè): 草地科學(xué)
2樓2012-08-10 12:04:38
3樓2012-08-10 12:10:49
4樓2012-08-10 12:11:26
5樓2012-08-10 12:13:11
gen007gen
木蟲 (正式寫手)
- 應(yīng)助: 28 (小學(xué)生)
- 金幣: 4954.7
- 散金: 69
- 紅花: 3
- 帖子: 413
- 在線: 262.9小時(shí)
- 蟲號: 1161736
- 注冊: 2010-12-03
- 性別: GG
- 專業(yè): 計(jì)算機(jī)科學(xué)的基礎(chǔ)理論
zhangwzh6樓2012-08-11 04:31:20
|
謝謝關(guān)心。 數(shù)學(xué)不好，我大概描述下： 給定一個(gè)無向帶權(quán)樹G(V,E),對于每一條相鄰的邊(u,v)∈E,其權(quán)值w(u,v)為1，對不相鄰的兩個(gè)節(jié)點(diǎn)m,n, 其w(m,n)為在G上的邊全之和（等于跳數(shù)）；設(shè)有G中全部葉子節(jié)點(diǎn)的集合Vs（Vs中結(jié)點(diǎn)個(gè)數(shù)大于V’）；一棵給定結(jié)構(gòu)的樹G’(V’,E’)，初始化E’權(quán)值均為0；是否存在這樣的一個(gè)映射f：對于每個(gè)V’中的節(jié)點(diǎn)u映射到子集Vs節(jié)點(diǎn)us，對于樹G’中E’，設(shè)(u,v)∈E’,則用w(us,vs)表示連接u、v節(jié)點(diǎn)的代價(jià)，使得樹的代價(jià)最��？ |
7樓2012-08-12 15:37:37
8樓2012-08-21 15:34:33
gen007gen
木蟲 (正式寫手)
- 應(yīng)助: 28 (小學(xué)生)
- 金幣: 4954.7
- 散金: 69
- 紅花: 3
- 帖子: 413
- 在線: 262.9小時(shí)
- 蟲號: 1161736
- 注冊: 2010-12-03
- 性別: GG
- 專業(yè): 計(jì)算機(jī)科學(xué)的基礎(chǔ)理論
【答案】應(yīng)助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
zhangwzh: 金幣+20, ★★★★★最佳答案, 謝謝啊，有空一定看看圖論，就是一直沒時(shí)間�。� 2012-08-22 09:04:35
zhangwzh: 金幣+20, ★★★★★最佳答案, 謝謝啊，有空一定看看圖論，就是一直沒時(shí)間�。� 2012-08-22 09:04:35
|
這個(gè)問題顯然是NP-hard的。因?yàn)閙axi leaf spanning tree是這個(gè)問題的special case, 而maxi leaf spanning tree是NP-hard的。但是是NP-complete的可能行不大。 你可以到google 搜索maxi leaf spanning tree的定義。 不過我覺得你要想學(xué)這些，要先把圖論好好看看。因?yàn)槎x了三次，可是第三次的定義也不是很嚴(yán)謹(jǐn)。其實(shí)你的問題可以描述成：給定一個(gè)邊帶權(quán)圖，求解該圖的含有M個(gè)葉子節(jié)點(diǎn)且總權(quán)值最小的子樹。 |
9樓2012-08-22 00:16:16
10樓2012-08-22 09:29:54
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 zhangwzh 的主題更新
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 085600材料與化工調(diào)劑 324分 +8 | llllkkkhh 2026-03-18 | 8/400 |
|
|---|---|---|---|---|
|
[考研] 267一志愿南京工業(yè)大學(xué)0817化工求調(diào)劑 +8 | SUICHILD 2026-03-12 | 8/400 |
|
|
|
[考研] 26調(diào)劑/材料/英一數(shù)二/總分289/已過A區(qū)線 +7 | 步川酷紫123 2026-03-13 | 7/350 |
|
|
|
[教師之家] 焦慮 +8 | 水冰月月野兔 2026-03-13 | 12/600 |
|
|
|
[考研] 280求調(diào)劑 +6 | 咕嚕曉曉 2026-03-18 | 7/350 |
|
|
|
[考研] 0703化學(xué)調(diào)劑 +3 | 妮妮ninicgb 2026-03-17 | 3/150 |
|
|
|
[考研] 268求調(diào)劑 +6 | 簡單點(diǎn)0 2026-03-17 | 6/300 |
|
|
|
[考研] 考研求調(diào)劑 +3 | 橘頌. 2026-03-17 | 4/200 |
|
|
|
[考研] 268求調(diào)劑 +8 | 一定有學(xué)上- 2026-03-14 | 9/450 |
|
|
|
[考研] 梁成偉老師課題組歡迎你的加入 +8 | 一鴨鴨喲 2026-03-14 | 10/500 |
|
|
|
[考研] 一志愿蘇州大學(xué)材料工程（085601）專碩有科研經(jīng)歷三項(xiàng)國獎(jiǎng)兩個(gè)實(shí)用型專利一項(xiàng)省級立項(xiàng) +6 | 大火山小火山 2026-03-16 | 8/400 |
|
|
|
[考研] 0854控制工程 359求調(diào)劑 可跨專業(yè) +3 | 626776879 2026-03-14 | 9/450 |
|
|
|
[基金申請]
今年的國基金是打分制嗎？
 50+3
|
zhanghaozhu 2026-03-14 | 3/150 |
|
|
|
[考研] 070300化學(xué)學(xué)碩求調(diào)劑 +6 | 太想進(jìn)步了0608 2026-03-16 | 6/300 |
|
|
|
[考研] 285求調(diào)劑 +6 | ytter 2026-03-12 | 6/300 |
|
|
|
[考研] 0703 物理化學(xué)調(diào)劑 +3 | 我可以上岸的對?/a> 2026-03-13 | 5/250 |
|
|
|
[考研] 中科大材料專碩319求調(diào)劑 +3 | 孟鑫材料 2026-03-13 | 3/150 |
|
|
|
[基金申請] 現(xiàn)在如何回避去年的某一個(gè)專家，不知道名字 +3 | zk200107 2026-03-12 | 6/300 |
|
|
|
[考研] 0703化學(xué)求調(diào)劑 +7 | 綠豆芹菜湯 2026-03-12 | 7/350 |
|
|
|
[考研] 085600材料與化工 309分請求調(diào)劑 +7 | dtdxzxx 2026-03-12 | 8/400 |
|