Landscape of solutions in constraint satisfaction problems
Landscape of solutions in constraint satisfaction problems
复制标题
约束满足问题的解图
DOI：
--
复制
发表时间：
2005
影响因子：
8.6
通讯作者：
O. Rivoire
中科院分区：
文献类型：
--
作者：
M. Mézard;M. Palassini;O. Rivoire
我们提出了一个理论框架，用于表征空间的几何性质的解决方案在约束满足问题，连同实际的算法，用于研究这种结构的特定情况下。我们应用我们的方法着色问题，我们得到的解决方案的总数，并详细分析了解决方案之间的距离分布。
We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.