基于Tulip-DD多值决策图的多状态可靠性量化实现问询

核心问题根源 #

你当前的硬编码方法的核心缺陷在于没有沿着BDD结构递归聚合概率，而是直接把二进制节点和多状态概率做固定映射，既跳过了x0（LSB）层的分支权重计算，也没有处理x0和x1的连接关系，导致结果偏差。

实现步骤 #

• 第一步：明确编码与权重的对应关系
  Tulip-DD对4状态变量x的二进制编码规则为(x1, x0)，其中x0为最低有效位，处于BDD层级的最顶端。先根据预设的状态概率表，预计算每个二进制位的分支权重：
  • x0=1时，覆盖x=1、x=3两个状态，总权重为对应状态概率之和
  • x0=0时，覆盖x=0、x=2两个状态，总权重为对应状态概率之和
  • x1层的分支权重不需要额外映射，因为x0层的条件概率已经在递归过程中完成聚合。
• 第二步：采用自底向上的递归遍历计算
  严格遵循“先算子节点、再算父节点”的计算顺序，避免硬编码映射：
  • 终止条件：遇到真叶节点返回概率1.0，遇到假叶节点返回概率0.0
  • 递归逻辑：对每个待计算节点，先递归算出其高、低两个分支的子节点概率，再结合当前节点的位分支权重，加权聚合得到当前节点的总概率
  • 必须处理BDD的否定边标记，避免因为库的节点简化逻辑导致判断错误
• 第三步：加入记忆化缓存
  对重复出现的BDD节点缓存计算结果，避免遍历大MDD时的重复计算开销。

原有代码的问题 #

• 仅判断相邻节点的变量名，没有递归遍历所有子节点，完全跳过了x0层的概率聚合环节
• 硬编码x1节点的分支概率，没有结合BDD的实际分支连接关系
• 直接将节点与aut.true比较，没有处理否定边，容易判断错误

修正后的可运行实现 #

import numpy as np
from omega.symbolic import temporal as trl
from functools import lru_cache

aut = trl.Automaton()
aut.declare_variables(x=(0, 3))

# 预计算二进制位的分支权重
bit_weights = {
    'x_0': {
        1: 0.2 + 0.4,  # 对应x0=1覆盖的两个状态概率和
        0: 0.1 + 0.3   # 对应x0=0覆盖的两个状态概率和
    },
    'x_1': {
        1: 1.0,
        0: 1.0
    }
}

@lru_cache(maxsize=None)
def calc_node_prob(node):
    # 叶节点终止判断
    if node == aut.true:
        return 1.0
    if node == aut.false:
        return 0.0
    # 处理否定边标记
    neg_sign = -1 if node.negated else 1
    clean_node = node.__class__(node.node_id, negated=False)
    # 递归计算子节点概率
    p_high = calc_node_prob(clean_node.high)
    p_low = calc_node_prob(clean_node.low)
    # 加权聚合
    var_name = clean_node.var
    res = neg_sign * (
        p_high * bit_weights[var_name][1] + 
        p_low * bit_weights[var_name][0]
    )
    return res

# 测试x=3状态的概率计算
u = aut.add_expr('x = 3')
state_prob = calc_node_prob(u)
# 输出结果应为0.4，与预设概率一致
print(state_prob)

注意事项 #

• 实现前务必先打印实际的变量层级顺序，避免把x0和x1的权重映射搞反
• 递归过程不需要手动拆解x1分支到具体状态的映射，x0层的权重聚合已经自然完成了两个变量连接关系的计算
• 如果扩展到更多状态，只需要按照编码位的顺序，重新计算每个位的分支权重即可，不需要修改递归逻辑

内容的提问来源于stack exchange，提问作者Guilherme Larangeira