충치법
Cavity method충치법은 통계물리학에서 일부 평균장형 모델을 해결하기 위해 1987년[1] 마르크 메자드, 조르지오 파리, 미겔 앙헬 비라소로가 제시한 수학적인 방법이며, 특히 질서 없는 시스템에 맞게 조정되었다.이 방법은 많은 응축 물질과 최적화 문제에서 지상 상태의 특성을 계산하는 데 사용되어 왔다.
처음에 Sherrington-Kirkpatrick 모델인 스핀안경을 다루기 위해 발명된 캐비티 방법은 더 넓은 적용 가능성을 보여주었다.너무 짧지 않은 루프가 있는 그래프의 경우, 나무와 같은 그래프에서 반복적인 방법을 일반화한 것으로 볼 수 있다.캐비티 방법으로 할 수 있는 다른 근사치는 보통 캐비티 접근법보다 수학적으로 더 미묘하고 덜 직관적인 복제 방법의 다른 단계와 동등한[clarification needed] 이름을 따서 명명된다.
캐비티 방법은 k-만족도 및 그래프 컬러링과 같은 최적화 문제를 해결하는데 유용하다는 것이 입증되었다.그것은 평균 사례에서 에너지 예측을 지상국가에 산출했을 뿐만 아니라 알고리즘적인 방법에 영감을 주었다.
참고 항목
충치법은 통계물리학의 맥락에서 시작되었지만, 신념 전파와 같은 다른 영역의 방법과도 밀접하게 관련되어 있다.
참조
- ^ Mézard, M.; Parisi, G.; Virasoro, M. (1987). Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications. Vol. 9. World Scientific Publishing Company.
추가 읽기
- Braunstein, A.; Mézard, M.; Zecchina, R. (2005). "Survey propagation: An algorithm for satisfiability". Random Structures and Algorithms. 27 (2): 201–226. arXiv:cs.CC/0212002. doi:10.1002/rsa.20057. ISSN 1042-9832. S2CID 6601396.
- Mézard, M.; Parisi, G. (2001). "The Bethe lattice spin glass revisited". The European Physical Journal B. 20 (2): 217–233. arXiv:cond-mat/0009418. doi:10.1007/PL00011099. ISSN 1434-6028. S2CID 59494448.
- Mézard, Marc; Parisi, Giorgio (2003). "The Cavity Method at Zero Temperature". Journal of Statistical Physics. 111 (1/2): 1–34. arXiv:cond-mat/0207121. doi:10.1023/A:1022221005097. ISSN 0022-4715. S2CID 116942750.
- Krz̧akała, Florent; Montanari, Andrea; Ricci-Tersenghi, Federico; Semerjian, Guilhem; Zdeborová, Lenka (2007). "Gibbs states and the set of solutions of random constraint satisfaction problems". Proceedings of the National Academy of Sciences of the United States of America. 104 (2): 10318–10323. arXiv:cond-mat/0612365. doi:10.1073/pnas.0703685104. ISSN 0027-8424. PMC 1965511. PMID 17567754. S2CID 10018706.
- Advani, Madhu; Bunin, Guy; Mehta, Pankaj (2018). "Statistical physics of community ecology: a cavity solution to MacArthur's consumer resource model". Journal of Statistical Physics. 3: 033406. doi:10.1088/1742-5468/aab04e. PMC 6329381. PMID 30636966.
