典型文献
树上自旋系统的快速采样算法
文献摘要：
自旋系统是统计物理学中用来描述微观粒子相互作用的重要框架,其可以描述伊辛模型,硬核模型,玻茨模型等统计物理学中的重要模型;通过求解自旋系统的配分函数可以得出物质的能量、磁矩等物理性质.作为一种重要的图模型,自旋系统在理论计算机、人工智能、概率论等领域中被称作马尔可夫随机场而广泛应用,其可以描述着色问题、图同态问题等图论中的重要问题.对图中的点和边赋予非负权重,自旋系统可以诱导出著名的吉布斯分布;配分函数的近似计算可以归约到对应的吉布斯采样问题,通过吉布斯采样可以求解系统的相关物理性质和统计规律.作为模型的简化,树上的自旋系统受到广泛研究;本文研究树上自旋系统的采样算法,并将其推广到树宽较小的图上.我们的主要工作可以列举如下:对于无外场的伊辛模型,基于节点的两种状态的对称性,可以直接计算出任意节点对应的边缘分布,然后通过简单变量的组合来模拟吉布斯分布.类似地,着色问题和玻茨模型也可以基于状态的对称性用简单变量来模拟吉布斯分布.对于一般的自旋系统,无法保证状态的对称性,我们先递归地计算出所有节点的边缘分布,然后基于这些边缘分布进行采样,并通过简单变量的组合来模拟吉布斯分布.对于普通图,我们引入树宽的概念来度量图与树的相似性,并且基于节点间的独立性将算法推广到树宽为2的伪森林和仙人掌图中.我们的算法仅需要线性时间来得到吉布斯分布中的一个样本,在时间复杂度上优于基于马尔可夫链蒙特卡洛模拟的采样算法.
文献关键词：
着色问题;吉布斯分布;伊辛模型;采样算法;自旋系统
中图分类号：
作者姓名：
白宗磊;王捍贫;曹永知;王璐璐
作者机构：
北京大学计算机学院高可信软件技术教育部重点实验室 北京 100871;广州大学计算机科学与网络工程学院 广州 510006
文献出处：
引用格式：
[1]白宗磊;王捍贫;曹永知;王璐璐-.树上自旋系统的快速采样算法)[J].计算机学报,2022(10):2093-2116
A类：
伊辛模型,吉布斯分布,仙人掌图
B类：
树上,上自,自旋系统,采样算法,统计物理,物理学,微观粒子,硬核,配分函数,磁矩,物理性质,图模型,概率论,被称作,马尔可夫随机场,着色问题,同态,图论,近似计算,归约,统计规律,列举如下,外场,直接计算,出任,边缘分布,似地,递归,线性时间,来得,一个样,时间复杂度,马尔可夫链,蒙特卡洛模拟
AB值：
0.240792
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
