软约束满足问题的符号表示及其推理研究

软约束满足问题是人工智能中一个重要的研究课题，在复杂调度、资源分配、优化排序等领域有着广泛的应用。针对目前软约束满足问题的求解技术中存在的问题，本项目提出一种能有效描述软约束满足问题的新型BDD结构，并基于此结构开展软约束满足问题的知识描述、符号推理算法的研究，建立具有低空间复杂度和高推理效率的软约束满足问题的符号推理求解系统。首先，从软约束满足问题的一般模型出发，提出一种对含有多值变量的非0-1数值函数具有强描述能力的新型BDD结构。在此基础上，建立从软约束满足问题到新型BDD结构表示的转化规则，对软约束满足问题进行符号化描述。进一步地建立软弧一致性符号技术和相应的具有软弧一致性符号预处理技术的符号推理算法、基于树分解技术的符号推理算法、带有启发式搜索的符号推理算法。最后，建立搜索与推理相融合的软约束满足问题的符号推理系统。项目具有源头创新性，对本研究领域的技术进步将产生积极的影响。

软约束满足问题（Soft CSP）是一类约束最优化问题，在人工智能和现实生活中有着广泛应用。本项目从软约束求解的两类完备算法—基于推理的算法和基于搜索的算法出发，以如何高效地提高算法的求解效率和降低算法的空间复杂度为目标开展研究。基于EVBDD和MDD结构，给出了用于描述Soft CSP的一种新的BDD扩展结构MADD，并制定了MADD的2条化简规则；依据多值函数的香农分解规则，设计了MADD上的有关操作算子，化简算法和构造算法；基于BDD及其扩展结构，给出了Soft CSP的结点一致性、基于AC3算法思想的（软）弧一致性等符号预处理技术，并给出了相应的符号推理算法；基于环割集思想，给出了Soft CSP的树分解符号求解算法；基于嵌套分解技术，给出了基于RDS的改进DFBB符号算法；研究了(no)good记录结构，及带有(no)good记录的Soft CSP符号求解算法；建立了搜索与推理相融合的Soft CSP的符号推理系统。