 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 查看: 1217 | 回復(fù): 15 | ||
[求助]
萬能的小木蟲，幫幫我吧， 一個類似 terminal Steiner tree problem問題
|
|
有一個無向圖G(v,e),假設(shè)有V有100個頂點。 我現(xiàn)在給定一個n,比如10， 那么，以葉子節(jié)點建立一個子圖，子圖是以V中任意n個葉子連接建立的最小生成樹。 請問建立這個最小生成樹問題是不是一個NP hard問題，有沒有相關(guān)的NP問題，用以證明。 查了些文獻，似乎是一個 terminal Steiner tree problem，但區(qū)別是那個頂點的子集是給定的，而我這個問題只是確定數(shù)量。這個更不一定，是不是可以這樣說，他那個是np, 我這個就更是np了，假如葉子有m個點，就是多了Cm,n倍而已。 [ Last edited by zhangwzh on 2012-7-25 at 10:54 ] |
回復(fù)此樓» 猜你喜歡
285化工學(xué)碩求調(diào)劑（081700）
已經(jīng)有10人回復(fù)
-
求材料調(diào)劑
已經(jīng)有10人回復(fù)
-
本科鄭州大學(xué)物理學(xué)院，一志愿華科070200學(xué)碩，346求調(diào)劑
已經(jīng)有4人回復(fù)
-
國自科面上基金字體
已經(jīng)有8人回復(fù)
-
能源材料化學(xué)課題組招收碩士研究生8-10名
已經(jīng)有11人回復(fù)
-
材料專碩英一數(shù)二306
已經(jīng)有5人回復(fù)
-
085600材料與化工調(diào)劑 324分
已經(jīng)有9人回復(fù)
-
0703化學(xué)調(diào)劑
已經(jīng)有12人回復(fù)
-
0703化學(xué) 305求調(diào)劑
已經(jīng)有4人回復(fù)
-
0703化學(xué)調(diào)劑，求各位老師收留
已經(jīng)有10人回復(fù)
dybo
木蟲 (正式寫手)
- 應(yīng)助: 8 (幼兒園)
- 金幣: 5500.2
- 散金: 134
- 紅花: 43
- 帖子: 625
- 在線: 239.9小時
- 蟲號: 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小時
- 蟲號: 1161736
- 注冊: 2010-12-03
- 性別: GG
- 專業(yè): 計算機科學(xué)的基礎(chǔ)理論
zhangwzh6樓2012-08-11 04:31:20
|
謝謝關(guān)心。 數(shù)學(xué)不好，我大概描述下： 給定一個無向帶權(quán)樹G(V,E),對于每一條相鄰的邊(u,v)∈E,其權(quán)值w(u,v)為1，對不相鄰的兩個節(jié)點m,n, 其w(m,n)為在G上的邊全之和（等于跳數(shù)）；設(shè)有G中全部葉子節(jié)點的集合Vs（Vs中結(jié)點個數(shù)大于V’）；一棵給定結(jié)構(gòu)的樹G’(V’,E’)，初始化E’權(quán)值均為0；是否存在這樣的一個映射f：對于每個V’中的節(jié)點u映射到子集Vs節(jié)點us，對于樹G’中E’，設(shè)(u,v)∈E’,則用w(us,vs)表示連接u、v節(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小時
- 蟲號: 1161736
- 注冊: 2010-12-03
- 性別: GG
- 專業(yè): 計算機科學(xué)的基礎(chǔ)理論
【答案】應(yīng)助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
zhangwzh: 金幣+20, ★★★★★最佳答案, 謝謝啊，有空一定看看圖論，就是一直沒時間�。� 2012-08-22 09:04:35
zhangwzh: 金幣+20, ★★★★★最佳答案, 謝謝啊，有空一定看看圖論，就是一直沒時間�。� 2012-08-22 09:04:35
|
這個問題顯然是NP-hard的。因為maxi leaf spanning tree是這個問題的special case, 而maxi leaf spanning tree是NP-hard的。但是是NP-complete的可能行不大。 你可以到google 搜索maxi leaf spanning tree的定義。 不過我覺得你要想學(xué)這些，要先把圖論好好看看。因為定義了三次，可是第三次的定義也不是很嚴謹。其實你的問題可以描述成：給定一個邊帶權(quán)圖，求解該圖的含有M個葉子節(jié)點且總權(quán)值最小的子樹。 |
9樓2012-08-22 00:16:16
10樓2012-08-22 09:29:54
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 zhangwzh 的主題更新
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 0703化學(xué)調(diào)劑，求各位老師收留 +10 | 秋有木北 2026-03-14 | 10/500 |
|
|---|---|---|---|---|
|
[考研] 281求調(diào)劑（0805） +6 | 煙汐憶海 2026-03-16 | 16/800 |
|
|
|
[考研] 311求調(diào)劑 +4 | 冬十三 2026-03-18 | 4/200 |
|
|
|
[考研] 328求調(diào)劑，英語六級551，有科研經(jīng)歷 +3 | 生物工程調(diào)劑 2026-03-17 | 7/350 |
|
|
|
[考研] 一志愿西南交大，求調(diào)劑 +4 | 材化逐夢人 2026-03-18 | 4/200 |
|
|
|
[考研]
 0854，計算機類招收調(diào)劑
+3
|
胡辣湯放糖 2026-03-15 | 6/300 |
|
|
|
[考研] 材料，紡織，生物（0856、0710），化學(xué)招生啦 +3 | Eember. 2026-03-17 | 9/450 |
|
|
|
[考研] 考研求調(diào)劑 +3 | 橘頌. 2026-03-17 | 4/200 |
|
|
|
[考研] 085601求調(diào)劑 +4 | Du.11 2026-03-16 | 4/200 |
|
|
|
[考研] 26考研求調(diào)劑 +6 | 丶宏Sir 2026-03-13 | 6/300 |
|
|
|
[考研] 考研調(diào)劑 +3 | 淇ya_~ 2026-03-17 | 5/250 |
|
|
|
[考研] 304求調(diào)劑 +3 | 曼殊2266 2026-03-14 | 3/150 |
|
|
|
[考研] 070303 總分349求調(diào)劑 +3 | LJY9966 2026-03-15 | 5/250 |
|
|
|
[考研] 326求調(diào)劑 +3 | mlpqaz03 2026-03-15 | 3/150 |
|
|
|
[考研] 294求調(diào)劑 +3 | Zys010410@ 2026-03-13 | 4/200 |
|
|
|
[考研] 265求調(diào)劑 +4 | 威化餅07 2026-03-12 | 4/200 |
|
|
|
[考研] 一志愿哈工大材料324分求調(diào)劑 +5 | 閆旭東 2026-03-14 | 5/250 |
|
|
|
[考研] 求材料調(diào)劑 085600英一數(shù)二總分302 前三科235 精通機器學(xué)習(xí) 一志愿哈工大 +4 | 林yaxin 2026-03-12 | 4/200 |
|
|
|
[考研] 308求調(diào)劑 +3 | 是Lupa啊 2026-03-12 | 3/150 |
|
|
|
[考研] 070303一志愿西北大學(xué)學(xué)碩310找調(diào)劑 +3 | d如愿上岸 2026-03-13 | 3/150 |
|