k-d-CSP模型的解空间结构和无回溯算法研究

We will study the k-d-CSP model using mathematical method. k-d-CSP model is an important representative of random model of constraint satisfaction problem, which covers a wide range, including RB model and k-CSP model. The study of k-d-CSP model has theoretical significance of studying problem hardness source and application value of directing algorithm design. We will first study the clustering phase transition of solution space structure, try to classify the value of k and d, study the clustering phenomenon and identify cluster scope, cluster diameter, distance between clusters, cluster number. Then, we give the complete classification description of clustering phenomenon of k-d-CSP model. Secondly, we will research on the effectiveness of backtrack-free algorithm, try to prove that the validity of the algorithm has phase transition phenomenon with the constraint density increasing, and try to prove that the phase transition point tends to 0 with the problem size growing; because the algorithm is affected by $lambda$-core properties, we will study the properties of threshold of $lambda$-core on the random k-hypergraph (k=k(n) growing with the number of vertex n). Finally, we will study the freezing phase transition of the solution space structure, and study the constraint density range where freezing phase exists and other properties.

我们将运用数学方法对k-d-CSP模型进行研究。k-d-CSP模型是随机约束满足问题模型的重要代表，该模型涵盖范围很广，包含了RB模型、k-CSP模型。对该问题的研究具有探究问题难度来源的理论意义和指导算法设计的应用价值。我们将首先研究解空间结构中的分簇相变，试图将模型按k、d取值进行分类，研究每一类的分簇现象，分别给出分簇范围、簇直径、簇之间距离和簇个数，从而给出k-d-CSP模型分簇现象的完整分类描述。其次我们将研究无回溯算法的有效性，试图证明该算法有效性随约束密度增大具有相变现象，并试图证明该相变的相变点随问题规模变大趋近于0；由于该算法有效性跟$lambda$-核性质密切相关，我们将研究随机k-超图(k=k(n)随节点个数n增长)$lambda$-核阈值性质。最后我们将研究解空间结构中的凝结相变现象，研究凝结相出现的约束密度范围及其他性质。

k-d-CSP模型是一种广泛的约束满足问题模型，它具有可变的约束长度k与可变的值域大小d。本项目对该模型的解空间结构进行了研究，对该模型上无回溯算法进行了研究。研究结果包括：详细描绘了k-d-CSP模型的解空间结构，发现在满足性相变点附近其解空间分解为广泛分布的分散的规模很小的凝结的簇，认为这导致了相变点附近问题难度大；详细描绘了含隐藏解的RB模型（k-d-CSP模型的特例）的解空间结构，发现该模型发生四种相变；详细描绘了含隐藏解的k-CSP模型（k-d-CSP模型的特例）的解空间结构；对RB模型上的（1，1）--超解进行研究，发现其超解个数期望值存在相变现象；对k-d-CSP模型上无回溯算法进行研究，发现d的变化影响该算法有效性；对凝结相变使用实验方法研究，给出其相变点。本项目为使用k-d-CSP模型生成（有解）难解实例提供理论依据，并将有助于算法设计。