一種求解DGA圖中具有長度約束的簡單路徑問題算法

何建軍

摘要：具有長度約束的簡單路徑問題具有較高的應(yīng)用價值。在一般圖中，它是一個NP完全問題，除非NP=P，否則沒有多項式時間算法。而對于一些特殊的圖，如有向無環(huán)圖，可以找到多項式時間算法。因此對有向無環(huán)圖中具有長度約束的簡單路徑問題進行研究。首先根據(jù)有向無環(huán)圖的特點，建立遞歸方程，然后根據(jù)遞歸方程給出一個在有向無環(huán)圖中求解具有長度約束的簡單路徑問題算法，同時給出一個有向無環(huán)圖中具有長度約束的簡單路徑構(gòu)造算法。為證明算法正確性，進行相應(yīng)實例驗證，把求解該問題的時間復(fù)雜度由O（NxTxL）改進為O（（N+|E|）L），空間復(fù)雜度改進為O（[EI+N）。

關(guān)鍵詞：有向無環(huán)圖;簡單路徑;長度約束

DOI：10.11907/rjdk.182897開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：中圖分類號：TP312文獻標(biāo)識碼：A 文章編號：1672-7800（2019）010-0082-04

0引言

在圖論中，k-path問題指在給定的圖中找出一條長度為k的簡單路徑，是最長路徑問題和最短路徑問題的一種特殊情況。k-path問題在生物信息學(xué)、交通運輸、數(shù)據(jù)挖掘和模式匹配等領(lǐng)域有重要的應(yīng)用價值。具有長度約束的簡單路徑（Simple Paths with Length Constraint，SPLC）問題是k-path問題的推廣，在一般圖中求解SPLC問題是一個NP完全問題，求解難度很大，除非NP=P，否則沒有多項式時間算法。但對一些特殊圖，比如有向無環(huán)圖、樹，則存在多項時間算法。

有向無環(huán)圖具有長度約束的簡單路徑問題（SPLCin DAGs），在序列模式挖掘、模式匹配、圖的可達查詢、多星成像等方面應(yīng)用廣泛。文獻[16]把有向無環(huán)圖中具有長度約束的簡單路徑問題應(yīng)用于圖的k步可達查詢中。文獻[18]把有向無環(huán)圖中具有長度約束的簡單路徑問題應(yīng)用于多星成像的圈調(diào)度中。Zhang提出了具有周期間隙約束的序列模式挖掘問題，并將該模式挖掘方法應(yīng)用在DNA序列挖掘中;Tanbeer等將具有周期間隙約束的序列模式挖掘方法應(yīng)用于購買模式的挖掘。盡管Zhang等采用空間變換的方法進行序列模式挖掘，但是該方法的基礎(chǔ)是具有間隙約束的模式匹配問題。文獻[21]研究了具有間隙約束和一次性條件模式匹配問題的求解方法，給出了將具有間隙約束的模式匹配問題轉(zhuǎn)換為有向無環(huán)圖的算法，使具有間隙約束的模式匹配問題與SPLC in DAGs問題建立了實質(zhì)性聯(lián)系。文獻[22]把有向無環(huán)圖中具有長度約束的簡單路徑問題應(yīng)用于產(chǎn)品族零部件關(guān)系網(wǎng)絡(luò)，并提出時間復(fù)雜度為O（N⁴）的算法。

有向無環(huán)圖有很多特殊的性質(zhì)，使一些在其它圖上沒有多項式時間算法的問題（除非NP=P），出現(xiàn)在有向無環(huán)圖上。比如最長路徑問題，在有向無環(huán)圖中，可以用拓?fù)渑判虻姆绞角蠼狻Ｎ墨I[8]利用網(wǎng)樹這種特殊的數(shù)據(jù)結(jié)構(gòu)給出在有向無環(huán)圖上求解有長度約束的簡單路徑問題的一個多項式時間算法。本文利用有向無環(huán)圖的有向、無環(huán)特性建立遞歸方程，設(shè)置邊界條件，提出一種更簡潔的動態(tài)規(guī)劃算法。

1問題定義

定義1：圖G=（V，E），其中V稱為頂點集，E稱為邊集。從頂點u到v的路徑是有序定點序列s={u=v₀，v₁，……，v_m=V}，其中定點序列應(yīng)滿足j-1，v_j>∈E（1≤j≤m））如果序列S中任何兩個定點不重復(fù)出現(xiàn)，則稱改路徑為簡單路徑。路徑長度是路徑終邊的數(shù)目。若i，v_j>∈E，則稱v_i為v_j的前驅(qū)，v_j為v_i的后繼。

定義2：具有長度約束的簡單路徑SPLC問題指給定圖G=（V，E）中任意兩點u，v∈V和正整數(shù)m，求解從u到v路徑長度為m的簡單路徑數(shù)目。SPLC in DAGs指在給定的有向無環(huán)圖中求解SPLC問題。

記有向無環(huán)圖G的節(jié)點數(shù)為N，邊數(shù)為|E|，長度約束為L，從v_i到v_j的長度為m的所有有向路徑構(gòu)成的集合S[i，j，m]，從v_i到v_j的長度為m且v_j的前驅(qū)為v_k的所有有向路徑構(gòu)成的集合S[i，k，j，m]。

SPLC in DAGs問題的求解難度在于定點u和v之間的路徑數(shù)有可能呈現(xiàn)指數(shù)形式，如圖1所示，因此不能采用窮舉法列出所有可能的路徑并判定路徑長度是否滿足約束條件進行求解。本文采動態(tài)規(guī)劃法進行求解。

2 動態(tài)規(guī)劃算法

2.1遞推方程建立

有向無環(huán)圖性質(zhì)包括：①若存在從v_i到v_j的有向邊，則從任意一個頂點到v_i的有向路上，一定不會出現(xiàn)v_j，否則會形成一個圈;②若有向無環(huán)圖任意一條有向路中均無重復(fù)的頂點，則為有向路徑;③在集合S[i，k，m-1]和集合S[i，k，j，m]之間存在一一對應(yīng)關(guān)系，即在有向五環(huán)圖G中從v_i到v_k的長度為m-1的所有有向路構(gòu)成的集合，和在有向無環(huán)圖G中從v_i到v_j的長度為m且v_j的直接前驅(qū)為v_k的所有有向路構(gòu)成的集合之間存在一一對應(yīng)關(guān)系，這是因為從S[i，k，m-1]任取一條從v_i到v_k且長度為m-1的有向路p，添加上有向邊k，v_j>后會構(gòu)成一條從v_i到v_j、長度為m且v_j前驅(qū)為v_k的有向路，應(yīng)用該方法從S[i，k，m-1]取得的任意兩條不同的從v_i到v_k、長度為m-1的有向路，得到從v_i到v_j的長度為m且前驅(qū)為v_k的有向路不同。同樣道理從S[i，k，j，m]任取一條從v_i到v_j、長度為m且v_j的直接前驅(qū)為v_k的有向路p′，吧有向邊[v_k，v_j]去掉后悔得到一條從v_i到 v_k、長度為m-1的有向路，而且應(yīng)用該方法從S_{i，k，j，m}取得任意兩條不同的有向路，得到從v_i到v_k、長度為m-1的有向路也不相同。

2.2求解算法QNSPCINDGA

變量說明：A[N][L]是一個二維數(shù)組，S[j][h]存儲的是從結(jié)點v_i到結(jié)點v_j且長度為h的路徑數(shù)目。N是圖G的結(jié)點數(shù)，L是設(shè)定的路徑長度。A[N]是一個數(shù)組的，A[k]是一個集合形變量，其中春初的是以vk為弧頭的所有弧的弧尾結(jié)點。Level記錄當(dāng)前正在計算的路徑長度。

2.3從原點到其他結(jié)點的長路徑構(gòu)造

3算法QNSPCINDGA實例

4算法復(fù)雜性分析與比較

算法QNSPCINDGA初始化時取結(jié)點集的時間為O（N），讀取弧集并初始化數(shù)組A的時間為。O（|E|），初始化M數(shù)組的時間為O（NL）。總共執(zhí)行L次循環(huán)，而每次循環(huán)訪問每個結(jié)點一次，訪問每個結(jié)點時，訪問其每條人弧1次，執(zhí)行循環(huán)時間為O（（N+|E|）L）。所以算法時間復(fù)雜度均為O（（N+|E|）L）。算法QNSPCINDGA空間消耗主要在對圖G的存儲和S數(shù)組上。對圖G的存儲由A數(shù)組完成，而A數(shù)組中的每個元素是一個逆領(lǐng)接鏈表，每條人弧僅存儲一次，且每個結(jié)點僅存儲一次，所以對圖G的存儲空間為O（N+0E0）。數(shù)組S存儲空間為O（NL），算法空間復(fù)雜度為O（|E|+NL）。

算法PA7HSPCINDAG的時間復(fù)雜度和空間復(fù)雜度估計：設(shè)從源點到其它節(jié)點結(jié)點且長度為L的路徑地數(shù)目為W，輸出每條長度為L的路徑耗時最多為O（L），所以總時間復(fù)雜度為O（WL）。算法PATHSPCINDAG僅需要NL的二維數(shù)組S存儲路徑數(shù)目和進行L次遞歸調(diào)用，其遞歸調(diào)用棧深度為L，所以其空間復(fù)雜度為O（NL+L）。

5結(jié)語

本文對有向無環(huán)圖具有長度約束的簡單路徑SPLC問題進行研究，針對有向無環(huán)圖的特點提出了一個動態(tài)規(guī)劃算法，并證明了算法正確性和有效性。該算法簡潔明了，時間復(fù)雜度和空間復(fù)雜度均相對較低，避免了文獻[8]的組合爆炸問題。邊帶權(quán)有向無環(huán)圖中具有長度約束的簡單路徑問題是下一步研究對象。