在人工智能范围中,不确定性推理泛指除精确推理以外的其它各种推理问题。包括不完备、不精确知识的推理、模糊知识的推理、非单调性推理等。在众多不确定性推理方法中,贝叶斯网(Bayesian belief networks)是属于一种基于模型的内涵方法。简单来讲,它提供了特定领域知识的一种模型表示以及基于这种模型的若干种学习和推理机制,用于建立模型并回答与这些领域知识相关的问询,并在此基础上进行辅助预测、决策及分析。自贝叶斯网出现以来,其推理计算一直是人工智能中研究的热点和难点之一。贝叶斯网推理方法分为精确和近似两大类。联结树方法是一种经典的贝叶斯网精确推理方法,在贝叶斯网推理中具有重要地位。联结树算法首先对贝叶斯网进行三角化,再转换为联结树,然后在联结树上进行信念传播,完成推理计算。将贝叶斯网以最优形式进行三角化,以使推理计算效率最高,是联结树算法的关键所在。对于给定的贝叶斯网络,寻找一个三角化图,使得其中的最大团簇的所含节点数最少,这类最优三角化问题称作树宽度(tree width)问题;另一类最优三角化问题称作树费用(tree cost)问题,其目标是使得三角化图中所有团簇的状态空间最小,这类问题与贝叶斯网的精确推理算法关系更为密切。树费用问题不仅对联结树方法,对变量消去方法、调节方法、可分解否定范式方法等其他各种精确推理方法也具有重要意义。在目前流行的求解树费用问题算法研究方面,主要的工作都是基于2012年Ottosen和Vomlel提出的Depth-first-search和Best-first-search算法,他们通过实验证明了Depth-first-search与Best-first-search的运行时间几乎相等,而前者使用的内存更少。之后,Li和Ueno对Depth-first-search进行改进,进一步提高了Depth-first-search的运行效率。本文的工作之一是基于Li和Ueno的工作,进一步改进Ottosen和Vomlel的Best-first-search算法,并更为仔细地研究Best-first-search相对于Depth-firstsearch的优缺点。为评估提出改进算法的性能,我们在一组贝叶斯网络上标准测试用例(http://www.cs.huji.ac.il/site/labs/compbio/Repository/)上进行了算法性能测试。实验结果表明,我们所提出的Best-first-search搜索算法,相对于Ottosen和Vomlel的Best-first-search算法,甚至和当前最好的Depth-first-search算法相比,在时间上和访问节点数量两个方面都有明显的优势。本文的工作之二是基于所提出的Best-first-search搜索算法,设计了一个可以编辑贝叶斯网络结构并进行推理计算的软件,并进一步实现一个可用于简单打印故障诊断的程序,以此来验证Best-first-search搜索算法的实用性。实验表明,我们所提出的算法具有一定的应用价值。