题目内容

在一个智能系统中，内部存在有限的模式，系统在每个时间步按照一定概率切换模式，并在当前模式下输出一个离散信号。给定系统的初始模式分布 $\pi$、模式间转移矩阵 $A$、每种模式下输出各个信号的概率矩阵 $B$，以及若干条观测到的信号序列，你需要为每条信号序列推断最可能的内部模式序列（最优路径），并计算该路径的对数概率。

要求：

• 全部计算在对数域进行，避免浮点下溢。乘法转为对数加法，求和时使用 numpy.logaddexp.reduce 或类似对数加法运算。
• 使用动态规划求解最优路径，只进行前向递推与回溯，无需前向/后向算法或参数训练。
• 所有浮点数使用 float64 类型，最终对数概率四舍五入保留 6 位小数。
• 只允许使用 numpy 库。

约束：模式数量 $N$ 不超过 4，信号种类数量 $M$ 不超过 4，每条信号序列长度 $T$ 不超过 6，信号序列总条数 $S$ 不超过 10。输入的所有概率矩阵行各自已归一化，不必另行检验。

输入描述

输入包含一行字符串，其格式为自定义的对象表示法，类似于 JSON 但可能缺少引号或包含无关字符。该字符串包含以下字段："pi"、"A"、"B"、"obs"，各字段值使用方括号列表表示，数值为整数或浮点数。具体格式请参照样例输入，并自行处理字符串中的不规范写法。

输出描述

输出一行 JSON 字符串，包含以下字段：

• "paths": 列表，每个元素是一个由模式编号构成的列表，表示对应信号序列的最优内部模式路径。
• "logp": 列表，元素是每个最优路径的对数概率（四舍五入保留 6 位小数），与输入信号序列顺序一致。

样例1

输入

{"pi": [0.8, 0.2], "A": [[0.9, 0.1], [0.2, 0.8]], "B": [[0.7, 0.3], [0.4, 0.6]], "obs": [[0, 1]]}

输出

{"paths": [[0, 0]], "logp": [-1.889152]}

说明

系统有 $N=2$ 个模式，$M=2$ 种信号。

首先将所有概率转换为对数：$\ln \pi = [\ln 0.8,\ \ln 0.2] \approx [-0.223144,\ -1.609438]$，对数转移矩阵 $\ln A$ 和对数发射矩阵 $\ln B$ 同理计算。

观测序列为 $[0, 1]$，长度为 $T=2$。

• 初始时刻 $t=0$（观测 0）： $\text{dp}[0][0] = \ln 0.8 + \ln 0.7 \approx -0.579819$ $\text{dp}[0][1] = \ln 0.2 + \ln 0.4 \approx -2.525729$ 较大值为状态 0。

• $t=1$（观测 1）： 对状态 0：最大前驱来自状态 0，值约为 $-0.685179$，加上 $\ln 0.3$ 得 $-1.889152$。 对状态 1：最大前驱来自状态 1，值约为 $-2.748872$，加上 $\ln 0.6$ 得 $-3.259698$。 最终 $\text{dp}[1]$ 中状态 0 更大。

回溯得到最优路径 $[0, 0]$，对数概率四舍五入为 -1.889152。

样例2

输入

{"pi": [0.3, 0.3, 0.4], "A": [[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]], "B": [[0.6, 0.4], [0.1, 0.9], [0.8, 0.2]], "obs": [[1], [0, 1, 0]]}

输出

{"paths": [[1], [2, 1, 0]], "logp": [-1.309333, -4.163566]}

说明

系统有 $N=3$ 个模式，$M=2$ 种信号。共 $S=2$ 条观测序列。

第一条序列 $[1]$（长度 $T=1$）： 直接计算初始对数概率加对应发射对数概率。

• 状态 0：$\ln 0.3 + \ln 0.4 \approx -2.120264$
• 状态 1：$\ln 0.3 + \ln 0.9 \approx -1.309333$
• 状态 2：$\ln 0.4 + \ln 0.2 \approx -2.525729$ 最大值对应状态 1，路径为 $[1]$，对数概率 -1.309333。

第二条序列 $[0, 1, 0]$（长度 $T=3$）：

• $t=0$（信号 0）：$\text{dp}[0] = [-1.714798, -3.506558, -1.139434]$，最大为状态 2。
• $t=1$（信号 1）：利用 $\ln A$ 和 $\text{dp}[0]$ 递推，得 $\text{dp}[1] \approx [-3.324236, -2.448768, -3.442019]$，最大为状态 1，前驱为状态 2。
• $t=2$（信号 0）：继续递推得 $\text{dp}[2] \approx [-4.163566, -5.444500, -4.281349]$，最大为状态 0，前驱为状态 1。 回溯得出路径 $[2, 1, 0]$，对数概率四舍五入为 -4.163566。