An efficient parallel algorithm for shortest paths in planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.     

An improved genetic algorithm for training layered feedforward neural networks

The new genetic algorithm for training layered feedforward neural networks proposed here uses a mutation operator for performing the search behaviors of local optimization. Combining the random restart method with the local search technique, the algorithm can converge asymptocally, to the optimal solution. Test with a practical example showed that the improved genetic algorthm is more efficient than the conventional genetic algorithm. Project supported by NSFC (No 39870940) and (G199054405-973) the National Key Scientific Research & Development Program.     

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.     

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.     

An efficient method for tracing planar implicit curves

INTRODUCTION Tracing a planar implicit curve f(x, y)=0 on a rectangular region [xl, xr]×[yb, yt] is of great interest in Computer-Aided Design and Computer Graphics. While parametric curves are easy to plot, plotting implicit curves is a challenging problem. Planar im- plicit curve plotting method can be classified into two categories (Shou et al., 2005; Martin et al., 2002; Lopes et al., 2002). In the first category are subdivi- sion methods (Shou et al., 2005; Martin et al., 2002) …     

An efficient enhanced k-means clustering algorithm

INTRODUCTION The huge amount of data collected and stored in databases increases the need for effective analysis methods to use the information contained implicitly there. One of the primary data analysis tasks is cluster analysis, intended to help a user understand the natural grouping or structure in a dataset. Therefore, the development of improved clustering algorithms has received much attention. The goal of a clustering algorithm is to group the objects of a database into a set of m…     

网络最短路问题的最优解邻域

最短路的最优解邻域问题就是在一个网络中找出所有的最优路及满足宽容条件的所有近似最优路从组合优化的观点出发，研究了最短路的最优解邻域及其算法，并进行了算法复杂性分析和实例求解。     

上市公司国有资产流失的路径和特征分析

上市公司国有资产流失的路径主要有上市公司国有资产在沉淀中流失，在权益分配中流失，在转让中流失，在重组发行中流失，在增资配股中流失，在资产置换中流失，在内部人控制下流失，在政府干预中流失，在授权经营中流失，在关联交易中流失。特征：流失载体的特殊性，流失状态的无形性、虚拟性和立体性，流失具具有隐蔽性，流失具有不确定性、复杂性和关联性，流失具有历史性。     

An efficient method for parallel CRC automatic generation

INTRODUCTIONCRC (CyclicRedundancyChecking)codesarewidelyusedintelecommunication ,especiallyintheinternallayersofprotocolssuchasEther net,X2 5,FDDIandATM (AAL5) .Thecom monhardwaresolutionforCRCcalculationisthelinearfeedbackshiftregister (LFSR) ,charac ter…     

An efficient method for parallel CRC automatic generation

The State Transition Equation (STE) based method to automatically generate the parallel CRC circuits for any generator polynomial or required amount of parallelism is presented. The parallel CRC circuit so generated is partially optimized before being fed to synthesis tools and works properly in our LAN transceiver. Compared with the cascading method, the proposed method gives better timing results and significantly reduces the synthesis time, in particular. Project (No. 60271010) supported by the National Natural Science Foundation of China     

An efficient algorithm for mining closed itemsets

This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and efficient pruning of search space. It also employs a hybrid approach that adapts search strategies, representations of projected transaction subsets, and projecting methods to the characteristics of the dataset. Efficient local pruning, global subsumption checking, and fast hashing methods are detailed in this paper. The principle that balances the overheads of search space growth and pruning is also discussed. Extensive experimental evaluations on real world and artificial datasets showed that our algorithm outperforms CHARM by a factor of five and is one to three orders of magnitude more efficient than CLOSET and MAFIA.     

An efficient algorithm for mining closed itemsets

INTRODUCTIONMiningfrequentitemsetsisafundamentalandessentialprobleminmanydataminingapplica tionsincludingthediscoveryofassociationrules,strongrules,correlations,sequentialrules,epi sodes,multi dimensionalpatterns,andmanyoth erimportantdiscoverytasks (AgarwalandSri kant,1994;Wangetal.,2 0 0 2 ) .Mostalgo rithmsproposedsofarworkwellondatasetswherethesizesofitemsetsarerelativelysmall.Howev er,theyusuallycrashwithdensedatasetswheretheitemsetsizesarelarge.Suchdatasetsincludethosecomposedofque…     

Forward and backward models for fault diagnosis based on parallel genetic algorithms

In this paper, a mathematical model consisting of forward and backward models is built on parallel genetic algorithms （PGAs） for fault diagnosis in a transmission power system. A new method to reduce the scale of fault sections is developed in the forward model and the message passing interface （MPI） approach is chosen to parallel the genetic algorithms by global single-population master-slave method （GPGAs）. The proposed approach is applied to a sample system consisting of 28 sections, 84 protective relays and 40 circuit breakers. Simulation results show that the new model based on GPGAs can achieve very fast computation in online applications of large-scale power systems.     

多约束非线性背包问题的一种有效算法

1IntroductionWe consider the following multi-di mensional nonlin-ear knapsack problem(MNKP)maxf(x)=∑nj=1fj(xj)s.t.gi(x)=∑nj=1gij(xj)≤bi,i=1,…,m,x∈X={x|lj≤xj≤uj,xjinteger,j=1,…,n},where allfjand allgijare nondecreasing functions ofxjon[lj,uj]forj=1,…,n,i=1,…,m,andljandujare integer lower and upper bounds forxj,re-spectively,j=1,…,n.It has been proved that0-1linear knapsack problemis NP-hard[1].Nonlinear knapsack problems have numerous appli-cations in various fields,for example,ca…     

一种改进的启发式网格任务调度算法

互联网技术的发展，硬件技术和通信技术的进步 共同加快了计算机领域前进的步伐。20世纪80年代 出现了并行计算，支持同步的算法、程序和体系结构相 继被开发。随后出现了分布计算，它要求各个处理机 之间能够协同计算，通过处理机间的通信共同解决问 题。网格计算技术的发展适     

基于BLAST接收机的空间复用天线选择算法

1IntroductionMultiple-input multiple-output(MIMO)systems canoffer significant capacity gains,compared to single-input single-output(SISO)systems.The extra degreesof freedom offered by multiple antennas can be usedfor increasing bit rates through spatial m…     

Implementation of autofocus in alignment system for layered imprint fabrication

Autofocus method based on the analysis of image content information is investigated to reduce the alignment error resulting from mark positioning uncertainty due to defocus in microstructure layered fabrication process based on multilevel imprint lithography, The applicability of several autofocus functions to the alignment mark images is evaluated concerning their uniformity, sharpness near peak, reliability and measure computation efficiency and the most suitable one based on power spectrum in frequency domain (PSFD) is adopted. To solve the problem of too much computation amount needed in PSFD algorithm, the strategy of interested region detection and effective image reconstruction is proposed and the algorithm efficiency is improved. The test results show that the computation time is reduced from 0.316 s to 0.023 s under the same conditions while the other merits of the function are preserved, which indicates that the modified algorithm can meet the mark image autofocusing require-ments in response time, accuracy and robustness. The alignment error due to defocus which is about 0.5 μm indi-cated by experimental results can be reduced or eliminated by the autofocusing implementation.     

关于简单线性恶化问题的平行机排序的一个全多项式逼近算法

In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.     

一种求解非线性约束优化的单变量边缘分布算法

借鉴罚函数法思想,将建立在Gauss网络的单变量边缘分布算法应用于非线性约束优化问题,提出的新算法突破了传统基于约束保持法或可行规则法的约束处理.且单变量边缘分布是基于搜索空间的宏观层面的进化方法,具备更强的全局搜索能力和更高的收敛率,从而为约束问题的求解提供了一种新的途径.     

导航过程中最短路径的动态调整算法

在导航过程中,当最短路径道路上有拥挤、堵塞或中断的情况发生时,利用Dijkstra最短路径算法中的最短路径长度和前驱结点两个辅助向量数据,可迅速在其邻接结点中选择一条新的最短路径。实现了最短路径的动态调整,从而可以尽快地到达目的地。