1樓：無言
到達第n層的最優路徑未必是到達第n-1層的最優路徑（貪心法）。
然而，到達第n層的最短路徑必然會通過第n-1層的某個節點。假設第n-1層有 個節點，那麼可以通過保留分別到達第n-1層 個節點的最優路徑，然後遍歷剩下的 條路徑求得到達第n層的最優路徑。本質上屬於動態規劃演算法，剔除不可能解，減少計算複雜度。
與貪心法的區別，貪心是每一層都選當前的最優路徑。在第n-1層，只會保留到達這一層 個節點中的最優路徑，即只會保留一條路徑，然後遍歷剩下的 條到第n層路徑找最優解。
最後放個複雜度。假設共有N層，第n層節點數為 ，並設D為 中的最大值。
遍歷：Viterbi(動態規劃)：
貪心法：
前兩種演算法都能找到最優解，貪心法未必能找到。
2樓：gongel
求A到E的最短路徑：
Min(A->E)=Min((Min(A->D1)+D1->E),(Min(A->D2)+D2->E),(Min(A->D3)+D3->E))=Min(15+4,14+8,12+5)=17(A->B3->C1->D3->E)
也就是儲存起始節點到所有節點的最小路徑，最後在達到終點前進行比較。
3樓：半碗魚
前面有大佬給的發燒例子是正解了，本小白終於看懂了。
在第i天，我們只用關心第i天發燒的最大概率路徑與第i天正常的最大概率路徑，其他不用記。
如果某天健康，無論他表現正常冷頭昏，他的往日最優路徑是不會變的。
這樣每天其實只用考慮2種往日可能。
如果有k個健康狀態，每天考慮的路徑只有k個，不會因為天數增加像列舉法導致要考慮的路徑增加。
4樓：
發現大部分答案和講義都只介紹了前向計算的過程，沒有明確說明backtracing的過程。劍橋大學的這個寫的挺清楚的：https://www.
cl.cam.ac.uk/teaching/1
617/MLRD/slides/slides9.pdf
5樓：趙易明
講下HMM裡估計狀態路徑的 Viterbi 演算法。
某晚，月高風黑。宿舍臥談，單身良久的小王發表感言：
— 我好喜歡隔壁班花花
— 如果花花願意做我女朋友，我願意給她買個LV
— 可是我好窮啊，為了買起LV我一定要好好學習當個優秀的程式設計師好好掙錢
— 可是當乙個優秀的程式設計師並不是一蹴而就的。嗯！我應該報個補習班什麼的。
平日裡小王還是挺言必信行必果的，聽到這話的我當時信以為真。若干月後，偶然發現小王床頭多了一本C++，我心裡暗自一驚：
「這B不會報了補習班了吧？！」
「不會想當個賺錢的程式設計師吧？！」
「不會想買LV了吧？！」
「不會吧，花花已經追到手了？！！！」
簡單來說就是了解每一步結果最可能的起因，然後根據最終結果，步步反推每乙個起因，這也是我們最習以為常的推理方法。
6樓：
@Kiwee 解釋得比較清楚了，網上很多教程抄來抄去，不是太囉嗦，就是講得不清不楚的。
我是看jhu的Ben Langmead的ppt看懂的，http://www.
cs.jhu.edu/~langmea/resources/lecture_notes/hidden_markov_models.pdf
7樓：Kiwee
最高票的回答結果是正確的，但是並沒有把viterbi演算法講明白，尤其是其中的dp思想。可以用相同的例子來解釋：
1.題目背景：2.已知情況：
隱含的身體狀態 =
可觀察的感覺狀態 =
月兒預判的阿驢身體狀態的概率分布 =
這就是初始狀態序列。
月兒認為的阿驢身體健康狀態的轉換概率分布 =
這樣就可以列出相應的狀態轉移矩陣。（人懶。。不想編輯公式了）
月兒認為的在相應健康狀況條件下，阿驢的感覺的概率分布 =
這樣就可以列出相應的觀測矩陣。
由上面我們可以發現，HMM的三要素都齊備了，下面就是解決問題了。
阿驢連續三天的身體感覺依次是： 正常、冷、頭暈 。
3.題目：
已知如上，求：阿驢這三天的身體健康狀態變化的過程是怎麼樣的？即已知觀測序列和HMM模型的情況下，求狀態序列。
4.過程：
初始化。第一天的時候，對每乙個狀態（健康或者發燒），分別求出第一天身體感覺正常的概率：P(第一天健康) = P(正常|健康)*P(健康|初始情況) = 0.
5 * 0.6 =0.3P(第一天發燒) = P(正常|發燒)*P(發燒|初始情況) = 0.
1 * 0.4 =0.04第二天的時候，對每個狀態，分別求在第一天狀態為健康或者發燒情況下觀察到冷的最大概率。
在維特比演算法中，我們先要求得路徑的單個路徑的最大概率，然後再乘上觀測概率。P(第二天健康) = max*0.4=0.
3*0.7*0.4=0.
084 此時我們需要記錄概率最大的路徑的前乙個狀態，即0.084路徑的前乙個狀態，我們在小本本上記下，第一天健康。 P(第二天發燒)=max*0.
3=0.027, 同樣的在0.027這個路徑上，第一天也是健康的。
第三天的時候，跟第二天一樣。P(第三天健康)=max*0.1=0.
00588，在這條路徑上，第二天是健康的。P(第三天發燒)=max*0.6=0.
01512,在這條路徑上，第二天是健康的。
最後一天的狀態概率分布即為最優路徑的概率，即P(最優)=0.01512，這樣我們可以得到最優路徑的終點，是發燒
由最優路徑開始回溯。請看我們的小本本，在求得第三天發燒概率的時候，我們的小本本上面寫的是第二天健康，好了，第二天就應該是健康的狀態，然後在第二天健康的情況下，我們記錄的第一天是健康的。這樣，我們的狀態序列逆推出來了。
即為：健康，健康，發燒。
簡略的畫個圖吧：
這兒的箭頭指向就是乙個回溯查詢小本本的過程，我們在編寫演算法的時候，其實也得注意，每乙個概率最大的單條路徑上都要把前乙個狀態記錄下來。
8樓：青衣修羅
看到乙個英文的pdf，很詳細的講解了 viterbi演算法。
9樓：hain
我盡量通俗的解釋一下：A序列是已知的，狀態有限，比如：a1, a2, a1, a3。
B序列也是狀態有限，但是不知道B序列的排列。A序列及B序列內在有聯絡，得知在B序列狀態轉移會對應A序列狀態轉移的乙個概率矩陣。維特比就是計算在這種情況下，B序列的最大可能序列。
10樓：張無忌
簡單理解就是最短路徑是由途徑點之間最短路徑組成的，所以每個節點儲存到當前節點最短路徑資訊就可以，最後用這些最短路徑來找到全域性的最短路徑
11樓：jinming
如果你知道前向後向演算法的，注意理解的點：
每個隱含狀態記錄的是達到這個隱含狀態的前一時刻的最優的隱含狀態，則通過最後乙個時刻概率最大的狀態就能回溯找到唯一的最優路徑
12樓：sivan
很多人都用隱馬爾科夫模型來回答viterbi演算法，其實viterbi演算法只是解決隱馬第三個問題（求觀察序列的最可能的標註序列）的一種實現方式。這個問題可以用於viterbi演算法實現，也可以用其他方式實現（如窮舉法）；而viterbi演算法可以用於解決隱馬第三問題，也可以用於解決其他問題。所以千萬不要把viterbi演算法和隱馬爾科夫模型等價了。
viterbi演算法其實就是多步驟每步多選擇模型的最優選擇問題，其在每一步的所有選擇都儲存了前續所有步驟到當前步驟當前選擇的最小總代價（或者最大價值）以及當前代價的情況下前繼步驟的選擇。依次計算完所有步驟後，通過回溯的方法找到最優選擇路徑。符合這個模型的都可以用viterbi演算法解決，隱馬模型的第三問題剛好符合這個模型，所以才採用了viterbi演算法。
13樓：white water
建議直接看 Michael Collins 關於 HMM 部分的講義。非常簡潔明瞭。
比看國內那些講的不清不楚的效率高多了。
14樓：Robert Zhou
從卷積碼角度說一下。演算法目的是在卷積碼的Trellis圖上找到所有可能路徑中最短的一條。
簡單事實：走在最短路徑上的必要條件是向身後看時所走過的路徑是所有可能路徑中最短的那一條。
把這個事實和Trellis圖結合起來就自然而直接地得到了Viterbi演算法。完畢。
15樓：魏通
直接上題目鏈結，(Problem - 4865)。
Viterbi Algorithm都是扯淡，動態規劃才是王道。
（我說的都是乾貨啊！
16樓：銘洋
以最大概率為準則獲取隱狀態序列，先選取最大概率的第乙個隱狀態，然後在確定第乙個狀態的基礎上以最大概率準則選擇第二個隱狀態，下面依次進行，由此獲得乙個隱狀態序列。
17樓：
1計算乙個觀測量在所有隱狀態下所有前乙個隱狀態轉移概率，找到每個隱狀態最有可能前乙個隱狀態；
2用同樣方法計算所有觀測量的所有隱狀態的轉移概率；
3找到轉移概率最大的路徑，對應的隱狀態序列為所求序列；
18樓：順子
我覺得樓主的最後結果是對的，就是公式錯了
P(前一天發燒，今天發燒) = P(發燒|前一天)*P(發燒->發燒)*P(冷|發燒) = 0.04 * 0.6 * 0.3 = 0.0072
P(前一天發燒，今天健康) =P(健康|前一天)*P(發燒->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
P(前一天健康，今天健康) =P(發燒|前一天)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 =0.084
P(前一天健康，今天發燒) = P(健康|前一天)*P(健康->發燒)*P(冷|發燒) = 0.3 * 0.3 *.03 =0.027這兩個地方對調一下就對了
19樓：
假設題主要去自駕旅遊，A，B，C是三個景點，但是又沒有直達的路。想去A，必須從1或者2這兩個大城市之一去；想去B，必須從3或4；想去C，必須從5或6。
現在題主的旅行計畫是從家出發，第一天玩A，第二天B，第三天C。大城市之間的、大城市到景點的公路如圖，里程都知道。
維特比演算法告訴你如何找條最近的路一路玩A，B，C。省點油嘛。如果暴力求解，即求出圖中任何兩點之間的里程，再比較，計算機受不了。所以採用動態規劃思想，大家有了維特比演算法。
A、B、C是觀察，城市是狀態。城市之間的里程是轉移概率（的對數）。城市到景點的距離（來回）是分布概率（的對數）。
但以上只是抽象化這個演算法幫你理解演算法的過程，隱去了物理意義。它的本質還是HMM模型。
如何通俗地講解 仿射變換 這個概念？
在同維度的變換公式上，旋轉和平移是兩種表達處理。增加一條座標系的維度，而平移和旋轉在高維座標系下都只是旋轉，且座標原點不動，因此一種表達公式就夠了。具體的過程景象，參照最高票的答案。仿射 這名字我理解為 模仿照射光線 ps 仿射變換的 照射光線 必須是平行光，如果是發散的點光源，則為 射影變換 co...
如何通俗易懂地給外行講解金融知識？
金融的本質，是投資與融資。融資的模式，無外乎股權融資 債權融資兩種，主要區別在於是否有明確的融資期限和融資利率。股權融資，就是有福同享 有難同當的融資模式。債權融資，就是賺了不多分 虧了不免單的融資模式。所有融資端的金融產品，都是圍繞著這兩個基本點展開的。投資，其實就是融資的反向操作而已。 惠子 比...
如何通俗易懂地講解網路七層協議？
龍江六叔 你作為使用者想發個快遞，你叫來了順豐，順豐快遞員從你手裡拿走了快遞，又裝進乙個盒子，然後把乙個快遞單子貼在了上面。快遞員回到集散中心，將快遞往那一扔不管了，分揀員把快遞按投遞的省市分開，發往同一地區的快遞放進乙個大快遞包。快遞包上有乙個單子。晚上大車司機來了，把按他的行進路線把所有大包放上...