Я слышал, что в статистической физике есть эвристические аргументы, которые дают результаты в теории вероятностей, для которых строгие доказательства либо неизвестны, либо очень трудно получить. Что является простым игрушечным примером такого явления?
Было бы хорошо, если бы ответ предполагал незначительный опыт в статистической физике и мог объяснить, что это за загадочная эвристика и как они могут быть неофициально обоснованы. Также, возможно, кто-то может указать общую картину того, сколько из этих эвристик может быть строго обосновано и как программа Лоулера, Шрамма и Вернера вписывается в это.
Ответы:
Второй абзац ответа RJK заслуживает более подробной информации.
Пусть - формула в конъюнктивной нормальной форме, с m предложениями, n переменными и не более чем k переменными в предложении. Предположим, мы хотим определить, имеет ли ϕ удовлетворительное присваивание. Формула ϕ является примером решения проблемы k-SAT.φ φ φ
Когда есть несколько предложений (так что m довольно мало по сравнению с n), то почти всегда можно найти решение. Простой алгоритм найдет решение примерно за линейное время по размеру формулы.
Когда есть много предложений (так что m довольно велико по сравнению с n), то почти всегда бывает, что решения не существует. Это можно показать с помощью счетного аргумента. Тем не менее, во время поиска почти всегда можно обрезать большие части пространства поиска с помощью методов согласованности, потому что многие пункты взаимодействуют так широко. Установление неудовлетворенности обычно может быть сделано эффективно.
В 1986 году Фу и Андерсон предположили связь между задачами оптимизации и статистической физикой на основе систем спинового стекла. Хотя они использовали такие предложения, как
они действительно дают конкретные прогнозы.
Димитрис Ахлиоптас работал над многими из оставшихся проблем и показал, что приведенный выше аргумент справедлив и для проблем удовлетворения ограничений. Они могут использовать более двух значений для каждой переменной. В одной ключевой статье строго показано, почему алгоритм распространения съемки работает так хорошо для решения случайных случаев k-SAT.
источник
Существует очень недавнее исследование , проведенное Лоулера на SLES . Вам нужно знать немного сложного анализа.
Хотя это и не имеет прямого отношения к вашему вопросу, возможно, вы могли бы проверить несколько работ Ахлиопты, которые также подпадают под «формализацию эвристики физиков», хотя и с точки зрения теоретического компьютерного ученого. Или, может быть, глубже в перспективе statphys вы можете просмотреть некоторые работы Зекхина .
Я думаю, что стоит добавить, что то, что вы назвали «результатами» физиков - большинство из которых следует назвать гипотезами, - в этой очень широкой категории задач полагается почти столько же (или даже больше) на численные эксперименты, как ( чем) на эвристических аргументах.
источник
(расширение моего комментария)
Обзор " эвристики от природы " можно найти здесь (около 95)
Другие эвристики включают обобщенные лангранжианы (известные как алгоритмы первичного-двойственного / ожидания-максимизации)
Однако они не исчерпывают всей « эвристики от природы », так как фактически начиная с 2003 года новые эвристики, основанные на электромаргнетизме , используются для решения как непрерывных, так и дискретных / комбинаторных методов оптимизации (таких как многомерный рюкзак или TSP , около 2012 г.)
источник