无向连通图中求约束条件下近似最长路算法  

An Approximation Algorithm for Finding the Longest Path in Undirected Connected Graph under Constrains

作　　者：孙承山[1] 何援军[1] 蔡鸿明[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《计算机仿真》2004年第7期45-47,81,共4页Computer Simulation

基　　金：总后科研项目资助(41A1C51)

摘　　要：在无向连通图中寻找最长路是一个NP问题,在实际应用中往往以近似最长路来代替最长路,但现存的算法都针对图中任意两点之间的近似最长路。该文利用一条最长路中是不可以被再插入一个新顶点的这个事实,通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法,以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路,而这样的一条路往往非常接近指定的起点与终点之间的最长路。该算法在绣花打版软件的应用中取得了良好的效果。It is a NP-hard problem to find the longest path in an undirected connected graph, so people intend to find some approximation algorithms in practice, but all the existing algorithms are for a approximate longest path between two random vertexes in the graph. Based on that a longest path can not be inserted into a new vertex, we can insert all the nodes possible into the path between certain two vertexes in the DFSTraverseTree of the graph to get a path that cann't be inserted into again in a polynomial-time, usually this path will be a very good approximate longest path between two certain vertexes. The algorithm was used in the embroidery software, and the result shows that the algorithm can work well in practice.

关 键 词：无向连通图 约束条件 近似最长路算法 深度优先生成树 算法应用 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]