PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] approximation

看板Prob_Solve (計算數學 Problem Solving)作者nayd (Mr.洋芋片)時間12年前 (2012/05/21 03:21)推噓1(1推 0噓 4→)

留言5則, 2人參與討論串2/2 (看更多)

我假設每個點有編號所以不會重覆選同個點則此演算法為： 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)