Fast algorithms for revision of some special propositional knowledge bases

In this paper,the computational complexity of propositional clause set counter-factuals is discussed.It is shown that the computational complexity of propositional clause set counterfactuals is at the second level of the polynomial hierarchy,and that the computational complexity of propositional Horn clause set counterfactuals is at the first level of the polynomial hierarchy.Furthermore,some polynomial algorithms are presented for some special propositional clauset set ,such as the unique satisfiable clause set and the clause set of which only one subset is minimally inconsistent with the input clause whose inconsistency check can be solved in polynomial time.     

一类树型知识库的更新算法

知识库的更新意即向知识库中添加新知识,同时为维护相容性而删除旧知识.已有的知识库更新方法在通常情况下都是难解的.该文从限制问题的结构出发,给出了一种当知识库对应的约束图为树时的多项式时间更新算法.在树型约束图中,算法通过一个自底向上的过程,得到更新后的知识库.     

Some Results on Matchgates and Holographic Algorithms

We establish a 1-1 correspondence between Valiant's character theory of match-gate/matchcircuit ^[13] and his signature theory of planarmatchgate/matchgrid ^[15], thus unifying the two theories in expressibility. In [3], we established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Plucker identities. The 1-1 correspondence established in this paper gives a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.     

Approximation Algorithms for 3D Orthogonal Knapsack

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ε and 8 ε , as well as an algorithm with approximation ratio 7 ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ε and 5 ε , respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.     

立体堆与分枝界限算法

分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施.     

一类两阶段杂交流水作业的近似算法

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.     

一类两阶段杂交流水作业的近似算法?

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务：第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作 NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.     

基于差分有序数组的图像匹配快速算法

本文提出了一种对模板匹配算法进行改进的快速算法。首先，对模板内所有像素进行排序并差分变换为函数F1（），将模板覆盖下的子图像函数f（x，y）累进求和变换为函数F2（），然后求取F1（）与F2（）乘积的最大值。由于模板存在大量灰度值相同的像素，经排序差分后F1（）中会有很多0和1，乘1和0的运算可以不做，从而消去了模板运算中的大量乘法和加法运算，同时在模板匹配移动过程中利用相邻窗口间的数据相关性，减少重复运算，和传统匹配算法相比，计算复杂度大大降低。     

知识库更新的研究

一、研究现状 在知识库管理中,当人们获取了新的领域知识时,就需对原有知识库进行更新.对知识库的更新,从理论上讲,主要有以下三种基本操作~[4]     

互联网通信中的信息选取与分布问题的建模与求解

讨论了互联网通信中的一个信息选取与规划问题。由于内部网的单个Web服务器容量不够大,不能容纳与日剧增的信息内容,如何将众多的信息分布到多个Web服务器上,使得每个服务器上存放的信息总量不超过各个服务器容量且避免访问瓶颈的发生;这是陈卫东等1999年提出的一个新问题,该文建立了该问题的一个优化新模型,在讨论了它的强NP－完全性,难近似性后,给出了一个伪多项式时间最优算法的一个多项式时间近似算法。     

修正的逻辑程序知识库更新方法

基于逻辑程序的知识库更新方法研究的焦点在于处理知识库的冲突问题,但代价是更新时规则库增大很快,该文提出了“修正的逻辑程序知识库更新方法”,此种方法基于一种规范知识库更新的形式化方法—修正程序,此种更新方法不仅可以最大程度地减少更新时规则库的增大,也避免了重复工作和知识库信息的丢失,还可以同时满足“替换更新”和“丰富更新”。     

Some Computational Aspects of distance-sat

In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones offered by sat solvers on sat encodings of distance-sat instances. The empirical evaluation allows us to draw firm conclusions about the respective performances of the algorithms and to relate the difficulty of distance-sat with the difficulty of sat from the practical side. A preliminary version of this paper appeared with the title “distance-sat: Complexity and Algorithms” in the proceedings of the 16 ^th National Conference on Artificial Intelligence (AAAI’99), pages 642–647, 1999.     

复杂社会网络的介数性质近似计算方法研究

随着计算机和互联网的迅猛发展,面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大,这对网络分析算法的性能提出了更高的要求 。介数值作为图的重要结构性质,广泛应用于基于图的聚类、分类算法,如何降低其计算的复杂性是急需解决的问题。目前,常用的方法是利用对最短路径长度的近似来降低低网络分析算法的复杂性,但已有的近似方法没有考虑现实大规模网络的复杂网络特性,对最短路径长度的近似方 近似计算方法,其基本思想是结合复杂网络的结构特性,利用通过网络中枢节点的路径来近似最短路径,以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算算提供了一种新颖的思路。通过与传统的介数计算方法和近的分析得到了若干有益的结论,为进一步的研究工作奠定了基础。     

Extraction of Fuzzy Knowledge Bases from Experimental Data by Genetic Algorithms

This paper deals with the problem of determination of linguistic "IF-THEN" rules from available experimental data, which is inverse to the problem of identification of nonlinear dependences by fuzzy knowledge bases. A method of genetic algorithms is proposed. The method is based on the operations of crossover, mutation, and selection of initial variants of solutions or so-called chromosomes, from which the most optimal solutions are subsequently chosen. The method is illustrated by a computer experiment consisting of the determination of knowledge on a nonlinear object with two input variables and one output variable.     

任意图支配集精确算法回顾

该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明,以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后,经过很长一段时期的沉寂,关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外,作者还盼望国内研究团体能更加重视这个快速发展的研究领域.     

无线传感器网络定位理论和算法

定位技术作为网络协议和应用的基础,已经成为无线传感器网络重要的支撑技术,是传感器网络研究的核心问题之一.系统地总结了近年来定位理论和算法的最新研究进展.全面阐述了定位问题的形式化定义、定位问题复杂度分析、基于刚性理论的定位理论和定位问题可计算性研究的最新成果.通过对定位理论的研究可以更好地揭示定位技术的本质,回答很多定位技术相关的基本问题.此外,还深入分析了近年来典型的定位算法,介绍每种算法的设计思想,分析其适用范围和不足.最后给出定位理论和定位算法未来的研究方向.     

短块移动排序算法研究

用短块移动操作对一个排列进行排序是一种染色体基因重排技术。怎样才能找出使用短块移动次数最少的排序算法是计算生物学等领域最热门的研究问题之一。给出了短块移动的最优解算法,对近似算法进行了修改。实验验证了最优解算法和近似算法在实际运行过程中都有较好的表现。     

基于差分矩因子的灰度图像矩快速算法

由于不变矩对图像的平移放大旋转的不敏感性,因此在图像处理、模式识别、场景匹配和计算机视觉等领域获得越来越广泛的应用．但是,求矩运算过程复杂,计算量大,使它的应用受到限制．快速求矩算法不少,但大多限于二值图像．文中提出一种新的适用于灰度图像的快速求矩算法．算法基于文中提出和证明的差分求和定理,即两个离散函数数组的乘积,等于将其中一个差分、另一个累进求和后的乘积．将矩因子作为一个函数数组,图像作为另一个函数数组,对矩因子数组实施多次差分,差分结果使得矩因子数组除边界1个或几个数组元素外,其余数组元素值皆为0．这样需对所有数组元素的乘积变为只对边界1个或几个数组元素的乘积．由于边界上不为0的数组元素值几乎都为1,这实际上就无需乘法计算．该算法原理简单,编程容易,求矩结果精确,适用于任意灰度图像．利用该算法,对任意大小和任意级别的灰度图像,无需任何乘法计算,且加法运算次数也大幅减少．和其它求矩算法相比,计算复杂性大大降低．     

遗传算法理论研究综述

针对遗传算法在理论研究方面存在的不足,系统地讨论了遗传算法理论研究的主要内容和方法,包括模式定理、编码策略、Ｍａｒｋｏｖ链与全局收敛性、维数分析、ＢＧＡ理论、可分离函数、Ｗａｌｓｈ与傅立叶函数分析及二次动力系统等,介绍了Ｎｏ Ｆｒｅｅ Ｌｕｎｃｈ定理,并指出相关的研究方向。