摘要
本文介绍了赋权诱导推理的基本概念及其求解算法复杂性研究的现状.诱导推理在人工智能领域有广泛的应用前景,但现有的求解算法都未能从根本上排除NP-难解性的困扰,本文考虑了其中一类子问题:二阶独立赋权诱导问题,并给出求其最优解的多项式时间算法.本文还对其它诱导问题进行了分析,给出P问题与NP问题的分界线.
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.
出处
《计算机学报》
EI
CSCD
北大核心
1997年第3期251-258,共8页
Chinese Journal of Computers
基金
国家自然科学基金
关键词
诱导推理
赋权诱导推理
多项式时间算法
算法
Abduction problem
weighted abduction problem
weighted matching
SAT problem.