斯温森-王算法

斯温森－王算法（英語：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.