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

何建軍

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

關鍵詞：有向無環圖;簡單路徑;長度約束

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

0引言

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

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

有向無環圖有很多特殊的性質，使一些在其它圖上沒有多項式時間算法的問題（除非NP=P），出現在有向無環圖上。比如最長路徑問題，在有向無環圖中，可以用拓撲排序的方式求解。文獻[8]利用網樹這種特殊的數據結構給出在有向無環圖上求解有長度約束的簡單路徑問題的一個多項式時間算法。本文利用有向無環圖的有向、無環特性建立遞歸方程，設置邊界條件，提出一種更簡潔的動態規劃算法。

1問題定義

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

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

記有向無環圖G的節點數為N，邊數為|E|，長度約束為L，從v_i到v_j的長度為m的所有有向路徑構成的集合S[i，j，m]，從v_i到v_j的長度為m且v_j的前驅為v_k的所有有向路徑構成的集合S[i，k，j，m]。

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

2 動態規劃算法

2.1遞推方程建立

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

2.2求解算法QNSPCINDGA

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

2.3從原點到其他結點的長路徑構造

3算法QNSPCINDGA實例

4算法復雜性分析與比較

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

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

5結語

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