上海第二工业大学学报
上海第二工業大學學報
상해제이공업대학학보
JOURNAL OF SHANGHAI SECOND POLYTECHNIC UNIVERSITY
2011年
3期
207-213
,共7页
竞争决策算法%元胞自动机%度约束最小生成树%降阶
競爭決策算法%元胞自動機%度約束最小生成樹%降階
경쟁결책산법%원포자동궤%도약속최소생성수%강계
competitive decision algorithm%cellular automata%degree-constrained minimum spanning tree%reduction
度约束最小生成树（Degree-Constrained Minimum Spanning Tree,简记DCMST）是网络设计和优化中的一个经典的组合优化难题。竞争决策算法是一种特别适合于求解组合优化难题的新型算法。为了提高求解DCMST问题的求解精度,将元胞自动机的邻居演化原理和竞争决策算法相结合——元胞竞争决策算法来求解DCMST;为了提高算法的效率,分析了度约束最小生成树问题的数学性质并利用这些性质对问题实现降阶。降阶过程会有效降低问题处理的规模。为了验证算法的性能,采用Delphi 7.0实现算法,经过数据测试和验证,并与其他算法的结果进行比较,证明了算法的有效性。
度約束最小生成樹（Degree-Constrained Minimum Spanning Tree,簡記DCMST）是網絡設計和優化中的一箇經典的組閤優化難題。競爭決策算法是一種特彆適閤于求解組閤優化難題的新型算法。為瞭提高求解DCMST問題的求解精度,將元胞自動機的鄰居縯化原理和競爭決策算法相結閤——元胞競爭決策算法來求解DCMST;為瞭提高算法的效率,分析瞭度約束最小生成樹問題的數學性質併利用這些性質對問題實現降階。降階過程會有效降低問題處理的規模。為瞭驗證算法的性能,採用Delphi 7.0實現算法,經過數據測試和驗證,併與其他算法的結果進行比較,證明瞭算法的有效性。
도약속최소생성수（Degree-Constrained Minimum Spanning Tree,간기DCMST）시망락설계화우화중적일개경전적조합우화난제。경쟁결책산법시일충특별괄합우구해조합우화난제적신형산법。위료제고구해DCMST문제적구해정도,장원포자동궤적린거연화원리화경쟁결책산법상결합——원포경쟁결책산법래구해DCMST;위료제고산법적효솔,분석료도약속최소생성수문제적수학성질병이용저사성질대문제실현강계。강계과정회유효강저문제처리적규모。위료험증산법적성능,채용Delphi 7.0실현산법,경과수거측시화험증,병여기타산법적결과진행비교,증명료산법적유효성。
Finding the Degree-Constrained Minimum Spanning Tree（DCMST for short） of a graph is a classical combinatorial optimization hard problem in network-designing and optimization.Competitive decision algorithm（CDA for short） is a new type algorithm especially suitable for solving combinatorial optimization problems.Cellular competitive decision algorithm for DCMST is presented here to improve the accuracy of the solution,which introduced the neighborhood evolution of cellular automata into CDA.To speed up the algorithm,the mathematical properties of DMST are used to reduce the scale of instances.To verify the effectiveness of the algorithm,it is being coded in Delphi 7.0 and series of instances are tested here.
