上週初看 Spielman, Teng 的 Smoothed Analysis 的觀點，感到有些驚奇，本來也想從原始論文 simplex method 那方面直接切入，
刊載在 JACM 的原文長達 80 頁，另有幾篇Spielman, Teng 在 STOC2001, ICM2002, CACM 2008 的介紹文章，只是稍微看懂 introduction 的介紹。
問題都還是環繞在 linear programming 上，但也還沒那麼多心力去了解 linear programming 的細節。
最後還是先以熟悉的 combinatorial Problems 來作個對 smoothed analysis 的初步探究。在 Banderier Mehlhorn, Beir 這篇文章裡討論了三個問題 quick sort, left-to-right Maxima, single source shortest Path Problems.
今天則先 focus 在 quick sort 這問題上。
首先從 smoothed analysis 的式子來了解，可看出smoothed analysis 是個介於 worst case analysis 和 average case analysis 之間的分析。smoothed analysis 是對於每一點，採其 neighbor 作平均。接著才在對這些平均中取其 worst case。當這 neighbor 小至只有一點時，即為 worst case analysis ，若 neighbor 大至全部，則為 average case analysis。
以下兩示意圖對來對於上述式子來在觀察哪些情況是適用於 smoothed analysis。藍色的曲線為每個 instance 的 running time，
綠色的曲線為 average case 的 running time。紅橘兩曲線則各取附近5點, 10 點的平均 running time。
若某演算法對其中有些 worst case 都很集中，則 smoothed analysis 後，也沒有太好的表現。
但若那些 worst case 很稀很分散，則 smoothed analysis 則有比較好的表現。
這也就是為何 smoothed analysis 可用來解釋 algorithm 在“實際應用”上的表現。現實世界的資料是充滿很多干擾、雜訊。因此若演算法的的表現如圖二，則實際執行時，會掉入那些稀有的 worst case 的機率其實不高。
但問題是如何定義“擾動”呢？ 在 quick sort 中，採用 partial permutation 的方法。每元素有 p 的機率會改變其位置，也就是平均有 np 的元素會改變，對於這些會被改變的 m 個元素，其有 m! 種置換方式。
基於這 partial permutation 的 models 下，要去估計任兩個元素的比較次數。
設 
為依大小排序後的序列，在 quick sort algorithm 中，當 
被挑選為 pivot 時，若 
和 有比較大小，則定令 
為 1，若無則為 0。
對於average analysis 即為，當 p = 1 時，則 期望值為 
，於是 )
。
當 p <1 時，對於 之值的估計要作比較仔細的分析。主要想法分為若 
有機會變為很靠近的點則視其值為 1，且論證此類情形不太多。而對其他大多數情況，則因其距離較遠，可論證其 會比較的機率較小。因此評估起來其期望值為 )
。
對於細部的分析，則有以下的 7 cases:
在此文的後半部在討論 left-to-right-maxima 問題，其想要陳述的為原先的 worst case instance ，在 smoothed analysis 後，並不一定為 worst case ，以及其 recursive depth 不為 )
。而在最後的 single shortest path problem ，則討論另一種擾動的 model : "partial Bit Randomization".
對於怎樣才是個合適的"擾動"也是個蠻重要的問題。例如，當我們看一個 maximum clique 的問題，所予許的小擾動是每個vertex pair 的連結有 p 的機會會改變，這樣便很容易破獲原本 maximum clique 的 property。如何來要在維持 property 的情況下，再去討論擾動的狀況， Spielman, Teng 在
Smoothed Analysis: Motivation and Discrete Models 中，也對其做了些相關討論。
在 smoothed analysis 中，
沒有留言:
張貼留言