约束满足问题的结构特征和算法分析

在约束满足问题中要求为一组变量赋值来满足给定的一组约束条件，这类问题覆盖了计算机科学、人工智能、运筹学等很多领域的重要问题。值域可变的约束满足问题可以更好地描述实际问题，近年来逐渐引起关注，但过去在固定值域条件下取得的结论往往不能直接应用。随机约束满足问题通过一个随机过程产生随机实例，通过调整随机过程的控制参数，可以观察到实例性质的相变现象，包括从有解到无解的可满足性相变、在可满足性临界点附近算法行为的相变等，但目前还没有建立起可满足性相变与难解性之间的确切关联。本项目研究值域可变的随机约束满足性问题的结构特征和算法分析，包括结构参数的取值和解空间的结构变化、各种求解算法的相变点、在算法模型和证明系统下的指数下界、近似算法和精确算法研究等，目标是比较其与固定值域的约束满足问题的差别，刻画值域可变的随机约束满足问题的难解性，建立起相变现象与难解性之间的确切联系，为实际应用打下坚实的理论基础。

本项目用理论分析和实验结果来研究约束满足问题的结构特征和算法分析，完成了研究计划。首先，从结构分解的角度研究了随机约束满足问题的相变现象与难解性。RB模型是一种值域增长的随机约束满足问题，具有精确相变并成功构造出各种难解算例。证明了RB模型的随机约束超图在不同结构分解方法下（包括铰链分解、树分解、最小环割集等）在相变区渐进具有大的结构参数，有关结果在顶级会议IJCAI上口头报告。利用腔方法研究了RB模型解空间的分簇现象，有关结果发表在重要物理学期刊PRE上。这些结果为RB模型的难解性提供了新的理论证据。此外，对随机k-SAT、随机Max-2-SAT、随机k-CSP、随机k-d-CSP、随机#CSP、知识编译等许多问题，也确定了可满足性相变点的存在性或改进了参数范围，有关结果发表在顶级期刊AIJ和SCI期刊IPL和EJC上，并在顶级会议AAAI和SAT墙报展示。其次，从算法分析的角度研究了约束满足问题的求解效果和难解性与易解性的分类。在RB模型上研究了一致性算法、回溯算法、局部搜索算法、消息传递算法等基本算法的求解效果。提出了以变元为中心的一致性概念，确定了在RB模型上这种一致性成立的参数范围，有关结果被SCI期刊MIND录用。利用这种一致性可给出RB模型无回溯求解的参数范围。利用改进的局部搜索算法，在一个RB模型构造的难解算例的求解中取得了当前最好结果，有关结果发表在顶级期刊AIJ和在顶级会议AAAI口头报告。证明了基于统计物理原理的消息传递算法在RB模型上相变点附近依然有效，有关结果发表在重要的统计物理期刊JSTAT上和中文核心期刊中国科学上。求最小环割集是个经典的NP完全问题，可用来求约束满足问题的后门变量。在二部图上扩展了最小环割集问题的难解的子问题类和易解的子问题类，有关结果被重要的计算机理论期刊TCS录用。指数时间精确算法和多项式时间近似算法是对付难解问题的经典方法。改进了背包问题在一种回溯算法模型下的指数下界，发表在期刊TCS上。把用来证明难近似性结果的UGC推广到带负的权值的情形，在会议COCOA上口头报告。总之，本项目累计发表学术论文24篇（顶级期刊3篇、顶级会议5篇含口头报告2篇和墙报3篇、SCI和EI检索各11篇）、编著教材1部、撰写综述1篇、组织国内和国际会议各1次、培养或协助培养研究生6人以上。