python维特比算法

朱雀 2022-11-25 13:07 201阅读 0赞

# -*- coding: utf-8 -*-
    from collections import defaultdict
    
    states = ("Rainy", "Sunny")
    observations = ("Walk", "Shop", "Walk", "Shop", "Clean", "Walk", "Shop", "Walk")
    start_probability = {"Rainy": 0.6, "Sunny": 0.4}
    transition_probability = {
                                "Rainy": {"Rainy": 0.7, "Sunny": 0.3},
                                "Sunny": {"Rainy": 0.4, "Sunny": 0.6},
                             }
    
    emission_probability = {
                                "Rainy": {"Walk": 0.1, "Shop": 0.4, "Clean": 0.5},
                                "Sunny": {"Walk": 0.6, "Shop": 0.3, "Clean": 0.1},
                              }
    
    
    # 利用动态规划求解最佳路径
    def compute(obs, states, start_p, trans_p, emit_p):
        # [{}, {}, {}]  长度与obs相同, 保存每条观测路径上面的各种天气的最佳概率
        v = [{} for _ in range(len(obs))]
        # {"state1": [], "state2": []}   长度与states 相同
        path = defaultdict(list)
    
        for state in states:
            v[0][state] = start_p[state] * emit_p[state][obs[0]]
            #path[state] = ["" for _ in range(len(obs))]
            path[state].append(state)
        print(path)
        # 以时间循环,从第一天开始循环
        for t in range(1, len(obs)):
            print("========================================")
            print(obs[t])
            # y1表示的是晴天还是下雨
            for y1 in states :   # 从path中取路径，作为上一个开始的路径
                max_prob = -1
                #  print(v[t-1]){'Rainy': 0.06, 'Sunny': 0.24}
                # v[t-1]表示上一天是晴天还是雨天以及概率
                for y0 in v[t-1]:
                    print(y0)
                    # 前一天的天气概率X转移概率X发射概率
                    nprob = v[t - 1][y0] * trans_p[y0][y1] * emit_p[y1][obs[t]]
                    if nprob > max_prob:
                        # 暂时记录到y1状态节点最后的概率
                        max_prob = nprob
                        # 暂时记录到y1状态节点的上一个y0节点
                        max_state = y0
    
                # 保存到当前的y1状态的最好的概率值
                v[t][y1] = max_prob
    
                # 到上一条路径与当前的y1链接起来，作为y1状态的最好路径
                newpath = []
                for state1 in path[max_state]:
                    newpath.append(state1)
                newpath.append(y1)
                path[y1] = newpath
        # 寻找最终概率最大的路径
        prob = -1
        for y1 in states :
            if v[len(obs) - 1][y1] > prob:
                prob = v[len(obs) - 1][y1]
                state = y1
    
        # 返回路径最大的路径
        return path[state]
    
    if __name__ == "__main__":
        max_path = compute(observations, states, start_probability,
                transition_probability, emission_probability)
        for state in max_path :
            print(state)

核心还是

# 前一天的天气概率X转移概率X发射概率 #

nprob = v\[t - 1\]\[y0\] \* trans\_p\[y0\]\[y1\] \* emit\_p\[y1\]\[obs\[t\]\]