计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2008年
24期
46-49
,共4页
元胞自动机%无向图%优化算法%复杂度
元胞自動機%無嚮圖%優化算法%複雜度
원포자동궤%무향도%우화산법%복잡도
运用元胞自动机理论,针对无向图剖分优化问题进行了分析和建模,提出了一种元胞自动机模型以及基于该模型的无向图剖分优化算法.在该元胞自动机模型中,元胞对应于无向图中的结点,元胞的邻居对应于邻接结点,元胞空间对应于无向图中的结点集,元胞的状态对应于所在的结点子集.实验及分析表明该算法不仅能找到无向图的近似最优剖分,而且有效地降低了空间复杂度和时间复杂度.
運用元胞自動機理論,針對無嚮圖剖分優化問題進行瞭分析和建模,提齣瞭一種元胞自動機模型以及基于該模型的無嚮圖剖分優化算法.在該元胞自動機模型中,元胞對應于無嚮圖中的結點,元胞的鄰居對應于鄰接結點,元胞空間對應于無嚮圖中的結點集,元胞的狀態對應于所在的結點子集.實驗及分析錶明該算法不僅能找到無嚮圖的近似最優剖分,而且有效地降低瞭空間複雜度和時間複雜度.
운용원포자동궤이론,침대무향도부분우화문제진행료분석화건모,제출료일충원포자동궤모형이급기우해모형적무향도부분우화산법.재해원포자동궤모형중,원포대응우무향도중적결점,원포적린거대응우린접결점,원포공간대응우무향도중적결점집,원포적상태대응우소재적결점자집.실험급분석표명해산법불부능조도무향도적근사최우부분,이차유효지강저료공간복잡도화시간복잡도.
