作者DJWS (...)
看板Prob_Solve
標題Re: [問題] approximation
時間Tue Apr 3 22:22:02 2012
※ 引述《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: 61.230.125.83
※ 編輯: DJWS 來自: 61.230.125.83 (04/03 22:32)
1F：推 wsx02:謝謝 04/04 11:50
2F：推 yamaimo:每移動1個點,S,T之間的邊數至少增加1,最多只需要移動|E| 04/07 18:31
3F：→ yamaimo:O(|E|*(|V|+|E|))可解決。 04/07 18:37