一类赋权诱导问题的多项式时间算法  

A POLYNOMIAL ALGORITHM FOR WEIGHTED ABDUCTION PROBLEM

作　　者：吴晔[1] 马绍汉[1] 

机构地区：[1]山东大学计算机科学系,中国科学院计算技术研究所CAD开放实验室

出　　处：《计算机学报》1997年第3期251-258,共8页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：本文介绍了赋权诱导推理的基本概念及其求解算法复杂性研究的现状．诱导推理在人工智能领域有广泛的应用前景，但现有的求解算法都未能从根本上排除ＮＰ－难解性的困扰，本文考虑了其中一类子问题：二阶独立赋权诱导问题，并给出求其最优解的多项式时间算法．本文还对其它诱导问题进行了分析，给出Ｐ问题与ＮＰ问题的分界线．This paper gives basic concept of weighted abduction problems and the outline of current complexity results to solve it. Abduction problems are widely used in the area of AI,but the present methods do not get rid of the difficulties of NP-hardness. This paper gives a polynomial algorithm to find the best explanation of a subclass problem of weighted abduction problems, second order independent abduction problem, and proved that solving second order independent incompatibility abduction is NP-complete. Some other P and NP-hardness weighted abduction problems are also given.

关 键 词：诱导推理 赋权诱导推理 多项式时间算法 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]