Метод полости - это математический метод, представленный Марком Мезаром , Джорджио Паризи и Мигелем Анхелем Вирасоро в 1987 году [1] для решения некоторых моделей типа среднего поля в статистической физике , специально адаптированных для неупорядоченных систем. Этот метод использовался для вычисления свойств основных состояний во многих конденсированных средах и задачах оптимизации .
Первоначально изобретено , чтобы иметь дело с моделью Шеррингтона-Киркпатрик из спиновых стекол , метод полости показал более широкое применение. Его можно рассматривать как обобщение итерационного метода Бете - Пайерлса в древовидных графах на случай графа с не слишком короткими циклами. Различные аппроксимации, которые могут быть выполнены с помощью метода полости, обычно называются в честь их эквивалента [ требуется пояснение ] с различными шагами метода реплик, который математически более тонкий и менее интуитивный, чем подход полости.
Метод полости оказался полезным при решении таких задач оптимизации , как k-выполнимость и раскраска графов . Он дал не только прогнозы энергии основных состояний в среднем случае, но и вдохновил алгоритмические методы.
Смотрите также
Метод полости возник в контексте статистической физики , но он также тесно связан с методами из других областей, таких как распространение убеждений .
Рекомендации
- ^ Mézard, M .; Parisi, G .; Вирасоро, М. (1987). Теория спинового стекла и не только: Введение в метод реплик и его приложения . 9 . Мировая научная издательская компания.
- Браунштейн, А .; Mézard, M .; Zecchina, R. (2005). «Обзор распространения: алгоритм выполнимости». Случайные структуры и алгоритмы . 27 (2): 201–226. arXiv : cs.CC/0212002 . DOI : 10.1002 / rsa.20057 . ISSN 1042-9832 . S2CID 6601396 .
- Mézard, M .; Паризи, Г. (2001). "Повторное посещение решетчатого спинового стекла Бете". Европейский физический журнал B . 20 (2): 217–233. arXiv : cond-mat / 0009418 . DOI : 10.1007 / PL00011099 . ISSN 1434-6028 . S2CID 59494448 .
- Мезар, Марк; Паризи, Джорджио (2003). «Метод полости при нулевой температуре». Журнал статистической физики . 111 (1/2): 1–34. arXiv : cond-mat / 0207121 . DOI : 10,1023 / A: 1022221005097 . ISSN 0022-4715 . S2CID 116942750 .
- Krz̧akała, Florent; Монтанари, Андреа; Риччи-Терсенги, Федерико; Семерджян, Гилхем; Здеборова, Ленка (2007). «Состояния Гиббса и множество решений задач удовлетворения случайных ограничений». Труды Национальной академии наук Соединенных Штатов Америки . 104 (2): 10318–10323. arXiv : cond-mat / 0612365 . DOI : 10.1073 / pnas.0703685104 . ISSN 0027-8424 . PMID 17567754 . S2CID 10018706 .