共查询到20条相似文献,搜索用时 609 毫秒
1.
Isomorphism identification for epicyclic gear mechanism based on mapping property and ant algorithm 总被引:1,自引:0,他引:1
To achieve computer-aided design for mechanism, one method that can be applied is graph theory. During the process of kinematic
structure enumeration using graph theory, isomorphism identification of graphs is an important and complicated problem. The
problem is known to be NP-complete problem. It is very important to improve the isomorphism identification efficiency and
reliability. The objective of this research work is to use ant algorithm to improve the isomorphism identification efficiency
and reliability for epicyclic gear mechanism. Based on mapping property between graphs, the isomorphism identification problem
can be changed into a matrix operation problem. Two graphs must be isomorphism if the two matrixes of the two graphs can be
exactly by exchanging their certain rows and columns, whereas show the two graphs must be non-isomorphic. A mixed model was
developed for isomorphism identification by integrating the ant algorithm and mapping property between graphs. The gratifying
results can be achieved while parameters are selected in appropriate situation by using the model. Finally, a computer program
has been developed in Visual C++. Some examples confirm the validity of the model. The work will be a reliable isomorphism
identification algorithm for intelligent CAD of epicyclic gear mechanism. 相似文献
2.
Hao Liu Shunyi Shi Ping Yang Jianming Yang 《Journal of Intelligent and Robotic Systems》2018,89(3-4):343-350
During the process of mechanism kinematic structure enumeration, isomorphism identification of graphs is an important and complicated problem. The problem is known to be a NP-complete problem. In this paper, according to the mechanism kinematic chain isomorphism identification criteria, a highly efficient hybrid genetic algorithm model is proposed for isomorphism identification. The model method is coupled with genetic algorithm, optimal choice, and optimal crossover operation. It shows a quick convergence rate of the late operation and can avoid convergence to local optimum. Simulation results show that the hybrid algorithm is more rapid and effective compared with simple genetic algorithm and the improved neural network algorithm. 相似文献
3.
The graph theory is an important method to achieve conceptual design for mechanism. During the process of kinematic structures
enumeration using graph theory, isomorphism identification of graphs is an NP complete problem. It is important to improve
the isomorphism identification efficiency and reliability. To solve the problem, an adaptive hybrid genetic algorithm is presented
by mixing the improved genetic algorithm and local search algorithm. The crossover rate and mutation rate can be designed
as adaptive parameters. Hence, the crossover rate and mutation rate can sustain the variety of the population and adjust the
evolution. In the meantime, the pseudo-crossover operator is introduced to improve the search efficiency. In the last, some
examples are illustrated to show the high efficiency of the algorithm by comparing with the results in other literatures. 相似文献
4.
Gloria Galan-Marin Enrique Merida-Casermeiro Domingo Lopez-Rodriguez 《Neural Processing Letters》2007,26(2):133-143
Detection of isomorphism among kinematic chains is essential in mechanical design, but difficult and computationally expensive.
It has been shown that both traditional methods and previously presented neural networks still have a lot to be desired in
aspects such as simplifying procedure of identification and adapting automatic computation. Therefore, a new algorithm based
on a competitive Hopfield network is developed for automatic computation in the kinematic chain isomorphism problem. The neural
approach provides directly interpretable solutions and does not demand tuning of parameters. We have tested the algorithm
by solving problems reported in the recent mechanical literature. Simulation results show the effectiveness of the network
that rapidly identifies isomorphic kinematic chains. 相似文献
5.
An efficient algorithm for subgraph isomorphism is presented. It combines tree search with relaxation by using resolution. Bitwise parallelism, which is an important factor in speed, is achieved during the resolution process even though a sequential computer is used. The algorithm can be easily modified to apply to multi-relation labeled graphs, attributed graphs and some higher order structures such as arrangements. 相似文献
6.
A (sub)graph isomorphism algorithm for matching large graphs 总被引:8,自引:0,他引:8
Cordella LP Foggia P Sansone C Vento M 《IEEE transactions on pattern analysis and machine intelligence》2004,26(10):1367-1372
We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs. 相似文献
7.
Combinatorial maps explicitly encode orientations of edges around vertices, and have been used in many fields. In this paper, we address the problem of searching for patterns in model maps by putting forward the concept of symbol graph. A symbol graph will be constructed and stored for each model map in the preprocessing. Furthermore, an algorithm for submap isomorphism is presented based on symbol sequence searching in the symbol graphs. The computational complexity of this algorithm is quadratic in the worst case if we neglect the preprocessing step. 相似文献
8.
侯爱民 《计算机工程与应用》2011,47(16):52-57
图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决。受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件:在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性。 相似文献
9.
A new approach to the problem of graph and subgraph isomorphism detection from an input graph to a database of model graphs is proposed in this paper. It is based on a preprocessing step in which the model graphs are used to create a decision tree. At run time, subgraph isomorphisms are detected by means of decision tree traversal. If we neglect the time needed for preprocessing, the computational complexity of the new graph algorithm is only polynomial in the number of input graph vertices. In particular, it is independent of the number of model graphs and the number of edges in any of the graphs. However, the decision tree is of exponential size. Several pruning techniques which aim at reducing the size of the decision tree are presented. A computational complexity analysis of the new method is given and its behavior is studied in a number of practical experiments with randomly generated graphs. 相似文献
10.
A heuristic polynomial algorithm is presented, which is used for the recognition of isomorphism of graphs and can be assigned to the group of methods that use local characteristic invariants of graphs. At each step, the behavior of the algorithm depends on information obtained at its previous steps. All the theorems stated are proved for a class of nonoriented graphs. 相似文献
11.
On the coding of ordered graphs 总被引:1,自引:0,他引:1
Ordered graph and ordered graph isomorphism provide a natural representation of many objects in applications such as computational
geometry, computer vision and pattern recognition. In the present paper we propose a coding procedure for ordered graphs that
improves an earlier one based on Eulerian circuits of graphs in terms of both simplicity and computational efficiency. Using
our coding approach, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time, although
no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today. An experimental evaluation demonstrates
the superior performance of the new method. 相似文献
12.
Lin Chen 《Parallel and Distributed Systems, IEEE Transactions on》1996,7(3):308-319
In this paper, we explore some properties of identification matrices and exhibit some uses of identification matrices in studying the graph isomorphism problem, a famous open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1s property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1s property. Graphs which have identification matrices satisfying the consecutive 1s property include, among others, proper interval graphs and doubly convex bipartite graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms 相似文献
13.
Messmer B.T. Bunke H. 《IEEE transactions on pattern analysis and machine intelligence》1998,20(5):493-504
We propose a new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph. The algorithm is based on a compact representation of the model graphs. This representation is derived from the set of model graphs in an off-line preprocessing step. The main advantage of the proposed representation is that common subgraphs of different model graphs are represented only once. Therefore, at run time, given an unknown input graph, the computational effort of matching the common subgraphs for each model graph onto the input graph is done only once. Consequently, the new algorithm is only sublinearly dependent on the number of model graphs. Furthermore, the new algorithm can be combined with a future cost estimation method that greatly improves its run-time performance 相似文献
14.
15.
16.
17.
18.
The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism
problem can be solved by efficient parallel algorithms, it is in the class AC
1. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to UL∩coUL. As a consequence of our method we get that the isomorphism problem for oriented graphs is in NL. We also show that the problems are hard for L. 相似文献
19.
本文将用于求解组合优化问题的模拟退火法引入聚类分析、属性关系图同态、分段曲线拟
合和特征选择等模式识别问题.(1)提出了一类新的聚类分析算法--模拟退火聚类法;
(2)给出了一种模拟退火图同态的方案和实现算法--ALISOM;(3)详细地讨论了如何应
用模拟退火组合优化法进行分段曲线拟合和特征选择. 相似文献
20.
无向图同构判定的并行算法 总被引:2,自引:0,他引:2
提出了一种判别无向图同构的方法,该方法根据无向图的邻接矩阵的特征值来判别出图的同构关系,而不需要其它附加信息。同时给出用Jacobi方法求出无向图的邻接矩阵的特征值的一种并行算法,它可以在分布式存储的多处理的多处理机上实现。实验结果表明,此方法是快速有效的,能在较短的运算时间内给出判断结果。 相似文献