解题思路
题目要求对每条观测序列，求：
- 最优隐藏状态序列
- 该最优路径对应的对数概率 logP(q^,o)
这正是经典的Viterbi 算法问题。
P4588.第2题-离散型隐马尔可夫模型预测
题目内容
请在仅使用 numpy 的前提下，实现离散型隐马尔可夫模型 (HMM) 的 Viterbi 动态规划。
给定：
-
初始分布 π∈RN
-
状态转移矩阵 A∈RN×N
-
观测概率矩阵 B∈RN×M (列索引=观测符号)
-
多条离散观测序列 {o(s)}s=1S ，符号取值 0...M−1
请为每条序列计算
1.最优隐藏状态序列 q^(s)=(q1,…,qT)
2.该序列的对数概率 logP(q^,o)
实现要求
-
对数域计算，避免下溢：所有乘法用 log+，求和用 logsumexp 或 np.logaddexp.reduce
-
只需前向传递 + 回溯，无需 forward/backward 或 EM 训练
-
所有浮点以 float64 计算；输出对数概率保留 6 位小数(四舍五入)
输入描述
单行 JSON:
{
"pi":[0.6,0.4], //长度N
"A": [[0.7,0.3],[0.4,0.6]], // N×N
"B": [[0.5,0.4,0.1],[0.1,0.3,0.6]], // N×M
"obs":[[0.0],[2.2]...] //S条序列，符号整数
}
-
N≤4,M≤4，序列长度 T≤6,S≤10
-
所有概率矩阵行各自已归一化；不必检验
输出描述
仅一行 JSON:
{
"paths":[[q11,q12,...],[q21,...],...], //每条序列最优路径
"logp":[-2.253795,-2.448768,...] //对应对数概率，使用 round(x,6) 保留小数位
}
次序须与输入 obs 保持一致。
补充说明
为确保通过测试用例，仅允许使用 numpy 。
样例1
输入
{"pi":[0.6,0.4],"A":[[0.7,0.3],[0.4,0.6]],"B":[[0.5,0.4,0.1],[0.1,0.3,0.6]],"obs":[[0,0]]}
输出
{"paths": [[0, 0]], "logp": [-2.253795]}
