黃檢寶,彭詩怡,郭煜銳
(南華大學(xué),衡陽421001)
國家發(fā)改委在2017 年1 月19 日,引發(fā)了《十三五規(guī)劃》,我國管道運輸?shù)目偫锍淘隽渴志薮骩1],在互聯(lián)網(wǎng)大數(shù)據(jù)時代背景下,如何用智能算法監(jiān)控管道運輸顯得尤為重要。最近公共祖先算法是圖論的經(jīng)典算法,它能夠快速地找出樹中兩點的最近公共祖先[2-3],相對于樸素的暴力搜索算法,其有較低的時間復(fù)雜度,本文通過最近公共祖先算法實現(xiàn)了快速監(jiān)控管道網(wǎng)絡(luò)中的最大流量,保障了管道運輸?shù)陌踩?/p>
對于有根樹T,結(jié)點u 和v 的最近公共祖先為LCA(u,v) ,LCA(u,v) 滿足為u和v的深度最大的父結(jié)點。例如,存在樹T0,其點集為V{1,2,3,4,5,6},邊集為E{(1,2),(1,3),(2,4),(2,5),(5,6)} ,令根結(jié)點為1,如圖1 所示,結(jié)點4 和結(jié)點6 的公共祖先有結(jié)點1 和結(jié)點2,由于結(jié)點2 的深度比結(jié)點1 的深度大,所以結(jié)點2 是結(jié)點4 和結(jié)點6 的最近公共祖先。
圖1 示例圖(一)
最近公共祖先問題的算法,主要包括歐拉序結(jié)合ST 表法、倍增法[3]、并查集[2-3]結(jié)合Tarjan 算法[4]和樹鏈剖分法[2]。其中包括離線算法和在線算法,離線算法需要提前知道所有要求LCA 的點對{(ui),vi,…},再一次性處理,得到所有的點對的公共祖先;而在線算法可以合理的根據(jù)需求,每輸入一對u 和v,即可求出他們的LCA。這四種算法中,除了并查集結(jié)合Tarjan 算法為離線算法,其他都是在線算法。歐拉序結(jié)合ST 表法的核心思想是首先通過深度優(yōu)先搜索得到有根樹的歐拉序,然后通過ST 表不斷查詢兩點的LCA;倍增法的核心思想是,將兩點同時往根節(jié)點跳躍2 的指數(shù)倍,當(dāng)深度差相等時,即可得到兩點的LCA;并查集結(jié)合Tarjan算法的核心思想為,在深度優(yōu)先搜索返回的過程中,不斷的用并查集合并搜索到的點,LCA 為并查集根節(jié)點。樹鏈剖分的核心思想為,將樹劃分為輕重鏈,然后用線段樹或者樹狀數(shù)組來維護(hù)每一條鏈,LCA 即為數(shù)據(jù)結(jié)構(gòu)查詢得到的結(jié)果。
最近公共祖先問題,包括四大算法,有線算法更具有實際應(yīng)用價值,下面對歐拉序和ST 表法求LCA 進(jìn)行詳細(xì)介紹。
歐拉序是對圖搜索過程中,記錄搜索路徑中遍歷的結(jié)點,每次經(jīng)過的點都需要記錄。與dfs 序不同的是,dfs 序類似于前序遍歷,只是將第一次遍歷的點按順序記錄下來。以圖1 為例,歐拉序為:{1,2,4,2,5,6,5,2,1,3,1},dfs 序為:{1,2,4,5,6,3}。
ST 表是一種能實現(xiàn)快速查找區(qū)間最大值或者最小值的數(shù)據(jù)結(jié)構(gòu),它通過二的冪次方來劃分區(qū)間,不斷的利用上一個小區(qū)間,合并求出當(dāng)前大區(qū)間的最大值或者最小值,而查詢時只需要將查詢的區(qū)間劃分為盡可能大的二次冪區(qū)間,重疊覆蓋取其最大值或最小值即可得到結(jié)果。
將這兩個算法結(jié)合,首先遍歷樹得到歐拉序,然后在歐拉序中使用ST 表快速查找LCA,例如,在圖1 中,求結(jié)點4 和結(jié)點6 的最近公共祖先,在歐拉序中找到結(jié)點4 和結(jié)點6 第一次出現(xiàn)的位置,即第3 個和第6個,對應(yīng)的序列為{4,2,5,6},再利用ST 表查詢第3 個位置和第6 個位置之間的最小值,即LCA 為{4,2,5,6}的最小值,結(jié)果是結(jié)點2。
A 國建立了一個龐大的石油管道運輸網(wǎng)絡(luò),如何才能快速的監(jiān)控管道網(wǎng)絡(luò)的流量,來保障石油運輸過程中的安全性呢?A 國有N 個城市,為了節(jié)省管道的材料費,A 國只布置了N-1 條石油運輸管道,即剛好能保證兩兩城市之間能互通,沒有城市是孤立狀態(tài)。現(xiàn)在A 國管道運輸管理者經(jīng)常需要增加某兩個城市之間的石油流量,假設(shè)每增加1 單位流量,兩城市之間的管道也會增加1 單位壓力,經(jīng)過多次操作后,A 國整個管道網(wǎng)絡(luò)最大的壓力是多少?
算法的輸入格式為:第一行輸入整型N,代表A 國城市的數(shù)量,之后輸入N-1 行整型ai和bi之,代表城市ai和城市bi之間有一條管道連通,再輸入整型k 代表需要對管道網(wǎng)絡(luò)進(jìn)行k 次操作,輸入k 行aj,bj和cj,分別代表城市aj和城市bj經(jīng)過的管道流量增加cj單位。(2≤N≤50000,1≤k≤100000)
算法的輸出格式為:輸出一行整型數(shù)據(jù),即整個管道網(wǎng)絡(luò)的最大壓力。
A 國的管道運輸網(wǎng)絡(luò)看做一個無向圖,有N 個點、N-1 條邊,兩兩點之間剛好相互可達(dá),那么這個無向圖不存在環(huán),因此它也是無根樹。對無根樹T1中某些路徑經(jīng)過k 次增流,每次增流相當(dāng)于增加邊權(quán),最終需要求k 次增流后的最大邊的權(quán)值是多少。下面,通過LCA 和樹上標(biāo)記算法來解決這個問題,并分析為什么樹上差分不可以有效地解決此問題。
(1)數(shù)列差分
數(shù)列區(qū)間操作常用的方法為數(shù)列差分[3],從數(shù)列差分的角度進(jìn)行推廣,對樹鏈操作,因此想到樹上差分,下面先介紹數(shù)列差分。數(shù)列差分可以做到批量操作數(shù)列區(qū)間加減法或者乘除法,適用于需要多次操作區(qū)間的情況。與枚舉算法對比,枚舉算法每次操作需要遍歷區(qū)間,時間復(fù)雜度為O(n2),而數(shù)列差分只需要將需要操作的端點標(biāo)記即可,最后遍歷一遍數(shù)列即可得到最終的結(jié)果,時間復(fù)雜度為O(n)。
例如,存在數(shù)列{1,5,6,2,5,5},分別對區(qū)間[0,4]、[1,5]的每個數(shù)加1,首先計算出差分?jǐn)?shù)組d={1,4,1,-4,3,0,0},然后處理端點,對于區(qū)間[0,4],將d[0]++,d[4+1]--,對于區(qū)間[1,5],d[1]++,d[5+1]--,最終d={2,5,1,-4,3,-1,-1},之后求d 數(shù)列的前綴和,即為最終答案:d={2,7,8,4,7,6}(答案只取前六個數(shù))。
(2)數(shù)列標(biāo)記
同樣是對數(shù)列區(qū)間操作,不使用到差分,只對區(qū)間端點標(biāo)記,也可以在O(n)時間復(fù)雜度下解決問題。同樣在上一個例子的基礎(chǔ)上,設(shè)標(biāo)記數(shù)組為flag={0,0,0,0,0,0,0},若[0,4]、[1,5]每個數(shù)都加1,則flag[0]++、flag[4+1]--、flag[1]++、flag[5+1]--,flag={1,1,0,0,0,-1,-1},flag 前綴和為s={1,2,2,2,2,1,0},這個數(shù)列就是原數(shù)列每個數(shù)的增量,因此,最終結(jié)果為{1+1,5+2,6+2,2+2,5+2,5+1},即{2,7,8,4,7,6}。
(1)LCA 與樹上差分
類比數(shù)列差分,結(jié)合LCA 做樹上差分,能做到多次操作某一條鏈的權(quán)值。假設(shè)根節(jié)點為結(jié)點1,dis[i]代表結(jié)點i 前向邊的差分流量,從結(jié)點1 開始遍歷,首先求出初始的dis 數(shù)列,之后,若對結(jié)點aj到結(jié)點bj中每一條邊加cj,因為涉及到操作LCA(aj,bj)的子結(jié)點,且又無法直接判斷LCA(aj,bj)的子結(jié)點,是否在結(jié)點aj到結(jié)點bj的路徑上,因此需要對結(jié)點aj到結(jié)點bj的路徑搜索。
圖2 示例圖(二)
如圖2 所示,對結(jié)點7 和結(jié)點8 的路徑權(quán)值都增加1,LCA(7,8)為結(jié)點2,因為結(jié)點4 和結(jié)點5 在路徑之上,并且為結(jié)點2 的子結(jié)點,因此dis[4]++,dis[5]++,對結(jié)點7 和結(jié)點8 的子結(jié)點操作,dis[10]--,dis[11]--,最后從結(jié)點1 開始求一遍前綴和即可。(這里在確定結(jié)點4 和結(jié)點5 時,則需要對結(jié)點7 到結(jié)點8 的路徑搜索。)
時間復(fù)雜度分析:k 次詢問,每次都需要對路徑進(jìn)行搜索,為O(n),所以總的復(fù)雜度為O(kn),與樸素的暴力搜索算法時間復(fù)雜度一致,因為用到了LCA 和其他的處理,因此時間復(fù)雜度常數(shù)會更大,總的來說還不如暴力搜索法。
(1)LCA 與樹上標(biāo)記
將根結(jié)點作為參考點,此時將dis[i]定義為結(jié)點i到根結(jié)點路徑上邊的增量,pre[i]定義為結(jié)點i 的前向邊權(quán),若對結(jié)點aj到結(jié)點bj中每一條邊加cj,則dis[aj]+=cj,dis[bj]+=cj,dis[LCA(aj,bj)]-=cj,最后后序遍歷樹T1,原始的邊的權(quán)值加上dis 的增量和,即為操作k 次后的邊權(quán)結(jié)果,并求出邊權(quán)的最大值即為問題結(jié)果。
圖3 示例圖(三)
如圖3 所示,對結(jié)點7 和結(jié)點8 的路徑權(quán)值都增加1,dis[7]++,dis[8]++,dis[2]-=2,計算dis 從葉子結(jié)點到根節(jié)點的累積增量,從結(jié)點7 至結(jié)點1,從結(jié)點8 至結(jié)點1,dis[7]=1,dis[4]=1,dis[8]=1,dis[5]=1,dis[2]=dis[4]+dis[5]+dis[2]=0,最終pre[i]+=dis[i]為最終結(jié)果。
算法復(fù)雜度分析:LCA 使用歐拉序結(jié)合ST 表的方法,ST 表預(yù)處理的時間復(fù)雜度為O(nlog2n),查找的復(fù)雜度為O(1),樹鏈操作都轉(zhuǎn)化為標(biāo)記,最后只需要遍歷求出累積值即可,時間復(fù)雜度為O(n),所以整個算法時間復(fù)雜度為O(nlog2n)。
本文分析了歐拉序、ST 表、數(shù)列區(qū)間問題和樹上路徑問題,結(jié)合歐拉序和ST 表能求出樹上兩結(jié)點的最近公共祖先,再以根節(jié)點為參考進(jìn)行樹上標(biāo)記,能在O(nlog2n)的時間復(fù)雜度下,求解出了管道網(wǎng)絡(luò)的最大壓力,而暴力搜索算法和樹上差分算法的復(fù)雜度為O(kn),由此可知在需要查詢的次數(shù)k 較多時,本文提出的最近公共祖先和樹上標(biāo)記算法,能大大節(jié)省計算資源,在管道運輸監(jiān)控上具有較大價值。