二分图最大匹配问题的分布式算法

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。     

LCS问题的一种新算法及其推广

求解LCS(Longest Common Subsequences)的通常算法,空间和时间的复杂性为O(n~2)。本文中提出的算法,空间复杂性为O(n),时间复杂性为O(n)～O(n~2),时间复杂性取决于序列中符号的分布,本算法便于并行处理及制成微处理器。 为了应用于模式识别,推广到WLCS(Weighted Longest Common Subsequences)以及LCSM(Longest Common Submatrix)。 给出了有关的定理,及算法正确性的证明。     

一种量词约束满足问题的混合易解子类

量词约束满足问题是人工智能和自动推理领域的一个重要问题.寻找多项式时间易解子类,是研究此类问题计算复杂性的关键.通过分析二元量词约束满足问题中的约束关系特征,以及量词前缀中的全称量词排列的顺序,提出了针对全称量词变量子结构的易解性质的分析方法.通过该方法,扩展了已知的基于Broken-Triangle Property的多项式时间易解子类,提出了一个更一般化的量词约束满足问题的混合易解子类.讨论了易解子类在问题结构分析中的一个应用,即通过易解子类确定量词约束满足问题的隐蔽变量集合,并通过实验分析不同易解子类所确定的集合大小.实验改造了基于回溯算法的求解器,在回溯过程中加入了易解子类的识别算法,并采用随机约束满足问题的生成模型作为测试基准.通过对比实验,验证了提出的多项式时间易解子类可以识别出更小的隐蔽变量集合,因此,新提出的易解子类在确定隐蔽变量集合方面更具优势.最后阐述了其他已有的混合易解子类也可以通过类似方法进行扩展,从而得到更多的一般化的理论结果.     

计算线段集合的相交直线及其最大存在范围

对给定的一个直线段集合S研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围——位于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n~*log,n),应用背景是模式匹配等领域.     

关于Vandermonde矩阵的串行与并行复杂性

为n+1阶Vandermonde矩阵,简称V阵。 本文首先给出求解相应线性代数方程组(简称V型方程组)的递推算法。算术运算总次数为O(n~2)级,接着进一步利用快速插值算法导出求V阵逆的O(n~2)算法,并分析了这两种算法的并行时间复杂性。     

一个新的多项式实根分离算法

本文提出了分离多项式方程P(x)=0的实根的一个新的计算机代数算法,它解决了王湘浩教授在[1]中提出的用连分数变换分离有重根多项式的实根的问题.对于有重根的n次多项式P(x),该算法具有时间复杂性上界O(n~6L~3(|P|_0)),远远优于现有的解决同样问题的计算机代数算法的时间上界O(n~(10)+n~7L~3(|P|_0)).该算法已在计算机代数系统SAC-2上实现.上机实验的结果也初步证实了新算法的优越性.     

基于离散对数的广义数字签名算法研究

回顾了Ren-Harn的广义环签名算法,但Ren-Harn的广义环签名并不能满足可转化性的定义。以Ren-Harn的方案为基础,提出了基于时间戳的Ren-Harn算法,即在算法中引入时间戳变量,同时构造出双线性映射的单向陷门函数。通过环签名算法的验证,改进方案不仅严格满足可转化性的定义,而且具有很好的安全性。在保障真实签名者对于环签名的独创性,防止信息的恶意篡改等方面有很深远的影响和意义。     

FD环境下满足PS及无α环模式分解问题研究

通过分析在FD集F的最小归并依赖集存在弱左部或弱右部冲突时所具有的性质和特征，讨论并给出了满足PS(保持FD，无损连接且满足SNF)且无α环分解的充要条件和算法，对算法的正确性、可终止性进行了证明，并对算法的时间复杂度给出了分析。     

F有内部冲突满足P2且无α环模式分解的研究

在数据库模式的无α环分解中,当数据模式R〈W,F〉的FD集F有内部冲突时,无论F是否存在广义左、右部冲突均不存在满足保持FD、无损连接、BCNF和无α环的分解。在某些实际应用中的分解只满足部分条件就够了,在分析F有内部冲突时最小归并依赖集D的特性,给出了归并依赖集满足的条件∑1和∑2,在此基础上,讨论给出了满足P2（保持FD、BCNF）且无α环分解的充要条件和算法,对算法的正确性、可终止性进行了证明,并对算法的时间复杂度给出了分析。     

用(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为()(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到()(t).     

用（）(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题,连接图是研究此问题的基本工具.现有算法构造的最好的连接图GF是基于自由区的概念而设计的,其顶数和边数分别为O(t)和O(tlogt),其中t为障碍的极边数.提出了广义自由区和极大正规划分的概念,在此基础上得到广义连接图GG,用来表征广义自由区之间的邻接情况,其顶数和边数均为()(t),且具有平面图的性质.同时还提出了基于扫描线的极大正规划分构造算法,其时间复杂度为O(tlogt);并提出规范路径的概念,以及采用"不改向"启发式策略的A*算法在广义连接图GG中寻找两点间的最短路径,算法的时间复杂度由基于GF的现有算法的O(tlogt)降低到()(t).     

大规模DEM数据并行可视域分析算法研究

可视域分析是具有高时间复杂性的地理计算,在进行大规模数字高程模型(DEM)数据的可视域分析时,传统的串行算法往往难以满足实际需求;提出一种基于环形扫描环的并行可视域分析算法,可以快速计算视点在大范围内的可视域范围,与传统的扫描线算法相比,并行环形扫描线算法以阵面方式向外扩张,从而避免了各坐标点角度的重复计算;通过试验对比发现,并行环形扫描线算法的计算效率约为ArcGIS 10.0中可视域分析的20倍,完全可以满足大规模DEM数据的可视域分析需求。     

线性四元树中轴变换

骨架和中轴变换概念运用于线性四元树,定义线性四元树中轴变换为具有一组棋盘距离值的线性四元树骨架.线性四元树中轴变换提供一种非常紧凑的区域表示法,它导致区域分割成边长为2的幂之和的最大正方形集合.提出两种算法计算一给定线性四元树的线性四元树中轴变换.最坏情况下它们的时间复杂性是O(n~2),其中n为线性四元树中四分形的数目.     

顺序统计问题研究

顺序统计问题是算法设计与分析中的一个典型的问题,即从n个元素中选出第k个最小元素。文章采用分治算法解决顺序统计问题,给出了通用算法,并对算法的复杂性进行了分析和讨论。对于子序列长度大于5的情形,该算法的最坏情形的时间复杂性为O(n)。     

Hypercube多处理器上图的最优算法

已知一个无向图G(V,E),|V|=n.本文在SIMD机器-Hype-rcube上提出了计算图的连通分支和最小生成树的两个最优算法.若Hypercu-be由P个处理器组成,则上述两个算法的时间复杂性都是O(n~2/p),1≤p且PlogP≤n.     

用Θ(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题，连接图是研究此问题的基本工具，现有算法构造的最好的连接图GF是基于自由区的概念而设计的，其顶数和边数分别为O（t)和O（tologt)，其中t为障碍的极边数，提出了广义自由区和极大正规划分的概念，在此基础上得到广义连接图GG，用来表征广义自由区之间的邻接情况，其顶数和边数均为Θ（t)，且具有平面图的性质，同时还提出了基于扫描线的极大正规划分构造算法，其时间复杂度为O(tlogt)；并提出规范路径的概念；以及采用“不改向”启发式策略的A^*算法在广义连接图GG中寻找两点间的最短路径，算法的时间复杂度由于GF的现有算法的O(tlogt)降低到Θ（t)。     

带文字改名策略的DPLL算法

限制在不可满足公式的不可满足性的证明,给出了一个改进的DPLL算法—RSMLS。新的算法带有一条对称规则(文字改名规则)和三条简化规则((1,*)-消解、子公式、重复规则)。作为一个应用实例,将RSMLS算法应用于鸽巢公式P_(n-1)~n的不可满足性证明。证明了:关于RSMLS算法,公式P_(n-1)~n有一棵反驳证明树至多带有O(n~3)个结点。     

简单无向图中H回路搜索的避圈算法

本文提出一个在简单无向图中搜索H回路的新算法,我们称之为避圈算法。我们分析的算法对于n阶简单无向图的时间复杂性亦为O(n~2·2~n),但VAX机上的程序实现和对2000例以上的64阶图的运行表明。只要G是H图,算法就可以立即找到一条H回路。而其它算法对于同样图例在10小时的连续运行时间里未能找到一条H回路。据此,我们猜测,本算法(或其改进)的时空复杂性远比我们分析的保守结果好得多,或者至少本算法也象著名的单纯形算法那样。理论复杂性很高但实际复杂性很低,因为很少出现最坏情况。本文是[1]中结论的直接结果。     

顺序统计问题研究

顺序统计问题是算法设计与分析中的一个典型的问题,即从n个元素中选出第k个最小元素.文章采用分治算法解决顺序统计问题,给出了通用算法,并对算法的复杂性进行了分析和讨论.对于子序列长度大于5的情形,该算法的最坏情形的时间复杂性为O(n).     

并行递归筛选选择算法

本文提出了一个基于动态分治和递归筛选方法求解选择问题的并行算法,描述了其在无存取冲突SIMD-SMC机器上的实现.所给出的算法对于在n台处理器上求解从n个数中选取前m个或第m个最小(或最大)者的问题(m相似文献