权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A Hypothetical Reasoning Method for Computing Near-optimal Solution in polynomial Time

多项式时间内计算近最优解的假设推理方法

基本信息

批准号：
06452398
负责人：
ISHIZUKA Mitsuru
金额：
$ 5.25万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (B)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至 1995
项目状态：
已结题

项目摘要

We have achieved a meaningful result in the area of efficient cost-based or weighted) hypothetical reasoning for computing a near-optimal solution which satisfies all given constraints. Prior to this research, we developed a polynomial-time cost-based hypothetical reasoning method, in which the set of described knowledge is transformed into linear inequalities and then an effioient approximate solution method of 0-1 integer programming called pivot and compliment method is applied to compute a near-optimal solution in polynomial time. While this method is very effective, it is hard for us to grasp its behavior operated in mathematical domain ; as a result, we can not improve its efficiency further by considering the knowledge structure of given problems. Thus we have developed a polynomial-time hypothetical reasoning method called networked bubble propagation (NBP) method, which performs an inference operation conceptually similar to the pivot and compliment method on a unique knowledge network. The time-consuming pivoting operation exchanging the states of basis and non-basis nodes (variables in 0-1 integer programming) is improved by considering the knowl-edge structure. The low-order polynomial-time efficiency of the NBP method is shown experimentally. It can be said that the result of this research is also meaningful in bridging symbol-oriented Al reasoning and OR (operation research) computation operated mathematically in multi-dimensional numerical domains.

在计算满足所有给定约束的近似最优解的有效、基于成本或加权的假设推理方面，我们已经取得了有意义的结果。在此之前，我们提出了一种基于多项式时间代价的假设推理方法，将所描述的知识集转化为线性不等式，然后应用一种有效的0-1整数规划的近似解方法--枢轴补法在多项式时间内计算出近最优解。虽然这种方法是非常有效的，但我们很难掌握它在数学领域的行为，因此，我们不能通过考虑给定问题的知识结构来进一步提高它的效率。因此，我们开发了一种多项式时间假设推理方法，称为网络气泡传播(NBP)方法，它在概念上执行的推理操作类似于在唯一知识网络上的枢轴和互补方法。通过考虑知识边结构，改进了基结点和非基结点(0-1整数规划中的变量)交换状态的旋转运算。实验证明了NBP方法的低阶多项式时间效率。可以说，本研究结果对于衔接面向符号的逻辑推理和运筹学在多维数域中的数学运算也是有意义的。