运用有向联接件知识求解装配序列规划

在分析联接件特征的基础上，提出了有向联接件的概念，建立基于联接件知识的零件表达式；运用有向联接件知识求解装配序列规划，实现了知识推理算法和几何约束推理算法的有机结合，有效地降低了装配规划的计算复杂度，保证规划所得装配序列的合理性和实用性．此外，还建立了装配体的自由空间图，可以解决非单调装配序列规划问题。     

曲线形套装路径规划算法研究

曲线形套装是一类非常复杂的产品装配过程,零件装配除了要顺着被套装零件曲线形移动还要配合调整自身的方位角才能到达目标,其路径规划问题难以沿用现有的装配路径规划方法。论文通过分析这类曲线形套装时的装配特征,在总结传统A搜索算法基础上,提出了一种能够自调整方位角的装配路径规划算法。在节点扩展中扩展位置和角度偏移量,并对传统A搜索算法加以改进,避免被套装零件局部凸凹变化引起搜索停滞不前和算法假失败情况。     

灰度图像矩的一种快速算法

大多数矩的快速算法仅适用于二值图像。本文给出了一种适用于灰度图像的矩快速算法。对N×N大小的灰度图像 ,引入 6个大小为N的数组 ,将求矩过程中重复计算的量一次计算后存入数组 ,减少了重复和冗余计算。虽然增加了 6个数组 ,内存的相对增加仅为 6/N。该算法原理简单 ,求矩结果精确 ,计算量大大减少。和直接法相比 ,加法和乘法运算次数仅为其 40 4%和2 2 6%。和Yang s算法相比 ,加法次数相同 ,而乘法次数约为其 67 6%。     

自动生产线中零件方位参数改变量的计算

在自动生产线装配时，由零件初始方位和终止方位，求解其变换矩阵，及由变换矩阵再求对零件所需进行的放置量和平移量，在规划自动线及零件的运用时是常见的基本问题，本文对此作了全面透彻的分析，并提出了简洁，高效的计算方法。     

快速霍夫变换算法

二值图像的直线检测过程中,标准霍夫变换算法的计算量为O（N^3)。该文提出一种快速霍夫变换算法,其计算量仅为O（N^2log2N)。该快速算法可以并行实现;处理器阵列规模为O（N^2)时,计算量为O（log2N)。文中还分析得到快速算法的误差上界,并提出一种改进的快速霍夫变换算法以获得更高的计算精度。最后,给出算法的数值算例。理论分析及数值算例都表明,该文的快速霍夫变换算法在直线检测过程中有着更高的计算效率,并且具有良好的计算精度。     

一种新的凸多边形不干涉算法

求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O（n+m）。     

树结构在N体问题中的应用*

N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2).采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分.Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法.BHA可快速计算各点受到的场力,计算复杂度为O(N log N),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度.数值结果表明,树结构的并行效果也很好.     

基于成本和并行装配的装配序列有向图求解

针对虚拟装配中装配序列规划问题,引入了有向图来描述装配过程中的零件以及零件间的装配约束关系。结合装配成本、并行装配、装配经验优化了装配关系有向图的拓扑排序算法。提出了将装配方向变化次数作为衡量装配成本的一项重要指标。提出了将单次可装配的零件数量作为装配优先方向的参考依据。文章最后给出了装配序列生成的具体算法。     

基于规则和爆炸图的装配序列规划

提出局部爆炸图的概念，运用几何干涉规则生成各直角坐标方向的局部爆炸图；在确立各方向的合并顺序后，用合并规则生成各零件的合并约束前元集；并据此进行局部爆炸图合并求解装配序列，实现了规则推理和几何推理算法的紧密结合，有效地避免了装配序列组合爆炸，降低了装配规划的计算复杂度，保证规划所得装配序列的可行性和实用性．     

时频分布算法的并行实现

二次时频分布(TFD)是一种常用的非平稳信号分析方法,以最常用的Wigner-Ville分布(WVD)为例,分析了离散时频分布算法实现,针对该算法的复杂性和计算量大的特点,实现了离散信号时频分布的并行算法,通过采用缓冲池和计算结果的压缩传输,同时减小了并行计算中传输数据总量和传输次数,将通信开销从O(N2)降低到O(N),解决了并行时频分布计算中数据传输“瓶颈”问题。     

An interactive approach of assembly planning

An interactive approach to assembly planning is presented. It provides a virtual reality interface for production engineers to program the virtual representation of robotic manipulators in a three-dimensional (3D) operation space. The direct human involvement creates a user-defined assembly sequence, which contains the human knowledge of mechanical assembly. By extracting the precedence relationship of machinery parts, for the first time it becomes possible to generate alternative assembly sequences automatically from a single sequence for robot reprogramming. This interactive approach introduces human expertise into assembly planning, thus breaking down the computational complexity of autonomous systems. Experiments and analysis provide strong evidence to support the incontestable advantages of "manufacturing in the computer".     

On the implementation of frontier-to-root tree automata inrecursive neural networks

We explore the node complexity of recursive neural network implementations of frontier-to-root tree automata (FRA). Specifically, we show that an FRAO (Mealy version) with m states, l input-output labels, and maximum rank N can be implemented by a recursive neural network with O( radical(log l+log m)lm(N)/log l+N log m) units and four computational layers, i.e., without counting the input layer. A lower bound is derived which is tight when no restrictions are placed on the number of layers. Moreover, we present a construction with three computational layers having node complexity of O((log l+log m) radicallm (N)) and O((log l+log m)lm(N)) connections. A construction with two computational layers is given that implements any given FRAO with a node complexity of O(lm(N)) and O((log l+log m)lm(N)) connections. As a corollary we also get a new upper bound for the implementation of finite-state automata into recurrent neural networks with three computational layers.     

Outliers, inliers and the generalized least trinuned squares estimator in system identification

The least trimmed squares estimator (LTS) is a well known robust estimator in terms of protecting the estimate from the outliers. Its high computational complexity is however a problem in practice. We show that the LTS estimate can be obtained by a simple algorithm with the complexity O( N In N) for large N, where N is the number of measurements. We also show that though the LTS is robust in terms of the outliers, it is sensitive to the inliers. The concept of the inliers is introduced. Moreover, the Generalized Least Trimmed Squares estimator (GLTS) together with its solution are presented that reduces the effect of both the outliers and the inliers.     

A complexity model for sequence planning in mixed-model assembly lines

Sequence planning is an important problem in assembly line design. It is to determine the order of assembly tasks to be performed sequentially. Significant research has been done to find good sequences based on various criteria, such as process time, investment cost, and product quality. This paper discusses the selection of optimal sequences based on complexity induced by product variety in mixed-model assembly line. The complexity was defined as operator choice complexity, which indirectly measures the human performance in making choices, such as selecting parts, tools, fixtures, and assembly procedures in a multi-product, multi-stage, manual assembly environment. The complexity measure and its model for assembly lines have been developed in an earlier paper by the authors. According to the complexity models developed, assembly sequence determines the directions in which complexity flows. Thus proper assembly sequence planning can reduce complexity. However, due to the difficulty of handling the directions of complexity flows in optimization, a transformed network flow model is formulated and solved based on dynamic programming. Methodologies developed in this paper extend the previous work on modeling complexity, and provide solution strategies for assembly sequence planning to minimize complexity.     

Towards a theory of local and global in computation

We formulate the rudiments of a method for assessing the difficulty of dividing a computational problem into “independent simpler parts”. This work illustrates measures of complexity which attempt to capture the distinction between “local” and “global” computational problems. One such measure is the covering multiplicity, or average number of partial computations which take account of a given piece of data. Another measure reflects the intuitive notion of a “highly interconnected” computational problem, for which subsets of the data cannot be processed “in isolation”. These ideas are applied in the setting of computational geometry to show that the connectivity predicate has unbounded covering multiplicity and is highly interconnected; and in the setting of numerical computations to measure the complexity of evaluating polynomials and solving systems of linear equations.     

CuMen：基于最大频繁序列模式的聚类算法及其在基因拼接中的应用

基因组序列拼接的主流方法是将整条序列随机打断成小片段,然后根据片段间重叠关系连接成长序列.由于较多噪音存在,算法复杂度高,加之生物数据的海量增长,序列拼接处理导致巨大的时空开销而无法完成.本文提出一种基于最大频繁序列模式的聚类算法,将整个数据集分成若干个子集,分别高效地处理,实现了一个基因拼接网格系统、透明动态的资源管理,大大扩展了基因拼接计算能力.基于最大频繁序列模式聚类算法及挖掘算法,针对生物数据的特性做出了优化.     

PAIDD: a hybrid P2P-based architecture for improving data distribution in social networks

Rapid growth in social networks(SNs)presents a unique scalability challenge for SN operators because of the massive amounts of data distribution among large number of concurrent online users.A request from any user may trigger hundreds of server activities to generate a customized page and which has already become a huge burden.Based on the theoretical model and analytical study considering realistic network scenarios,this article proposes a hybrid P2P-based architecture called PAIDD.PAIDD fulfills effective data distribution primarily through P2P connectivity and social graph among users but with the help of central servers.To increase system efficiency,PAIDD performs optimized content prefetching based on social interactions among users.PAIDD chooses interaction as the criteria because user’s interaction graph is measured to be much smaller than the social graph.Our experiments confirm that PAIDD ensures satisfactory user experience without incurring extensive overhead on clients’network.More importantly,PAIDD can effectively achieve one order of magnitude of load reduction at central servers.     

F[x]-lattice basis reduction algorithm and multisequence synthesis

By means of F[x]-lattice basis reduction algorithm, a new algorithm is presented for synthesizing minimum length linear feedback shift registers (or minimal polynomials) for the given mul-tiple sequences over a field F. Its computational complexity is O(N2) operations in F where N is the length of each sequence. A necessary and sufficient condition for the uniqueness of minimal polynomi-als is given. The set and exact number of all minimal polynomials are also described when F is a finite field.     

Computing the graph-based parallel complexity of gene assembly

We consider a graph-theoretical formalization of the process of gene assembly in ciliates introduced in Ehrenfeucht et al. (2003) [3], where a gene is modeled as a signed graph. The gene assembly, based on three types of operations only, is then modeled as a graph reduction process (to the empty graph). Motivated by the robustness of the gene assembly process, the notions of parallel reduction and parallel complexity of signed graphs have been considered in Harju et al. (2006) [7]. We describe in this paper an exact algorithm for computing the parallel complexity of a given signed graph and for finding an optimal parallel reduction for it. Checking the parallel applicability of a given set of operations and scanning all possible selections amount to a high computational complexity. We also briefly discuss a faster approximate algorithm that however, cannot guarantee finding the optimal reduction.     

Network partition methods for use in symbolic analysis by interpolation

Symbolic analysis of networks of high order and complexity is not a straightforward process. The problems encountered are usually enormous demands for computer storage and time together with inaccurate results. A number of methods are presented which can drastically reduce the computer requirements and in some cases keep the computational error to a minimum. The principle of the methods is to partition the networks into a number of parts, and techniques of division and recombination are developed.