MaxSAT random method : 0.5-approximation 6:20 (X1 or -X2) and (X2 or X3 or -X4) and (-X1 or -X3 or X4) 每個clause用 Yi代表 7:50 max Y1 + Y2 + ... + Ym sigma(Xi)(when clause's element is positive) + sigma(1-Xi)(when clause's element is negative) >= Yi , 1 <= j <= m Xi = {0,1} , 1 <= i <= n Yj = {0,1} , 1 <= j <= m ------------------- relax : Xi,Yi = [0,1] 15:15 Rounding stage set Xi to be true with probability Yi (Yi is LP 的最佳解) Xi will be set {0,1} Yi range [0,1] ------------------- proof 19:35 根據極限定理 . . .
Hi mate!! Great job on the channel. Have you ever considered using smzeus . c o m to help your videos rank better?!
If you want to understand the SAT problem in a funny way, go check SAT-Your Day. A game available on App Store and Google Play Store !
感謝分享。我找遍了 UA-cam 竟然沒有英文的教材解釋 2-SAT 如何用 SCC 解。非常驚訝發現台灣的教材！
what were you thinking when you uploaded this video?! everything sucks about it, have you yourself ever watched it??????
Sound sucks...
Captioning would be nice.
MaxSAT random method : 0.5-approximation 6:20 (X1 or -X2) and (X2 or X3 or -X4) and (-X1 or -X3 or X4) 每個clause用 Yi代表 7:50 max Y1 + Y2 + ... + Ym sigma(Xi)(when clause's element is positive) + sigma(1-Xi)(when clause's element is negative) >= Yi , 1 <= j <= m Xi = {0,1} , 1 <= i <= n Yj = {0,1} , 1 <= j <= m ------------------- relax : Xi,Yi = [0,1] 15:15 Rounding stage set Xi to be true with probability Yi (Yi is LP 的最佳解) Xi will be set {0,1} Yi range [0,1] ------------------- proof 19:35 根據極限定理 . . .
謝謝您的回覆呦
Integer Programming is NP-Complete Linear Programming is P Integer Programming 3:50 目標函數 (objective function) : Maximize X1+X2 限制式 (constraints) : 4*X1 - X2 <=8 2*X1 + X2 <=10 X1 , X2 = 0 or 1 -------------------------- IP : 0 or 1 => {0,1} LP : 0 ~ 1 => [0,1] -------------------------- 21:25 weight vertex cover minimum total weight 每個邊就一個限制式 Minimize : 5*X1 + 1*X2 + 5*X3 + 10*X4 + 4*X5 + 6*X9 + 7*X2 subject to : X1 + X2 >=1 X1 + X3 >=1 . . . Xi = {0,1} relax : Xi = [0,1] if Xi <=0.5 ; Xi = 1 if Xi > 0.5 ; Xi = 0
Randominzed Approximation Algorithm 3-SAT 在clause中隨機將原宿設成 F or T 那麼括號不滿足的機率是1/8 E[C] : 每一個括號被滿足的機率 * clause個數= 1-(1/8) * m = 7/8 * m 近似比 : C*/E[C] <= m/(7m/8) = 8/7 k-SAT 近似比 : 2^k / (2^k-1) Max-2-Cut 給一個graph，給一個cut可以砍掉最多邊。(將vertex分兩群) random : 每點隨機分群。 每個編成為cut機率為1/2 C*/E[C] = 2 Max-K-Cut 每個編成為cut機率為k-1/k C*/E[C] = k/(k-1) greedy : 每次一個點，如果鄰居大多都是A群，自己則設為B群。
Set Cover minimum sub-collection 找出最少集重點 : 因為調和數列 所以 C/C* = O(logN) 14:00 在最佳解中任意集合內所有element的值相加會小於調和數列 44:00 greedy每次都會挑在剩下沒有cover的element中最好的set 最好的set(cover最多的點，有可能跟最佳解一樣) |S(i)-(S(1)聯集到S(i-1))| >= |S-(S(1)聯集到S(i-1))| = u(i-1)
Set Cover minimum sub-collection 找出最少集合可以cover所有elements Feature Selection 找出有鑑別度的特徵 可以reduce到Set Cover Set Cover-greedy 找覆蓋最多還沒被覆蓋elements的set 每次set覆蓋到的element(不包含那些已經被覆蓋到的)的size 覆蓋到的element都會給他一個值Cx(1/size) C = sigma(Cx) C ={1,3,4,5} C* ={3,4,5} 將C和C*的set中所覆蓋到element的值Cx相加 C/C* 會是log(n)倍(因為調和數列1+1/2+...+1/n) 隨著element越多差距會越來越大
permutation e.g. 1 2 3 6 4 5 在一個數列N的數列前面加 0 ，後面加上 N+1 在沒有連續的數字間標上breakpoint 觀察上升以及下降趨勢 旋轉一次會消除最多 breakpoint的趨勢 如果沒有選轉會消掉breakpoint，就隨機旋轉一個趨勢 (如我存在一個遞減的字串，保證一定可以消除breakpoint)
近似演算法 1. ractablility : polynomail time 2. feasibility : 合法的解 3. quality : 任意資料輸入進去會產生靠近最佳解的近似解 近似解與最佳解的比值 ，天花板和地板 TSP 2-approximation 完全圖 & 三角不等式 minimum spanning tree pre order(拜訪節點順序) H <= 2*MST <= 2*OPT TSP 3/2-approximation 完全圖 & 三角不等式 minimum spanning tree odd degrees's vertex 互相拉邊 minimum weight perfact matching & euler tour cost(euler tour) = cost(MST)+cost(perfact matching) cost(MST) < OPT cost(euler tour < OPT +cost(perfact matching) cost(perfact matching) < 1/2 OPT cost(euler tour < OPT + 1/2 OPT
真的覺得需要改善錄製方式，不然雜訊跟電流聲音實在……
一種感嘆，感覺每次很重要的地方都被雜訊黑掉= =|||
影片因為網路連線不佳，以致聲音受到影響。