| 【论文摘要】 |
在人工智能领域和计算机科学领域中,有大量的问题可以被看作是约束满足问题(Constraint Satisfaction Problem,CSP),例如语言理解、生产调度、规划、模式识别等。由于变量和约束往往是不能完全独立的,当问题涉及到较大规模时,要降低求解的难度,就要对变量和约束进行处理,使其分解成既能满足总体约束需要,又能降低求解难度的形式,也就是对约束分解。
本文基于约束满足问题的分解方法,对应用数据库理论的铰链分解(hinge分解)技术和基于其上的改进方法CaT分解(结构化分解)策略进行了描述,并对与此算法相关的其他几种分解算法及不同角度的比较分析,利用Java、XML、struts等技术在B/S体系结构的产品配置器系统中进行配置分解,在系统中应用并实现了该分解算法。
最后,我们给出了分解算法的实验结果数据,验证此算法对有限度的约束满足问题是一种有效的分解方式,以及对不同方法(原配置器系统和现系统的算法)的对比分析。实验结果表明,在问题规模较小的情况下,求解配置的效果不明显,但是分解本身的效率却很高;当问题规模较大时,利用分解算法处理配置求解也能得到较为理想的结果。 |
