這邊有3個演算法的觀念想請教各位板友
Q1: NP-C的證明方式 與 reduce的概念
在探討一個問題 B 是不是NP-C的時候 , 都會用reduce的手法去說明 B 比較難
以我目前的理解 , 把問題A reduce 到問題 B , 代表 B 比 A 難
我的理由: 如果要知道B是否有解,可以用符合問題A的instance,經過多項式時間內
的f轉換,得到問題B的解
以證明Longest Path是NP-C為例 :
已知難度為NP-C的 問題A : G是否有Hamilton path ?
欲證明難度為NP-C的問題B : G是否存在一simple path長度≧k
要證明問題B為NP-C須說明兩件事情
(1) 問題B 是 NP
(2) 問題B 是 NP-C (用已知的NP-C問題reduce到問題B)
我的問題 : 證明(2)是否只要說明 A→B 即可 ?
書本上看到的寫法都會證明兩邊 A <--> B , 不太能理解為什麼需要證明"必要條件"(
往左的箭頭A←B) , 如果要說明問題B比問題A難,不是只要將NP-C難度的問題A reduce
到問題B就可以說明了嗎 ?
----------------------------------------------------------------------------
Q2: 0-1 knapsack為NP的複雜度論述
書本上說明0-1背包問題的複雜度為 nW , 更確切的表示為 n2^(logW) , 因此
並不是一個多項式時間服雜度的問題 , 有點不懂黃色那個轉換的來由?
W
----------------------------
| |
n | |
| |
----------------------------
----------------------------------------------------------------------------
Q3: Minimum Spanning Tree(MST) & Flow Network
Q3-1(T or F) 如果一圖G的edge weight皆不相同 , 則G的MST唯一
Q3-2(T or F) 如果一個flow network的每個edge之capacity皆不相同 ,
則maximum flow唯一
上述兩題是我自己想到的狀況 , 想和各位板友確認
我自己覺得是 F , T
理由3-1: 假設有五根edge , weight分別為1~5 , MST包含的edge可以是
{1,5,3}或{2,3,4} , 所以應該不唯一 , 只是有點不嚴謹 , 不
曉得是否正確?
理由3-2: 可能存在數個由不同組edge組成的 min Cut , 但都對應到相同的max flow值,
是用類似3-1的情況想像的 , 不曉得是否正確? (附帶一問 , 這種說法應該
只能確保流到t的最大量,但不能確認中間的路徑走的是相同的吧?頂多保證在
cut1和cut2的edge必定flow=capacity )
| |
| |
s--->| -------> |---> t
| |
| |
cut1 cut2
(2,5) (3,4) ()內代表cut到的edge之capacity組合
謝謝大家看完 , 在麻煩大家回答了~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.77.243
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1413707220.A.050.html