作者nayd (Mr.洋芋片)
站內Prob_Solve
標題Re: [問題] approximation
時間Mon May 21 03:21:11 2012
我假設每個點有編號 所以不會重覆選同個點
則此演算法為：
let N = # of edges at the cut
for all v in S
check all edges of v, say (u,v)
let n(S) be # of such u in S.
n(T) T
if n(T) > n(S), then add v to S, N = N - n(T) + n(S)
此演算法的問題在於，不同的點的順序，會造成不同的結果
也就是題目所說的 hill-climbing
(6) V個點都看過之後 這個過程裡 每個edge恰好被看過2次
因此複雜度為O(|E|)
(7) max deg(v) / 2 (考慮一個tree)
(8) 最倒楣的順序為：每次都選到不同side的點
那麼 cut 上的 edge 數會是
2n + (2n-1) + (2n-1) + 2n + 2n + ... + (n+1) + (n+1)
= 2n + (3n-2)*(n+1)
※ 引述《DJWS (...)》之銘言：
: ※ 引述《wsx02 ()》之銘言：
: : http://ppt.cc/_7PH
: : 這是交大研究所的考題 不是作業0.0
: : 這題我找了一些答案
: : 想跟大大確認一下答案
: : (6) O(|E| * (|E|+|V|)) 或
: : O(|V| * (|E|+|V|))
: : 不知道哪個是正確的..
: 照字面看 每次V點可選，運氣不好又重複選 O(無限大)
: 最普通的 每次V點可選，檢查邊需要E，總共要選V點 O(VVE)
: 強一點的 選過的點永不再選，檢查邊需要E，總共要選V點 O(VE)
: 最強的 如果一開始先把兩點之間多重的edge拼起來 O(VV)
: 不知道考官喜歡哪一種......
: : (7) 1/2 或
: : |E|/2
: : 不知道應該填哪一個
: E
: 運氣好的時候可以找到正解
: 運氣好是什麼時候呢？ 正解最大會是多少呢？
: 例如下面那題的完全二分圖 :p
: : (8) 找到的是2n^2 可是不是很確定
: : 謝謝
: 完全二分圖(X,Y)一定可以找到正解
: 抓一個點過去 ---> a. 與X同側: 邊數為零，不會增加邊，所以最後啥都沒做
: b. 與Y同側: 因為是完全圖，一定會增加邊
: 所以答案就是 K(2n, 2n) 的邊數 2n * 2n = 4nn
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.100.250.242
※ 編輯: nayd 來自: 76.100.250.242 (05/21 03:21)
1F：推 wsx02:請問(6) 每個V被看過不是就花O(V) 每edge看兩次不是O(V*2E)? 05/21 23:32
2F：→ nayd:樓上的情況是對於每個點 去看所有的edge 06/09 10:32
3F：→ nayd:每個edge會被重覆看|V|次 所以不是這樣的 06/09 10:34
4F：→ nayd:應該是 每個v 去看跟它相鄰的v 所以頂多O(V^2) 06/09 10:37
5F：→ nayd:仔細算的話只有O(|E|) 這個小於O(|V|^2)所以比較tight 06/09 10:39