| 一类赋权诱导问题的多项式时间算法 |
| |
| 引用本文： | 吴晔 马绍汉. 一类赋权诱导问题的多项式时间算法[J]. 计算机学报, 1997, 20(3): 251-258 |
| |
| 作者姓名： | 吴晔 马绍汉 |
| |
| 作者单位： | [1]山东大学计算机科学系 [2]中国科学院计算技术研究所 |
| |
| 摘 要： | 本文介绍了赋权诱导推理的基本概念及其求解算法复杂性研究的现状。诱导推理在人工智能领域有广泛的应用前景，但现有的求解算法都未能从根本上排除ＮＰ－难解性的困扰，本文考虑了其中一类子问题；二阶独立赋权诱导问题，并给出求出其最优解的多项式时间算法。
|
| 关 键 词： | 诱导推理 赋权诱导推理 多项式时间算法 算法 |
A POLYNOMIAL ALGORITHM FOR WEIGHTED ABDUCTION PROBLEM |
| |
| WU Ye. A POLYNOMIAL ALGORITHM FOR WEIGHTED ABDUCTION PROBLEM[J]. Chinese Journal of Computers, 1997, 20(3): 251-258 |
| |
| Authors: | WU Ye |
| |
| Abstract: | 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. |
| |
| Keywords: | Abduction problem weighted abduction problem weighted matching SAT problem. |
| 本文献已被 CNKI 维普 等数据库收录！ |
