14.4.3 精确推理的复杂度
我们论证了由于变量消元避免了重复的计算（也能够去除无关变量），它比枚举算法更高效。变量消元算法的时间和空间需求取决于算法运行过程中构造出的最大因子，而后者又进一步取决于变量消元次序和网络结构。
图14.2所示的防盗网络属于这样一个网络家族：网络中任何两个节点都至多只有一条无向路径相连。这种网络结构称为单连通（singly connected）网络或者多树（polytree），有一个特别好的性质：多树上的精确推理的时间与空间复杂度都与网络规模呈线性关系。这里，网络规模定义为条件概率表中的条目个数；如果每个节点的父节点个数都不超过某个常数，那么复杂度与网络节点个数呈线性关系。这个结论对于与网络拓扑次序相一致的任何节点次序都成立（习题14.7）。
对于多连通（multiply connected）网络，如图14.11（a）所示，在最坏情况下变量消元算法可能具有指数级的时间和空间复杂度，甚至在每个节点的父节点个数有固定界限的情况下。这并不令人惊讶，如果考虑到“因为概率推理包含命题逻辑推理作为它的一种特殊情况，所以贝叶斯网络的推理是一个NP 问题 ”。事实上，可以证明（习题14.8）这个问题与计算命题逻辑公式中可满足的赋值个数的问题难度相当。这意味着它是一个#P难题（“个数P难题”，“number-P hard”）——也就是说，严格地难于NP完全问题。
贝叶斯网络推理的复杂度和约束满足问题（CSP）的复杂度有密切的关系。如我们在第五章中讨论的，求解离散约束满足问题的难度与其约束图究竟在多大程度上“类似于树形结构”相关。诸如超树宽（hypertree width）这样的能够限制求解约束满足问题复杂度的度量，也能够直接应用于贝叶斯网络。而且，变量消元算法还可以推广，用于求解约束满足问题，如同求解贝叶斯网络上的查询。
图14.11 （a）一个多连通网络及其条件概率表。（b）多连通网络的一个团等价物
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
