Найдите путь с максимальной вероятностью между двумя вершинами в марковской модели

Question

Учитывая марковскую модель, которая имеет начальное состояние с именем S и состояние выхода с именем F, и эта модель может быть представлена ​​как ориентированный граф с некоторыми ограничениями:

1. Каждое ребро имеет некоторый вес лежит в диапазоне (0,1] в качестве вероятности перехода.

2. весов ребер, выходящих из каждой суммы узла 1.

Вопрос в том, как ранжировать пути между начальным состоянием и состоянием выхода? Или, точнее, как найти путь с наивысшей вероятностью?

С одной стороны, весовые коэффициенты являются вероятностями, поэтому чем длиннее путь, тем меньше будут продукты, поэтому одна эвристическая стратегия заключается в выборе более коротких путей и более крупных кандидатов веса; но может ли эта проблема быть преобразована в проблему кратчайшего пути или с использованием какого-то адаптированного алгоритма Витерби или какого-либо алгоритма DP для решения?

Answer 1

Преобразование ваших вероятностей в пространство журнала (база данных не имеет значения). Теперь вероятность пути становится суммой весов логарифма (поскольку log(ab) = log(a) + log(b). Поскольку веса/вероятности равны < 1, весы в лог-пространстве будут отрицательными, а путь имеет наибольший вес.

Чтобы принести его больше в регулярную проблему вы можете свести на нет все весы пространства журнала, чтобы все они были положительными, и вы ищете самую низкую сумму. На этом этапе вы можете запускать стандартные алгоритмы (Dijkstra будет простым и очень быстрым), чтобы найти путь к вам ищем Если у вас есть сумма, то свести на нет его и вычислить экспоненциальным, чтобы получить вероятность

TL; DR:.. заменить все вес ш с -log (ш) и запустить с Алгоритм Дейкстры новых весами

.