布尔方向差分及其在故障诊断中的应用

许多文章利用布尔差分的概念建立故障完全测试集的算法。其优点是推导清晰严谨,但其缺点是,一、所求得的测试码对应组合逻辑网络无故障时的正确输出值不能立即确定。二、计算复杂性高,特别对扇出再收敛型结构更为如此。本文作者提出布尔方向差分和沿通路布尔差分的概念,并以此为基础建立一种组合逻辑网络故障诊断测试集的算法。上述两个缺点可以克服。     

关于无向网络容量扩充的问题

将带约束的最大容量路问题扩展到约束条件含固定费用的无向网络的容量扩充问题，并给出了强多项式算法。     

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP—hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP—hard问题，并可十分容易地推广到多维欧氏空间．     

求解图最大团的并行算法

本文给出了一个求解图中最大团的异步并行算法。在算法中采用了最优先搜索和分枝限界法等人工智能搜索技术,避免了无意义的搜索。其特点是易于在共享内存多处理机的并行计算机上实现,其执行时间曲线表明,对图中任意2点之间边存在概率小于1/3的无向图,具有较高效率的求解过程。还给出了在一定条件限制下,求解 NP—完全问题的方法。     

非凸复盖问题的近似算法

本文讨论了一维空间中的非凸复盖问题。其中复盖点所使用的每一个非凸部件,都是一维非正规环。这是个强 NP—完全问题。我们采用移动策略,给出了这类问题的一系列多项式时间近似算法。     

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP-hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP-hard问题，并可十分容易地推广到多维欧氏空间．     

一种新的显式与或图搜索算法

给出了一种新的能找出含圈与或图的最佳解图的算法，证明了其正确性，并分析了其复杂性．     

缩减MAX SAT问题中变元个数的多项式时间算法

针对ＭＡＸ ＳＡＴ问题，提出一个缩减变元个数的多项式时间算法，若Ｔ是ＭＡＸ ＳＡＴ问题的任何一个实例，该处法将其转化为另一个实例Ｐ，具Ｐ中的变元个数小于Ｔ中的子句个数，在采用其他算法求出Ｐ的最优解后，可用Ｐ的最优解构造Ｔ的最优解。此算法可作为一个有效的预处理处理。