師大學報：數理與科技類

Permanent URI for this collection

http://rportal.lib.ntnu.edu.tw/handle/20.500.12235/180

Browse

Browsing 師大學報：數理與科技類 by Author "Rue-Yi Chen and Shun-Shii Lin"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    完全圖上最大權重配對問題之自我穩定演算法的設計及分析
    (國立臺灣師範大學研究發展處, 2000-04-??) 陳瑞宜; 林順喜; Rue-Yi Chen and Shun-Shii Lin
    在1974年，Dijkstra提出了自我穩定的概念。一個分散式系統不論其初始狀態為何，最後都會收斂至正確的系統狀態稱之為自我穩定系統。近年來，自我穩定演算法不用初始化的特性受到許多研究者的重視。Hsu和Huang針對分散式網路中「最大配對」問題提出了自我穩定演算法，並利用變數函數分析法，證明了此演算法需耗用的時間複雜度為O(n3)，然而Tel針對此一演算法提出不同的變數函數，證明最多需要O(n2)的時間複雜度。在本論文中，我們將自我穩定系統的理論應用在完全圖上的「最大權重配對」問題，設計出包含五個規則的自我穩定演算法，並針對此自我穩定演算法的正確性進行證明分析。最大權重問題是指當節點兩兩配對之後，其線段權重兩兩交換並不會找到更大的值，也就是除了希望在圖中找到最大配對之外，更進一步能夠使配對的權重達到最大。因此我們結合了Hsu-Huang最大配對自我穩定演算法，以及嶄新的交換配對規則，保留自我穩定系統容錯及自我穩定的特性，設計了時間複雜度為O(n2+nk)的一個最大權重配對問題之自我穩定演算法。