動態規劃算法
維特比算法是一種動態規劃算法，主要用於尋找最有可能產生觀測事件序列的隱含狀態序列，這種算法特別適用於馬爾可夫信息源和隱馬爾可夫模型(HMM)的上下文中。
維特比算法由安德魯·維特比於1967年提出，最初套用於數字通信鏈路中解卷積以消除噪音。它被廣泛套用於CDMA、GSM數字蜂窩網路、撥號數據機、衛星通信、深空通信和802.11無線網路中解卷積碼。維特比算法也常用於語音識別、關鍵字識別、計算語言學和生物信息學等領域。例如，在語音識別中，聲音信號作為觀測到的事件序列，而文本字元串則被視為隱含的產生聲音信號的原因，因此可以對聲音信號套用維特比算法來尋找最可能的文本字元串。
維特比算法的核心思想是通過動態規劃的方式，在每個時間步選擇最優路徑，從而降低時間複雜度。它通過保存之前的最優路徑，再選擇當前步的最優路徑並記錄，以此來減少重複計算。在具體實現中，維特比算法從第一個觀測開始，遞歸地計算到當前時刻為止的最優路徑機率，並記錄下這些路徑。最終，通過回溯這些機率最高的路徑，可以找到從開始到結束的最優路徑。