algo | Minimal Coverage

http://140.113.39.130/cgi-bin/gs32/hugsweb.cgi?o=dnthucdr&s=%22GH000945617%22.id.&

在我們之前有關Link Failure Detection的研究,提出了一個求解Minimum Set Covering Problem的Heuristic Algorithm。Minimum Set Covering Problem是一個常見的問題,在各方面都有廣泛的應用。我門之前的研究,證實了此Algorithm在求解由Link Failure Detection所產生的Minimum Set Covering Problem時,具有比Greedy Algorithm更好的效果。然而,我們並沒有針對它與其他類似的演算法進行更深入的分析及比較,且其時間複雜度亦過高。

本篇論文對此Heuristic Algorithm提出了改良的方法,使其worst cast time complexity由O(min(|X|,|F|))*O(|F|)*O(|F|)*O(|X|)降低為O(min(|X|,|F|))*O(|F|)*O(|X|),並且整理出與此方法類似的Greedy based algorithms,包含Greedy Algorithm、TGreedy Algorithm以及AltGreedy Algorithm[6]。我們以各種不同的方式產生了Minimum Set Covering Problems,包含由Link Failure Detection問題所形成的Minimum Set Covering Problem[1]、OR-Library[9],以及由各種不同參數所產生的Random Problems。

針對這些algorithms以及各種不同類型的Minimum Set Covering Problem,我們做了完整的模擬測試,從模擬的結果可以觀察出我們先前所提出的Heuristic Algorithm,不僅在求解由Link Failure Detection所產生的Minimum Set Covering Problem時有很好的效果,對於一般性的Minimum Set Covering Problem,也能求得比其他方法更好的解。

另外,本篇論文針對此Heuristic Algorithm以及其他類似的algorithms,也做了worst case time complexity的分析,由分析的結果以及模擬的結果,我們發現TGreedy演算法的最差情況時間複雜度最高,AltGreedy演算法次之,Greedy演算法最小。而我們所提出的Heuristic Algorithm,在本篇論文的改良前,其最差情況時間複雜度與AltGreedy演算法相同。在本篇論文的改良後,其最差情況時間複雜度則降低至與Greedy演算法相同。





Comments