動態(tài)規(guī)劃求最短路徑算法,與窮舉法相比優(yōu)點在于大大降低了時間復(fù)雜度;

1. 假如從起點A到終點S的最短路徑Road經(jīng)過點B1,那么從起點A到B1的最短路徑的終點就是B1,否則如果存在一個B2使得A到B2的距離小于B1,那么起點A到終點S的最短路徑Road就不應(yīng)該經(jīng)過B1,而應(yīng)該經(jīng)過B2,這顯示是矛盾的,證明了滿足最優(yōu)性原理;
2. 假設(shè)從A到S需要經(jīng)過N個時刻,每個時刻有M個狀態(tài)(B1,B2...BM),那么我們只需要記錄對應(yīng)每個狀態(tài)的最短路徑即可,這樣在任意時刻,只需要考慮非常有限的幾種最短路徑即可(取決于該時刻對應(yīng)的狀態(tài)個數(shù)),且不需要向上考慮之前的時刻,也就是不存在多維條件問題;
3. 結(jié)合以上兩點,假設(shè)當前我們需要從時刻i到i+1時,從起始點S到時刻i的所有最短路徑已經(jīng)找出并記錄到時刻i的所有狀態(tài)上了,那么我們只需要考慮沒時刻i的所有狀態(tài)的最短路徑連接到時刻i+1的所有狀態(tài)上后得到的對應(yīng)每個狀態(tài)的最短路徑并記錄到狀態(tài)中即可(后續(xù)計算與時刻i已無關(guān));
4. 循環(huán)3,知道終點時刻為止,此時終點的所有狀態(tài)中都保存了一個最短路徑,取其中最短即可(或者說最大概率);

Python Code:

import sys

states = ('Rainy', 'Sunny', 'Snowy', 'Thunder')
 
observations = ('walk', 'playSnow', 'clean', 'clean', 'shop', 'clean', 'walk', 'shop', 'clean', 'playSnow', 'scare', 'walk')
 
start_probability = {'Rainy': 0.4, 'Sunny': 0.3, 'Snowy': 0.2, 'Thunder': 0.1}
 
transition_probability = {
    'Rainy' : {'Rainy': 0.5, 'Sunny': 0.2, 'Snowy': 0.15, 'Thunder': 0.15},
    'Sunny' : {'Rainy': 0.1, 'Sunny': 0.5, 'Snowy': 0.3, 'Thunder': 0.1},
    'Snowy' : {'Rainy': 0.4, 'Sunny': 0.2, 'Snowy': 0.3, 'Thunder': 0.1},
    'Thunder' : {'Rainy': 0.4, 'Sunny': 0.2, 'Snowy': 0.1, 'Thunder': 0.3},
    }
 
emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.3, 'clean': 0.4, 'playSnow':0.1, 'scare':0.1},
    'Sunny' : {'walk': 0.4, 'shop': 0.2, 'clean': 0.1, 'playSnow':0.1, 'scare':0.1},
    'Snowy' : {'walk': 0.2, 'shop': 0.1, 'clean': 0.2, 'playSnow':0.4, 'scare':0.1},
    'Thunder' : {'walk': 0.1, 'shop': 0.1, 'clean': 0.4, 'playSnow':0.1, 'scare':0.3},
}

def viterbi_output(states,observations,start_probability,transition_probability,emission_probability):
    """
    states:隱狀態(tài)
    observations:觀察狀態(tài)
    start_probability:初始概率
    transition_probability:轉(zhuǎn)換概率(某個隱狀態(tài)轉(zhuǎn)換到某個隱狀態(tài))
    emission_probability:發(fā)射概率(某個隱狀態(tài)轉(zhuǎn)換到某個觀察狀態(tài))
    算法思路:
        目的:根據(jù)三天的觀察狀態(tài),計算最有可能的三天天氣隱狀態(tài)
        根據(jù):得到最后一天的概率后,其中概率最大的即表示該條狀態(tài)鏈是最有可能的隱狀態(tài)鏈
        方法:
            第一天概率:隱狀態(tài)的初始概率*該狀態(tài)到第一天的觀察狀態(tài)的發(fā)射概率
            其他天概率:前一天隱狀態(tài)的概率*前一天隱狀態(tài)到當天隱狀態(tài)的轉(zhuǎn)換概率*當天隱狀態(tài)到當天觀察狀態(tài)的發(fā)射概率
        關(guān)鍵:
            1.并不需要保存每一天的狀態(tài),實際上每天的循環(huán)計算中只會用到前一天的數(shù)據(jù)即可(因此V這個變量實際上長度為2即可)
            2.路徑的保存
    """
    V = [{}]#V[時間][天氣]=概率
    path = {}#保存路徑
    #第一天
    for state in states:
        V[0][state]=start_probability[state]*emission_probability[state][observations[0]]
        path[state]=[state]
        print "第一天概率估計:(天氣:%s,概率:%f)" % (state,V[0][state])
    #其他時間
    for day in range(1,len(observations)):
        print "第%d天概率估計:" % (day+1)
        V.append({})
        newPath = {}
        for day_s in states:
            (prop,state) = max([V[day-1][s]*transition_probability[s][day_s]*emission_probability[day_s][observations[day]],s]for s in states)
            V[day][day_s]=prop
            newPath[day_s] = path[state]+[day_s]
            print "\t假設(shè)當前隱狀態(tài)為:%s,得到最大概率:%f,對應(yīng)前一天隱狀態(tài):%s" % (day_s,prop,state)
        path = newPath
    return max([(V[len(observations)-1][prop],path[prop])for prop in V[len(observations)-1]])

if __name__ == '__main__':
#argv[1]表示計算觀察的天數(shù)
    print viterbi_output(states,observations[:int(sys.argv[1])],start_probability,transition_probability,emission_probability)

時間長度為5天時的運行結(jié)果圖

運行結(jié)果圖