Комментарии 16
Интересно. Но на один вопрос так и не нашел ответа для себя: а для каких практических задач это можно применять?
На этот вопрос я и не пытался давать ответ в статье. Данная задача берёт свое начало в физике полимеров. Примерно 50 лет назад физика полимеров стала отдельным направлением науки, поскольку изучение свойств этих самых полимеров оказалось очень важным. Полимер – это большая молекула, которая моделируется в виде простой цепочки (без самопересечений), проходящей по узлам воображаемой решётки. Цепочка может замкнуться сама на себя только в конечных точках, так образуется цикл.
Почему циклы гамильтоновы? Это связано с изучением свойств плотноупакованных полимеров. Плотноупакованный полимер (глобула) будет проходить по всем узлам воображаемой решётки.
Зачем считать все возможные циклы? В физике существует понятие энтропия системы. В данной задаче (не буду доказывать строго) энтропия равна логарифму всех возможных конфигураций полимера. Чтобы посчитать этот логарифм, нужно посчитать и само это количество.
Разумеется, точное решение физиков не интересует, их интересует скорость, с которой число конфигураций будет расти с увеличением числа узлов. Эта скорость может быть найдена тем точнее, чем больше точных решений удастся посчитать. Чем больше решёток посчитано, тем точнее будет экстраполяция на большие решетки. В общем, здесь ещё долго можно рассказывать и про константу связности и про другие вещи из физики, но факт в том, что задача имеет практическую ценность.
Теоретическая ценность задачи в том, что она позволяет разрабатывать численные методы перечислительной комбинаторики, которая уже имеет огромное количество приложений.
Почему циклы гамильтоновы? Это связано с изучением свойств плотноупакованных полимеров. Плотноупакованный полимер (глобула) будет проходить по всем узлам воображаемой решётки.
Зачем считать все возможные циклы? В физике существует понятие энтропия системы. В данной задаче (не буду доказывать строго) энтропия равна логарифму всех возможных конфигураций полимера. Чтобы посчитать этот логарифм, нужно посчитать и само это количество.
Разумеется, точное решение физиков не интересует, их интересует скорость, с которой число конфигураций будет расти с увеличением числа узлов. Эта скорость может быть найдена тем точнее, чем больше точных решений удастся посчитать. Чем больше решёток посчитано, тем точнее будет экстраполяция на большие решетки. В общем, здесь ещё долго можно рассказывать и про константу связности и про другие вещи из физики, но факт в том, что задача имеет практическую ценность.
Теоретическая ценность задачи в том, что она позволяет разрабатывать численные методы перечислительной комбинаторики, которая уже имеет огромное количество приложений.
Эммм… Я занимаюсь физикой полимеров. :) Как раз компьютерным моделированием, но не алгоритмической частью моделирования, а прикладной, скажем так (ну и полимеры не на решетке, но это уже детали). В общем, истоки понятны. Сейчас, как я понимаю, большую ценность задача имеет именно с теоретической точки зрения.
Да, пожалуй, с теоретической точки зрения больше, чем с практической. По части физики, этим алгоритмом я уточнил константу связности для циклов на решётке. Долгое время считалось, что теория среднего поля дает правильный ответ 4/e, но практика показала, что это не так. Я скоро опубликую результаты по этой теме. Точнее, они уже публикуются. Конечно, этот результат носит теоретический характер. Сам я полимеры не выращиваю.
А вы статью специально для хабра писали?
А по мне, так волновой алгоритм ляжет на Ваши задачи куда элегантнее.
Я знаю только один волновой алгоритм — для решения задачи о максимальном потоке. Сюда его не применить. Описанный мной алгоритм на сегодняшний день является самым оптимальным для решения данной задачи. Более оптимального алгоритма, который работал бы на практике в научной литературе нет. К сожалению, это так.
отличная статья. практическое применение (или просто отработать алгоритм) можно здесь:
acm.timus.ru/problem.aspx?space=1&num=1459
acm.timus.ru/problem.aspx?space=1&num=1459
К сожалению, в этой задаче при таких игрушечных ограничениях решение слишком тривиальное: возьмите готовую формулу и решайте.
Например, для N=5 для решетки с длиной 2M там будет формула a(M) = 11a(M-1)+2a(M-3). Записываем это выражение с помощью матрицы и возводим в нужную степень за логарифмическое время.
Например, для N=5 для решетки с длиной 2M там будет формула a(M) = 11a(M-1)+2a(M-3). Записываем это выражение с помощью матрицы и возводим в нужную степень за логарифмическое время.
Вы правы. но каждый видит то, что ищет :)
лично я — возможность отработать динамику по профилю
лично я — возможность отработать динамику по профилю
мне, кстати, немного не ясно как в общем виде выделять невозможные переходы, вы не могли бы на этом как-то остановиться поподробнее? объяснения, приведенные в статье, понятны, но вот даже интуитивно нет уверенности как оно будет выглядеть для N-го случая
Переходы организуются перебором всех 2m-1 способов поставить горизонтальные рёбра для каждого из разрезов.
Вам не нужно выделять невозможные переходы. Нужно переходить от одного разреза в те, в которые возможно. А невозможные переходы — это когда некоторая комбинация горизонтальных рёбер приводит к одному из трёх случаев, описанных в статье. Начиная с разреза 00...0 нужно построить все допустимые разрезы. Недопустимые вы автоматически даже не увидите.
Если это первая задача, которую вы решаете на динамику по профилю, я рекомендовал бы начать с задачи о димерах (или домино, или паркет). Моя задача — одна из самых сложных в этой теме. Конечно, если ограничения большие, а не детские.
Вам не нужно выделять невозможные переходы. Нужно переходить от одного разреза в те, в которые возможно. А невозможные переходы — это когда некоторая комбинация горизонтальных рёбер приводит к одному из трёх случаев, описанных в статье. Начиная с разреза 00...0 нужно построить все допустимые разрезы. Недопустимые вы автоматически даже не увидите.
Если это первая задача, которую вы решаете на динамику по профилю, я рекомендовал бы начать с задачи о димерах (или домино, или паркет). Моя задача — одна из самых сложных в этой теме. Конечно, если ограничения большие, а не детские.
про паркет читал у Василевского, спасибо.
«Переходы организуются перебором всех 2m-1 способов поставить горизонтальные рёбра для каждого из разрезов.»
да, разумеется, это ясно
«Вам не нужно выделять невозможные переходы. Нужно переходить от одного разреза в те, в которые возможно. А невозможные переходы — это когда некоторая комбинация горизонтальных рёбер приводит к одному из трёх случаев, описанных в статье.»
для построения следующего профиля мне необходимо из всех 2^m-1 состояний исключить те 3 варианта, которые вы описали, верно?
не ясно было только как эти 3 случая будут себя «проявлять» для больших N.
«Итак, предположим, что мы располагаем информацией обо всех возможных разрезах нашей решётки „
как именно получить информацию обо всех возможных разрезах для N на этапе выполнения программы?
«Переходы организуются перебором всех 2m-1 способов поставить горизонтальные рёбра для каждого из разрезов.»
да, разумеется, это ясно
«Вам не нужно выделять невозможные переходы. Нужно переходить от одного разреза в те, в которые возможно. А невозможные переходы — это когда некоторая комбинация горизонтальных рёбер приводит к одному из трёх случаев, описанных в статье.»
для построения следующего профиля мне необходимо из всех 2^m-1 состояний исключить те 3 варианта, которые вы описали, верно?
не ясно было только как эти 3 случая будут себя «проявлять» для больших N.
«Итак, предположим, что мы располагаем информацией обо всех возможных разрезах нашей решётки „
как именно получить информацию обо всех возможных разрезах для N на этапе выполнения программы?
Если честно, я не понимаю, в чём проблема. Вот взяли некий разрез. Вот он перед вами. Применяете к нему все возможные способы поставить горизонтальные рёбра для перехода. Некоторые комбинации будут давать другой разрез, некоторые будут давать абсурдную ситуацию (одну из 3-х). Выбираете только те, которые дают другой разрез.
Может я не понимаю вопроса?
Может я не понимаю вопроса?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Метод динамического программирования для подсчёта числа циклов на прямоугольной решетке