Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

Sub-optimal solutions to track detection problem using graph theoretic concepts

This paper demonstrates how the problem of tracking targets, which appear as either straight or curved lines in two-dimensional display images (or data images) can be formulated in terms of a directed weighted graph model and how dynamic programming techniques can be efficiently applied to reach an optimal or sub-optimal solution. In general, track detection algorithms providing optimal solutions have good detective ability, but most of them suffer from the inability to detect discontinuous lines or to resolve efficiently pairs of crossing lines. A sub-optimal solution is provided that efficiently overcomes these weaknesses. We focus on modeling the track detection problem in terms of a graph, formulating fast sequential/parallel sub-optimal track detection algorithms and testing them on simulated data in order to show their detective ability. Moreover, we specify the conditions under which sub-optimal algorithms can perform at least as well as their corresponding optimal algorithms. This is significant for the track detection problem where fast, accurate and real-time detection is considered a necessity.     

Recommending suitable learning scenarios according to learners’ preferences: An improved swarm based approach

The paper presents a new approach for recommending suitable learning paths for different learners groups. Selection of the learning path is considered as recommendations to choosing and combining the sequences of learning objects (LOs) according to learners’ preferences. Learning path can be selected by applying artificial intelligence techniques, e.g. a swarm intelligence model. If we modify and/or change some LOs in the learning path, we should rearrange the alignment of new and old LOs and reallocate pheromones to achieve effective learning recommendations. To solve this problem, a new method based on the ant colony optimisation algorithm and adaptation of the solution to the changing optimum is proposed. A simulation process with a dynamic change of learning paths when new LOs are inserted was chosen to verify the method proposed. The paper contributes with the following new developments: (1) an approach of dynamic learning paths selection based on swarm intelligence, and (2) a modified ant colony optimisation algorithm for learning paths selection. The elaborated approach effectively assist learners by helping them to reach most suitable LOs according to their preferences, and tutors – by helping them to monitor, refine, and improve e-learning modules and courses according to the learners’ behaviour.     

Tool path generation framework for accurate manufacture of complex 3D sheet metal parts using single point incremental forming

The prototyping of complex sheet metal parts using single point incremental forming (SPIF) requires the generation of optimal tool paths and/or tool path sequences that ensure that the formed part is within geometric design specifications. The presence of a multitude of features on complex parts leads to multiple inaccuracy inducing phenomena occurring simultaneously due to interactions between the features. This paper proposes a network analysis methodology using topological conceptual graphs to capture the effects of different phenomena on the final accuracy of a sheet metal part manufactured by SPIF. Using this framework optimized tool paths can be generated that compensate for the inaccuracy inducing behavior. Tool path generation algorithms to create partial tool paths that account for the accuracy of specific features in the part based on the proposed framework are also presented. Finally, the creation of integrated tool paths maintaining complementarity between tool paths and desired continuity behavior using non-uniform cubic B-splines is illustrated. A number of case studies demonstrating the applicability of the integrated framework are discussed, where the maximum deviations in the part are significantly reduced and the average absolute deviations for the complete part are brought down to less than 0.5 mm.     

基于AR规则的全路径测试数据自动生成方法

基于全路径的研究现正处于起步阶段,提出了一种全新的NRPS算法（不重复路径搜索算法）和AR规则来对程序的源文件进行静态分析,生成有向无负权图,进而得到不重复路径集;并结合粒子群优化算法最终生成最优测试用例。实验表明,该方法具有可行性。     

Profiling selected paths with loops

Path profiling records the frequency of each path in an executed program.To accomplish profiling,probes are instrumented in the program and executed as the program runs.So,the number of probes has a significant impact on the efficiency of a profiling technique.By profiling only the interesting paths,existing techniques try to improve the profiling efficiency by reducing the number of probes and optimize path encodings for efficient storage.However,they lack accuracy,waste time on running uninteresting paths,and can mainly deal with acyclic paths.In this article,a novel technique called Profiling Selected Paths(PSP)is introduced to profile selected paths,which enables custom selection for both acyclic and cyclic paths and increases the execution efficiency by early termination on uninteresting paths.Theoretical analysis and experimental evaluation indicate that PSP performs better than existing techniques.     

基于子结构的内力约束连续体拓扑优化

通过拓扑优化可以得到传力路径,不同传力路径对应不同内力载荷。如果将内力载荷作为目标或约束进行拓扑优化,可以得到满足不同需求的传力路径,为拓扑优化的发展提供新思路和新方法。为了得到不同内力载荷需求的传力路径,基于子结构法将结构分开使内力暴露出来。以结构质量最小为目标,以内力为约束建立拓扑优化模型,基于独立、连续、映射( independent, continuous, mapping, ICM)方法和单位载荷法将内力显式化,通过累加获得需要控制的传力路径上的内力,通过迭代调整2个路径上的内力使其比值达到一个稳定的值,从而获得满足内力约束的传力路径。算例表明：不同的内力约束可以得到不同的传力路径。     

面向矿井突水避险的双向搜索多最优路径算法

为节省煤矿水灾状况下的逃生时间,提高应急救援效率,在传统的Dijkstra算法基础上提出一种基于双向搜索的K则最短路径算法.首先综合考虑煤矿特殊巷道分布,提出井巷长度当量权值,然后利用灰色理论模型预测特定时间段内每条巷道的人流量,进而根据人流量对行走速度的影响关系式得到每条巷道的通行时间值,最终通过双方搜索策略改进算法,实现事故点到逃生井口的多条最佳逃生路线.根据井下巷道拓扑结构提取构建一个无向带权网络图,在MATLAB环境下利用上述优化算法进行仿真验证.结果显示,该改进算法具有更好的准确率和实用性.     

空心双拐曲轴内高压成形数值模拟

应用动态显式有限元法对空心双拐曲轴的内高压成形过程进行了模拟分析,研究了加载路径对内高压成形的影响,指出了在加载曲线中存在着最佳成形区间,成形压力小于20MPa时,管坯产生起皱,成形压力大于32MPa时,管坯发生开裂,只有合理的应用加载路径,成形压力介于20MPa与30MPa之间,使轴向进给量可以正好补偿径向的变形量才能获得壁厚较为均匀的合格零件。     

板料成形极限理论与实验研究进展

成形极限是板材成形领域中重要的性能指标和工艺参数。文章在阐述成形极限在板料成形中的意义的基础上,综述并分析了成形极限在理论和实验方面的研究进展。成形极限图受应变路径的影响,给工业生产应用带来极大不便。以极限应力构成的成形极限应力图不受应变路径的影响,作为复杂加载路径的成形极限判据更加方便和实用。FLSD研究与FLD相结合,成为精确地确定破裂判别准则的主要途径之一,是近来研究的热点。十字形双向拉伸是实现复杂加载路径有效实用的试验方法。最后对成形极限应力图和十字形双向拉伸试验需要解决的关键问题作了阐述。