алгоритм Витерби

Это 18-й день моего участия в августовском испытании обновлений. Ознакомьтесь с подробностями мероприятия: Испытание августовского обновления

Алгоритм Витерби — это особый, но наиболее широко используемый алгоритм динамического программирования, с помощью которого можно решить задачу поиска кратчайшего пути в любом графе. Алгоритм Витерби предлагается для специального графа - задачи о кратчайшем пути ориентированного графа (решетки) сети ограждений. Это важно, потому что любая проблема, описываемая Скрытой Марковской моделью, может быть использована для ее декодирования, включая сегодняшнюю цифровую связь, распознавание речи, машинный перевод, преобразование пиньинь в китайские иероглифы, сегментацию слов и т. д.

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

Для иллюстрации возьмем относительно простой пример: найдите кратчайший путь из S в E, как показано ниже.

Прежде всего предположим, что существует кратчайший путь (красный) от S до E, и этот путь проходит через точку C2, тогда мы можем быть уверены, что среди 64 (4X4X4=64) подпутей от S до C2, подпуть должен быть кратчайшим. (Доказательство: доказательство от противного. Если между S и C2 есть более короткий подпуть, то его можно использовать для замены исходного пути, а исходный путь явно не является кратчайшим, что противоречит нулевой гипотезе)

Точно так же мы можем сделать вывод, что из точки S в точку B2 есть кратчайший подпуть между двумя точками. **В этом случае, когда мы вычисляем кратчайший путь из точки S в точку C2, должны ли мы просто рассматривать кратчайший путь из S ко всем узлам слоя B? ** Ответ - да! Потому что «глобальный кратчайший» путь от S до E должен проходить через эти «локальные кратчайшие» подпути.

Формула приведена ниже,$f(i)$за$S$к узлу$i$стоимость кратчайшего пути,$\text{dist}(i,j)$представляет узел$i$к узлу$j$расстояние. но

Псевдокод выглядит следующим образом:

f[1]=0
pre[1] = 0 # pre[i]=j表示最短路径的路程中，由j跳转到i
for i in range(point_num): # 遍历所有的点
    for j in incominglist: # 遍历所有指向这个点的路径
        best_score = inf
        score = f[j] + dist(j, i)
        if score < best_score:
            best_score = score
            pre[i] = j