∑树结构与更新最小生成树的并行算法

更新最小生成树问题,即已知图的最小生成树,当图的某条边的赋值被改变,如何快速有效的求新出的最小生成树.本文引进了∑-树结构,并以此获得了一个快速有效的更新最小生成树的并行算法,并行时间为O(logn),处理器个数为O(n~(4/(?)),计算模型为CREW-PRAM.其中n 为图的顶点个数,而且,进行预处理所需的时问也只需O(log~2n),处理器个数为O(n~(?)),存贮数据所需的空间为O(n~(?)).     

一个最优并行选择算法

最优并行算法系指其所用时间与处理器数目之乘积等于相应串行算法之时间下界的那一类并行算法。对于求解从n个数中选取前m个或第m个最小(或最大)数的选择问题(m相似文献   

基于超立方体Q_n节点编码的最小生成树算法

利用超立方体Q_n的同构拓扑结构,基于其节点编码特征,依据广度优先的策略,找到了一种新的寻找最小生成树的算法.文中提出的算法总共包括了十个步骤,完成一次循环,算法频度为f(n)=2~n-1+n~3+n~2+2n,因此算法的时间复杂度为O(2~n).这一算法为寻找超立方体Q_n中的最小生成树提供了新的思路,为Q_n中设计相应路由算法提供了有力的理论支撑.     

超立方体中过k个指定点的最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(kn)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n~2+2n(n~2+2)次运算,算法的时间复杂度为O(n~3),属于多项式计算.     

有限群上几个问题的算法及复杂度分析

本文讨论有限群上几个计算问题。我们设了一个O(n~2)时间的算法去查找n阶Abel群的基底(把n阶Abel群分解为循环P群的直积)。给出了复杂度为O(n~2log_2n)的n阶Abel群的检验算法。证明了n阶Abel群的同构检验可在O(nlOg_2n)时间内完成。最后,我们讨论定义在有限群上的旅行售货员问题:证明了该问题是NP完全的,并给出了一个O(m·n~2·2~n)时间的算法求解它。     

一类树问题的快速并行算法

本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.     

多处理器上（m,n）选择问题的一个并行算法

给出求解从任意给定的n个数据中选取m个最小(最大)者即(m,n)选择问题的一个并行算法(m相似文献   

基于AOV和广义表的梯形图转指令表的转换算法

梯形图是IEC 61131-3标准定义的4种可编程逻辑控制器(programmable logic controller, PLC)编程语言之一,但因为梯形图无法被处理器直接执行,所以大多数商用PLC编程系统都会将梯形图转换为类似汇编语言的指令表,便于生成机器指令。该文提出一种基于AOV(activity on vertex)图和广义表的转换算法,相比基于广义表的现有算法,重点解决了多线圈输出问题。此外,该文提出了遍历带有输出标志位的广义表的深度优先搜索算法,以生成对应的指令表。算法时间复杂度最佳情况为O(n),最差为O(n~2)。     

树的m—路中心

提出了m—路中心的概念。对无权树和赋权树分别给出了O(n log n),O(n~2)及O(n log (d(T)/Wminee(T)))算法,其中Wminee(T)是赋权树的最小权数。     

无线传感器网络增配节点实现双连通并优化中继路径

对所有节点有统一通信功率和传输半径的无线传感器网络,用平面无向图建模。提出一个基于广度优先的O(n~3)多项式时间搜索算法来发现无线传感器网络中的双连通分量,继而确定网络中所有关节点,然后提出一个最坏情况有O(n~2log(n/3))多项式计算时间的贪心算法来增加尽量少的节点以实现网络双连通,同时,增配节点形成的新路径有助于减少部分节点到汇聚节点的中继跳数。实验结果也验证了以上算法的效果。     

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（（ｎ＋ｍ）／ｌｏｇｎ）处理器的最佳、高速并行算法     

求解一类T型线性方程组的快速算法

本文首先给出一个求解一类T型线性方程组的快速串行算法,它的复杂性是O(nlogn),比目前最好的O(n~2)算法复杂性要低。接着又指出了它的并行计算方案,在n台处理机的条件下,计算步数不超过O(logn),速度倍数是O(n),效率是O(1)。     

PRAM模型模拟RMESH模型的2种方案

给出用PRAM模拟RMESH的2种方案：用n个处理器的PRAM-CRCW模型模拟 sqrt(n)×sqrt(n) 个处理器的RMESH模型的时间复杂度为O(nlogn),用n²个处理器的PRAM-CRCW模型模拟 sqrt(n)×sqrt(n) 个处理器的RMESH模型的时间复杂度为O(logn),同时也给出了PRAM-CREW和PRAM-EREW模型模拟的时间复杂度。     

受限SIMD PRAM模型上的高效并行图算法

在限定处理机个数的 CREW PRAM并行计算模型上,给出了图论中一些基本问题的并行算法.所给并行算法的费用c(n)=p(n)*t(n)是目前已知的最好结果,其中p(n),t(n)分别是对一具有n个顶点图实施并行算法所用处理机的个数和最坏情况下的时间复杂性。     

基于散列技术的快速子串归并算法

用统计方法研究东西方语言的多词单元问题和东方语言的未登录词问题时需要删除同频子串(子串归并)．传统的子串归并算法时间复杂度为O(n^2),在大规模语料库的处理中效率低下．提出一种基于散列技术的时间复杂度为O(n^2)的子串归并算法,并用数学方法证明其与O(n^2)复杂度的算法等价,即输入相同时输出也相同．不同规模语料上的实验结果表明新算法能够大大缩短子串归并所需时间,适用于大规模语料库的处理．     

区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法.利用这两种方法,对最小团覆盖、最大团、最大独立集、最小支配集、Hamiltonian 回路、最佳道路覆盖、最小带宽和Steiner 树的计算问题, 在EREW PRAM 模型上给出O(logn) 时间,使用O(n) 处理器的高效并行算法.     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

优先队列与并行分枝界限算法

讨论了分枝界 使用的优先队列结构,针对分枝 界限算法的选择规则和淘汰规则,提出了立体堆,双层立体堆,串队列三种新的结构;给出了各结构上相应的基本算法及复杂度分析,在此基础上给出了一类ＰＲＡＭ－ＣＲＥＷ模型上基于双层立体堆的并行分枝界限算法,其运行时间为Ｏ（（ｒ／ｌｏｇｒ）ｈｌｏｇｈ＋ｒｈ）,其中ｒ为可用处理器ｈ为找到最优解时的迭代次数。     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).