非二元条件约束满足问题求解

2014-08-10 07:33:50袁际军黄敏镁
计算机集成制造系统 2014年3期

袁际军,黄敏镁

(1.广东财经大学 金融学院,广东 广州 510320;2.华南师范大学 管理科学系,广东 广州 510006)

0 引言

约束满足问题(Constraint Satisfaction Problem,CSP)由一组具有有限域的变量以及限制变量间取值组合的约束构成。CSP的解是一组对所有变量的赋值,并使得该赋值满足所有的约束[1-2]。近三十年来,CSP因其强大的知识表示能力及丰富的领域独立求解技术,在越来越多的现实领域中得到广泛应用,如调度问题[3-4]、日程安排问题[5]、配置问题[6-7]等。然而,随着上述问题求解规模的扩大、约束维数的多元化以及解空间变化的动态性,使得CSP直接建模并求解上述问题时,易遇到知识表示及求解上的困难。

为了有效处理变量在约束条件支配下动态参与问题求解的特性,如豪华型汽车需要配置天窗而标准型不必配置天窗(即变量“天窗”是否出现在最终解中,依赖于变量“汽车”的取值是豪华型还是标准型),Mittal和Falkenhainer对CSP进行了扩展,提出了经典的动态约束满足问题(Dynamic Constraint Satisfaction Problems,DCSP)模型[8]。DCSP模型将CSP中的变量划分为初始变量和非初始变量两类,并引入激活性约束建模初始变量与非初始变量以及非初始变量间的条件依赖关系;通过激活性约束动态地控制非初始变量的状态,使之依条件动态参与问题求解并出现在最终解集中。为了区别文献中已有的另一类动态约束满足问题[9],Sabin将Mittal提出的DCSP模型更名为条件约束满足问题(Conditional Constraint Satisfaction Problems,CCSP)[10-11],并从二元约束的角度进行了系统的研究。尽管条件约束满足问题及其变体,如Sabin提出的复合约束……

登录APP查看全文