Минимизация энергии MRF

[MGM]

В общем случае минимазация энергии MRF - задача экспоненциальной сложности.
Если вес перехода от одного соседнего состояния к другому линейная метрика относительно индекса состояния (пропорциональна абсолютной величине разности соседних индексов), то такую задачу можно свести к нахождению минимального сечения в направленном потоке графа.
Это уже полиномиальная сложность. В худшем случае О(куб) от количества вершин графа.
Но решение точное.

Вопрос есть ли точные решения для других метрик. Усечённый корень, к примеру, или просто усечённая линейная функция.
В той области, в которой я работаю (Computer Vision) существует мнение (сужу по публикациям),
что в этом случае существуют только аппрксимациии с помощью различных алгоритмов Линейного Программирования, или Graph Cut methods like alpha expansion and alpha- beta swap Байкова.

Я, в принципе, нашёл метод, как точно решить эту задачу с помощью гибридного метода.

Используется не совсем классический граф, и приёмы схожие с линеййным программированием.


Но не хочется начинать очень трудоёмкую работу не будучи уверенным,
что никто из математиков уже не решил эту проблему до меня.
Надеюсь, здесь есть настоящие эксперты.

[мат-ламер]

Для неэкспертов поясните пожалуйста постановку задачи. Что такое MRF?

[MGM]

мат-ламер в сообщении #222176 писал(а):

Для неэкспертов поясните пожалуйста постановку задачи. Что такое MRF?

Это очень долго.
Приблизитель так Дискретное распределение Гиббса нормализуется, логарифмируется.
Поэтому наиболее вероятное состояние можно вычислить не через максимизацию произведения, а через минимизацию суммы логарифмов.
Эту сумму обычно делят на две части, и по аналогиии с термодинамикой называют суммой кинетических энергий и вторую суммой потенциалов, химических или ещё каких.

Предполагается, что природа выбирает минимально возможную энергию.
Что и требуется найти.
Методы из классического анализа к дискретным произвольным расспределениям не применимы, заранее говорю.