论文标题
L距离的统计力学最小主导设置问题
Statistical Mechanics of the L-Distance Minimal Dominating Set problem
论文作者
论文摘要
统计力学广泛应用于解决硬性优化问题，这是与低温相关的最佳策略。如果温度适当降低，预计常见的热力学过程将接近基态能量，但是当网络在低温下包含更长的循环时，这种信念并不总是合理的。以前，我们始终实施规范平衡过程来预测低能，但是它在L距离（l> 1）最小的主导设置问题中不起作用，因为热力学过程无法保证在低温下找到系统的稳定状态。在这里，我们采用了腔化方法的能量钳位策略（微型典型平衡过程）来预测低能量，并发现微磁过程仍在低温下在规范过程中发现给定系统的稳定状态。我们开发信念传播分解（BPD）和贪婪的算法来计算L-distance（$ 2 <l <7 $）的最小统治集，我们发现BPD算法结果优于贪婪的算法。我们目睹了在不同的l距离上具有不同平均能量的负$β$的出现。自由能在$β= 0 $的情况下具有不连续的相变。我们通过微型腔腔法预测基态能量，克服了规范腔法的局限性。
Statistical mechanics is widely applied to solve hard optimization problem, the optimal strategy related to ground state energy that depends on low temperature. Common thermodynamic process is expected to approach the ground state energy if the temperature is lowered appropriately, but this belief is not always justified when the network contains more long loops in low temperature. Previously we always implement the canonical equilibrium process to predict the low-energy, but it doesn't work in L-distance (L>1) minimal dominating set problem, because the thermodynamical process can not guarantee to find the stable state of the system at the low temperature. Here, we employ energy-clamping strategy of cavity method ( micro canonical equilibrium process ) to predict low-energy and discover that the microcanonical process still find the stable state of given system at low temperature where canonical process work out. We develop Belief Propagation Decimation (BPD) and Greedy algorithm to calculate the L-distance ($2<L<7$) minimal dominating set, we find that the BPD algorithm results outperform the Greedy algorithm. We have witnessed the emergence of negative $β$ with different mean energy on different L-distance. The free energy has a discontinuous phase transition at $β= 0$. We predict the ground state energy by microcanonical cavity method, overcoming the limitation of canonical cavity method.
