All roads lead to Rome - New search methods for the optimal triangulation problem
All roads lead to Rome - New search methods for the optimal triangulation problem
复制标题
条条大路通罗马——最优三角测量问题的新搜索方法
DOI：
10.1016/j.ijar.2012.06.006
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jirí Vomlel
中科院分区：
文献类型：
--
作者：
Thorsten J. Ottosen;Jirí Vomlel
为了在贝叶斯网络中使用连接树方法进行有效的推理，需要对网络图进行三角剖分。这种三角剖分的质量在很大程度上决定了后续推理的效率，但不幸的是，三角剖分问题是np困难的。在现有的三角剖分方法中，通常使用树宽准则来确定三角剖分的最优性。但是，这个标准可能会导致比总表大小标准更困难的推理问题。因此，我们研究了深度优先搜索和最佳优先搜索的新方法，以找到最优的总表大小三角形。通过对图中团的有效动态维护，提高了搜索速度。Stix对这一问题进行了研究，本文提出了一种新的基于brown - kerbosch算法的简单方法，该方法优于Stix的方法。这种新方法是通用的，因为它可以与其他算法一起使用，而不仅仅是布朗-克博斯算法。寻找最优三角剖分的算法主要被认为是离线方法，但它们可能构成有效的任意时间启发式的基础。此外，这些方法可以精确地评估启发式的质量，并允许我们发现搜索空间中最重要的部分，以指导随机抽样。
To perform efficient inference in Bayesian networks by means of a Junction Tree method, the network graph needs to be triangulated. The quality of this triangulation largely determines the efficiency of the subsequent inference, but the triangulation problem is unfortunately NP-hard. It is common for existing methods to use the treewidth criterion for optimality of a triangulation. However, this criterion may lead to a somewhat harder inference problem than the total table size criterion. We therefore investigate new methods for depth-first search and best-first search for finding optimal total table size triangulations. The search methods are made faster by efficient dynamic maintenance of the cliques of a graph. This problem was investigated by Stix, and in this paper we derive a new simple method based on the Bron-Kerbosch algorithm that compares favourably to Stix’ approach. The new approach is generic in the sense that it can be used with other algorithms than just Bron-Kerbosch. The algorithms for finding optimal triangulations are mainly supposed to be off-line methods, but they may form the basis for efficient any-time heuristics. Furthermore, the methods make it possible to evaluate the quality of heuristics precisely and allow us to discover parts of the search space that are most important to direct randomized sampling to.
影响因子：
1.1
作者：
Tomita, Etsuji;Tanaka, Akira;Takahashi, Haruhisa
通讯作者：
Takahashi, Haruhisa