如何簡單地理解維特比演算法(viterbi演算法)?

時間 2021-06-04 00:32:14

1樓:

剛開始看數學之美遇到viterbi演算法(維特比演算法)的,我引用一下我另外一篇回答:

如何通俗地講解 viterbi 演算法?

如下圖,假設你從S和E之間找一條最短的路徑,除了遍歷完所有路徑,還有什麼更好的方法?

維特比演算法解決的是柵欄圖的最短路徑問題,圖的節點按列組織,每一列的節點只能和相鄰的列的節點相連,不能跨列相連,節點之間有著不同的距離,距離的值就不在圖上全部標註出來了,大家自行腦補。

答案:維特比演算法(viterbi)。

為了找出S到E之間的最短路徑,我們先從S開始從左到右一列一列地來看。

首先從S到A列的路徑,有三種可能:S-A1、S-A2、S-A3,如下圖:

我們不能武斷的說S-A1、S-A2、S-A3中的哪一段肯定是最短路徑中的一部分。

我們接下來在看B列,B列的B1、B2、B3乙個個地來分析。

先看B1:

如上圖,經過B1的路徑有3條:

S-A1-B1

S-A2-B1

S-A3-B1

這三條路徑中我們肯定可以知道其中哪一條是最短的,假設S-A3-B1是最短的,那麼我們就得出了,經過B1的所有路徑當中S-A3-B1是最短的,其它兩條路徑路徑S-A1-B1和S-A2-B1可以刪掉了。

接下來,我們繼續看B2:

如上圖,經過B2的路徑有3條:

S-A1-B2

S-A2-B2

S-A3-B2

這三條路徑中我們肯定可以知道其中哪一條是最短的,假設S-A1-B2是最短的,那麼我們就得出了,經過B2的所有路徑當中S-A1-B2是最短的,其它兩條路徑路徑S-A2-B2和S-A3-B1可以刪掉了。

接下來我們繼續看B3:

如上圖,經過B3的路徑有3條:

S-A1-B3

S-A2-B3

S-A3-B3

這三條路徑中我們肯定可以知道其中哪一條是最短的,假設S-A2-B3是最短的,那麼我們就得出了,經過B3的所有路徑當中S-A2-B3是最短的,其它兩條路徑路徑S-A1-B3和S-A3-B3可以刪掉了。

現在對於B列的所有節點我們都過了一遍,看看我們找到多少條最短路徑:

我們我們刪掉了其它不可能是最短路徑的情況,留下了三個可能的最短路徑:S-A3-B1、S-A1-B2、S-A2-B3,彙總到下圖:

S-A3-B1、S-A1-B2、S-A2-B3都有可能是全域性的最短路徑,我們不能武斷地說哪一條一定是全域性最短路徑的一部分。

如果我們你認為沒毛病就繼續往下看C列,如果不理解,回頭再看一遍。

講到C列了,類似B列,我們從C1、C2、C3乙個個節點分析。

經過C1節點的路徑有:

S-A3-B1-C1、

S-A1-B2-C1、

S-A2-B3-C1

我們肯定能從這三條路徑中過找到最短的那條,例如:S-A3-B1-C1,其它兩天就刪掉好了。

同理,我們可以找到經過C2和C3節點的最短路徑,彙總一下:

在C列也只剩3條備選的最短路徑,我們仍然不能武斷地判斷哪條最短。

我們繼續看E了。

到E也只有3種可能性:

我稍微對比一下這三條路徑就能得到最短路徑了

中午不睡覺,一時興起畫的圖,略顯粗糙,將就看吧

如何最簡單 通俗地理解Softmax演算法?

老杜 softmax就是soft版本的max,理解了soft的含義就理解softmax了。什麼叫soft版本?我們先看看普通的max,以及普通max hard在什麼地方。比如說三個數x 2,1,5 求max x 小學生都會,答案是5,很簡單.如果以向量的方式表達這個對映關係,也可以表示成max x ...

如何最簡單 通俗地理解決策樹演算法?

雲朵 決策樹 Decision tree 是一種基本的分類與回歸方法,是一種非引數的有監督學習方法。決策樹是一種樹狀結構,它的每乙個葉子結點對應著乙個分類,非葉子結點對應著在某個屬性上的劃分,根據樣本在該屬性上的不同取值降氣劃分成若干個子集。其基本原理是通過遞迴切割的方法來尋找最佳分類標準,進而最終...

如何通俗簡單地理解 Inbound Marketing 和 Outbound Marketing

吳嘉陽 簡單一句話,以客戶需求的強烈程度分 主動營銷 inbound marketing 使用者需求相對較高,使用者主動索取產品相關資訊 和被動營銷 outbound marketing 使用者需求相對較低,被動被強推來索取產品資訊 劉延飛 Inbound marketing會慢慢成為marketi...