斯溫森-王算法

斯溫森－王算法（英語：Swendsen–Wang algorithm）由物理學家羅伯特·斯溫森與王建生於1987年提出，是首個非局域的蒙特卡洛算法，用以解決臨界點附近效率變低的臨界慢化問題。

斯溫森－王算法最初用於易辛模型與玻茨模型，後來被推廣到其他模型之中。該算法的關鍵是按照Fortuin與Kasteleyn的理論將玻茨模型變換為滲流理論的模型，相鄰自旋間按概率成鍵。之後再通過霍森－科佩爾曼算法標識聯鍵的集團（cluster），並將每個集團內的所有自旋賦以相同的隨機值。由於該算法可以一次改變整個集團的自旋，因而在臨界點附近能夠顯著提高效率，以解決臨界慢化問題。

2005年，加州大學洛杉磯分校教授朱松純與其博士生阿德里安·巴爾布（Adrian Barbu）推廣了斯溫森－王算法，將其看作是一個梅特羅波利斯－黑斯廷斯算法並計算了相應的接受概率，使其適用於任意後驗概率的採樣。

參考文獻

• Swendsen, R. H., and Wang, J.-S. (1987), Nonuniversal critical dynamics in Monte Carlo simulations, Phys. Rev. Lett., 58(2):86–88.
• Kasteleyn P. W. and Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11; Fortuin C. M. and Kasteleyn P.W. (1972), Physica (Utrecht) 57:536.
• Wang J.-S. and Swendsen, R. H. (1990),Cluster Monte Carlo algorithms, Physica A 167:565.
• Barbu, A., Zhu, S. C. (2005), Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities, IEEE Trans Patt. Anal. Mach. Intell., 27(8):1239-1253.