计算机集成制造系统
計算機集成製造繫統
계산궤집성제조계통
COMPUTER INTEGRATED MANUFACTURING SYSTEMS
2014年
3期
636-651
,共16页
非二元条件约束满足问题%非二元条件回溯算法%非二元条件前向检查算法%非二元弧一致性
非二元條件約束滿足問題%非二元條件迴溯算法%非二元條件前嚮檢查算法%非二元弧一緻性
비이원조건약속만족문제%비이원조건회소산법%비이원조건전향검사산법%비이원호일치성
non-binary conditional constraint satisfaction problem%non-binary conditional backtracking algorithm%non-binary conditional forward checking algorithm%non-binary arc consistency
非二元条件约束满足问题是二元条件约束满足问题的泛化.给出了非二元条件约束满足问题模型;针对求解过程中激活性约束引起的变量空间变化,分别采用“后看”策略和嵌入不同程度非二元弧一致性的“前看”策略思想,提出一种非二元条件回溯算法和两种非二元条件前向检查算法,以有效处理约束维数的非二元性及变量依条件参与求解的动态性等问题;分析了三种算法最坏情况下的时间复杂性;通过随机生成的测试实例仿真实验比较了三种算法的求解性能.实验结果表明:在处理难问题时,两种非二元条件前向检查算法的性能均显著优于非二元条件回溯算法;而在分别处理中小规模低动态性特征与大规模高动态性特征问题时,两种非二元条件前向检查算法性能存在显著差异.
非二元條件約束滿足問題是二元條件約束滿足問題的汎化.給齣瞭非二元條件約束滿足問題模型;針對求解過程中激活性約束引起的變量空間變化,分彆採用“後看”策略和嵌入不同程度非二元弧一緻性的“前看”策略思想,提齣一種非二元條件迴溯算法和兩種非二元條件前嚮檢查算法,以有效處理約束維數的非二元性及變量依條件參與求解的動態性等問題;分析瞭三種算法最壞情況下的時間複雜性;通過隨機生成的測試實例倣真實驗比較瞭三種算法的求解性能.實驗結果錶明:在處理難問題時,兩種非二元條件前嚮檢查算法的性能均顯著優于非二元條件迴溯算法;而在分彆處理中小規模低動態性特徵與大規模高動態性特徵問題時,兩種非二元條件前嚮檢查算法性能存在顯著差異.
비이원조건약속만족문제시이원조건약속만족문제적범화.급출료비이원조건약속만족문제모형;침대구해과정중격활성약속인기적변량공간변화,분별채용“후간”책략화감입불동정도비이원호일치성적“전간”책략사상,제출일충비이원조건회소산법화량충비이원조건전향검사산법,이유효처리약속유수적비이원성급변량의조건삼여구해적동태성등문제;분석료삼충산법최배정황하적시간복잡성;통과수궤생성적측시실례방진실험비교료삼충산법적구해성능.실험결과표명:재처리난문제시,량충비이원조건전향검사산법적성능균현저우우비이원조건회소산법;이재분별처리중소규모저동태성특정여대규모고동태성특정문제시,량충비이원조건전향검사산법성능존재현저차이.
