计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2010年
z1期
243-244,250
,共3页
武鹏%李美安%裴喜春%周根宝
武鵬%李美安%裴喜春%週根寶
무붕%리미안%배희춘%주근보
分布式互斥%请求集%贪心算法
分佈式互斥%請求集%貪心算法
분포식호척%청구집%탐심산법
在分布式系统中,各节点必须互斥地访问临界区.节点的请求集的长度决定了系统的效率、性能.虽然最优请求集的节点数最少(大约n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算.提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集.与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集.本算法时间复杂度为O(n2),生成的请求集长度为n～2n.
在分佈式繫統中,各節點必鬚互斥地訪問臨界區.節點的請求集的長度決定瞭繫統的效率、性能.雖然最優請求集的節點數最少(大約n),但已有的解決方案該類問題算法類似于窮舉法,隨著節點的增加,該方法變得不可計算.提齣瞭一種快速的請求集生成算法,該算法以循環差集請求集生成算法的理論和貪心算法的基本思想為基礎,在每次迭代的過程中,選齣一箇噹前條件下最優的節點加入請求集.與其他的方法相比較,該方法能對任意給定的整數快速、有效地生成對稱的請求集.本算法時間複雜度為O(n2),生成的請求集長度為n～2n.
재분포식계통중,각절점필수호척지방문림계구.절점적청구집적장도결정료계통적효솔、성능.수연최우청구집적절점수최소(대약n),단이유적해결방안해류문제산법유사우궁거법,수착절점적증가,해방법변득불가계산.제출료일충쾌속적청구집생성산법,해산법이순배차집청구집생성산법적이론화탐심산법적기본사상위기출,재매차질대적과정중,선출일개당전조건하최우적절점가입청구집.여기타적방법상비교,해방법능대임의급정적정수쾌속、유효지생성대칭적청구집.본산법시간복잡도위O(n2),생성적청구집장도위n～2n.
