计算机仿真
計算機倣真
계산궤방진
COMPUTER SIMULATION
2004年
7期
45-47,81
,共4页
无向连通图%最长路%深度优先生成树
無嚮連通圖%最長路%深度優先生成樹
무향련통도%최장로%심도우선생성수
在无向连通图中寻找最长路是一个NP问题,在实际应用中往往以近似最长路来代替最长路,但现存的算法都针对图中任意两点之间的近似最长路.该文利用一条最长路中是不可以被再插入一个新顶点的这个事实,通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法,以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路,而这样的一条路往往非常接近指定的起点与终点之间的最长路.该算法在绣花打版软件的应用中取得了良好的效果.
在無嚮連通圖中尋找最長路是一箇NP問題,在實際應用中往往以近似最長路來代替最長路,但現存的算法都針對圖中任意兩點之間的近似最長路.該文利用一條最長路中是不可以被再插入一箇新頂點的這箇事實,通過對圖的深度優先生成樹的指定起點和終點之間的路徑進行不斷插入的方法,以多項式的算法複雜度求得一條指定起點和終點間不可再被插入頂點的路,而這樣的一條路往往非常接近指定的起點與終點之間的最長路.該算法在繡花打版軟件的應用中取得瞭良好的效果.
재무향련통도중심조최장로시일개NP문제,재실제응용중왕왕이근사최장로래대체최장로,단현존적산법도침대도중임의량점지간적근사최장로.해문이용일조최장로중시불가이피재삽입일개신정점적저개사실,통과대도적심도우선생성수적지정기점화종점지간적로경진행불단삽입적방법,이다항식적산법복잡도구득일조지정기점화종점간불가재피삽입정점적로,이저양적일조로왕왕비상접근지정적기점여종점지간적최장로.해산법재수화타판연건적응용중취득료량호적효과.
