Re: [問題] approximation

[nayd (Mr.洋芋片)]

我假設每個點有編號 所以不會重覆選同個點

則此演算法為：

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)
推 wsx02:請問(6) 每個V被看過不是就花O(V) 每edge看兩次不是O(V*2E)?
→ nayd:樓上的情況是對於每個點 去看所有的edge
→ nayd:每個edge會被重覆看|V|次  所以不是這樣的
→ nayd:應該是 每個v 去看跟它相鄰的v 所以頂多O(V^2)
→ nayd:仔細算的話只有O(|E|)  這個小於O(|V|^2)所以比較tight