Cocco S, Monasson R
CNRS-Laboratoire de Physique Théorique de l'ENS, 24 rue Lhomond, 75005 Paris, France.
Phys Rev Lett. 2001 Feb 19;86(8):1654-7. doi: 10.1103/PhysRevLett.86.1654.
Decision and optimization problems typically fall into one of two categories for any particular solving algorithm. The problem is either solved quickly (easy) or demands an impractically long computational effort (hard). Here we show that some characteristic parameters of problems can be tracked during a run of the algorithm defining a trajectory through the parameter space. Focusing on 3-satisfiability, a recognized representative of hard problems, we analyze trajectories generated by search algorithms. These trajectories can cross well-defined phases, corresponding to domains of easy or hard instances, and allow one to successfully predict the times of resolution.
对于任何特定的求解算法，决策和优化问题通常可分为两类。问题要么能快速解决（简单），要么需要耗费长得不切实际的计算量（困难）。在这里我们表明，在算法运行过程中可以跟踪问题的一些特征参数，这些参数定义了一条穿越参数空间的轨迹。以3 - 可满足性（一种公认的难题代表）为例，我们分析了搜索算法生成的轨迹。这些轨迹可以穿过定义明确的阶段，这些阶段对应于简单或困难实例的区域，并且能让人成功预测解决时间。
