聖塔非研究所 組合最佳化中的臨界性和平行性 2026-03-18 · 工作論文 · 更新 2026/03/19 上午12:23 摘要 我們證明了組合最佳化問題中相變的存在。對於許多這樣的問題，隨著局部搜尋演算法的並行化，解決方案的品質首先會提高，然後急劇下降，不比隨機搜尋好。這種轉變可以使用有限尺寸縮放（一種借用統計物理學的技術）成功地表徵。我們展示了一系列廣義自旋玻璃模型和旅行商問題的結果。我們確定臨界指數，研究噪音的影響，並討論相變存在的條件。 原文連結PDF 來源 本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。 原文連結 原文連結 PDF 來源 論文資訊 類型：工作論文 編號：工作論文 #1346 日期：2026-03-18 摘要 我們證明了組合最佳化問題中相變的存在。對於許多這樣的問題，隨著局部搜尋演算法的並行化，解決方案的品質首先會提高，然後急劇下降，不比隨機搜尋好。這種轉變可以使用有限尺寸縮放（一種借用統計物理學的技術）成功地表徵。我們展示了一系列廣義自旋玻璃模型和旅行商問題的結果。我們確定臨界指數，研究噪音的影響，並討論相變存在的條件。