[统计数据] 在求解随机约束满足时，谨慎下降占上风 问题 [推广有奖]

摘要翻译：
我们研究了随机局部搜索算法在$k$-可满足性($k$-SAT)问题中的性能。本文提出了一种新的随机局部搜索算法ChainSAT，它通过能量的{\em从不向上}在问题实例的能量景观中移动。ChainSAT是一个\emph{focused}算法，因为它只考虑出现在未满足子句中的变量。我们通过大量的数值研究表明，ChainSAT和其他聚焦算法几乎可以在线性时间内解决大的$k$-SAT实例，直到高子句与变量的比值$\alpha$；例如，对于k=4，我们观察到的线性时间性能远远超出了解空间中最近假定的聚类和凝聚跃迁。ChainSAT的性能是一个惊喜，因为通过设计，算法陷入了它遇到的第一个局部能量最小值，但没有遇到这样的最小值。我们还研究了随机局部搜索算法所访问的解空间的几何形状。
---
英文标题：
《Circumspect descent prevails in solving random constraint satisfaction
  problems》
---
作者：
Mikko Alava, John Ardelius, Erik Aurell, Petteri Kaski, Supriya
  Krishnamurthy, Pekka Orponen, and Sakari Seitz
---
最新提交年份：
2007
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Physics        物理学
二级分类：Statistical Mechanics        统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  We study the performance of stochastic local search algorithms for random instances of the $K$-satisfiability ($K$-SAT) problem. We introduce a new stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by {\em never going upwards} in energy. ChainSAT is a \emph{focused} algorithm in the sense that it considers only variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large $K$-SAT instances almost surely in linear time, up to high clause-to-variable ratios $\alpha$; for example, for K=4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.
---
PDF链接：
https://arxiv.org/pdf/711.4902