求解單位L∞范數下帶值約束的最短路逆問題的算法?

于成成 周澤聿 張斌武

（1.河海大學企業管理學院 常州 213022）（2.河海大學常州校區數理教學部 常州 213022）

1 引言

最短路問題是一類很重要的問題，其逆問題也具有很大的研究價值，它們在交通網絡、通信網絡等實際問題中有著廣泛的應用。同時很多網絡問題的逆問題也可能轉化成最短路逆問題，最短路逆問題的解決有助于許多其他網絡問題的解決。

近年來，最短路逆問題受到眾多學者的關注，相關學者在最短路逆問題上也取得了一些進展。D.Burton 和Ph.LTiont［1］首先提出最短路逆問題，并使用二次規劃的算法來求解L2范數下的最短路逆問題。Zhang Jianzhong等［2］引入列生成算法來求解單位L1范數下的最短路逆問題。Ahuja等［3］將單位L1范數下的最短路逆問題轉化為最短路問題，從而得到了一個強多項式時間算法；將單位L∞范數下的最短路逆問題轉化為最小平均圈問題；將非單位L∞范數下的最短路逆問題轉化為最小費用和時間比例圖問題。Xu Shaoji 等［4］將非單位權重下的最短路逆問題轉化為最小費用流問題。在有值約束的條件下，Burton等［5］證明了非單位L2范數下帶值約束的最短路逆問題是NP完全問題。張斌武等［6～11］研究Hamming 距離下各種網絡的最短路逆問題及改進問題，對一些特殊網絡給出了強多項式時間算法及近似算法，并證明了Hamming距離下一般網絡的最短路逆問題是NP 困難的。除此之外，還有學者［12～14］研究了其他約束條件下的最短路逆問題，取得了一些進展。

本文研究單位L∞范數下帶值約束的最短路逆問題，要求調整邊長度向量，使得給定路徑P0為新長度向量下圖G的最短路徑，且在新長度向量下P0的長度不超過給定的上界，并使得邊長度的最大改變量最小。

最短路逆問題在實際生活中有著重要的應用。例如，有一個交通網絡G=(V，E，w)，V集合表示不同的城市，E集合表示城市之間的道路，w集合表示車輛通過不同道路的時間向量。現在有兩個重要的城市s和t，兩城市間存在若干的道路，其中包含一條從s到t的城際快速通道P0，要求車輛通過城際快速通道所用的時間為兩城市所有道路中最短的，同時車輛通過城際快速通道所用的時間不能超過給定的上界K。為了使城際快速通道P0成為連接兩城市s和t最快的道路，需要對許多道路進行改造，改造會產生一定的費用，在滿足要求的情況下，總的調整費用最小。

2 問題介紹

L∞范數下帶值約束的最短路逆問題可以描述為

要求改變邊長度向量w，使改變之后的長度向量={，...，} 滿足：

1）P0為圖=(V，E，wˉ )上的最短路；

2）(P0)≤K；

3）‖w-‖∞=max(ci|-wi|;ei∈E)最小。

本文主要研究邊單位改變費用相同的情況，即ci=1，i=1，2，...，m。

3 單位L∞范數下帶值約束的最短路逆問題的算法

為給出所研究問題的算法，先對圖G的邊長度向量w進行如下調整：若ej∈P0，則將其邊長度調整為負值，即=-wj；若ej?P0，則其邊長度不進行調整，即=wj。調整之后的圖記為G′=(V，E，w′)。

定義1在w′下，若圈C上所有邊的長度之和小于零，即＜0，則稱圈C為負圈。

引理1［3］路徑P0為圖G上的最短路的充分必要條件是圖G′中不存在負圈。

由引理1 可知，若要使得P0成為圖G上的最短路徑，只需要調整圖G′的邊長度向量w′使其不存在負圈。

定 義2設Ω 為 圖G′中 圈 的 集 合，對?C∈Ω，定義平均圈為圈C上邊的長度和與邊個數的比值，記為其中 |C|為圈C上邊的個數。最小平均圈λ*表示集合Ω 中所有圈其平均圈的最小值，即λ*=。

引理2［3］若圖G′的最小平均圈λ*＜0，則是使圖G′不存在負圈的最小調整量。

推論1在圖G中，使得P0成為最短路的最小調整費用為|。

下面對圖G′分兩種情況進行討論：

1）當圖G′不存在負圈時，由引理1可知，P0已經為圖G的最短路徑；

故單位L∞范數下最短路逆問題即轉化為求圖G′的最小平均圈問題。

下面給出求G′的最小平均圈的方法：對無向圖G′進行如下調整：若ej∈P0，則將ej調整為單向邊，且邊的方向與路徑P0的方向相同；若ej?P0，則將ej調整為雙向邊。調整之后的有向圖記為圖G″，其最小平均圈記為λ*0。Karp［15］給出了如下的求解有向圖G″中強連通分量的最小平均圈的算法，其算法的時間復雜度為O(nm)。

其中Fk(v)表示從起點s到點v必須強制經過k條邊的最短路徑。Fk( )v計算公式為

其中f(u，v)表示圖G″中點u到v的邊長度。且有F0(s)=0；F0(v)=∞，v≠s。

容易證明圖G′的最小平均圈等于圖G″的最小平均圈，即λ*=，故λ*可在時間復雜度O(nm)內求出。

下面給出求解單位L∞范數下帶值約束的最短路逆問題的算法。

該算法的思想是：將圖G調整為含負權圖G′，求解圖G′的最小平均圈λ*，設單位L∞范數下滿足最短路逆問題約束的最小調整費用為μ1，若λ*》≥0，根據引理1，P0已為圖G的最短路徑，則μ1=0；若λ*＜0，根據引理1和引理2，使得P0為圖G最短路徑的最小調整費用為 |λ*|，則μ1=-λ*。計算t=(dw(P0)-K)/ |P0|，設單位L∞范數下滿足值約束的最小調整費用為μ2，若t≤0，的長度已不超過上界K，則μ2=0；若t＞0，滿足值約束的最小調整費用為t，則μ2=t。設單位L∞范數下帶值約束的最短路逆問題的最小調整費用為μ*，則μ*為 調 整 費 用μ1，μ2的 最 大 值 ，即μ*=max(μ1，μ2)。算法的具體過程如下：

算法1（求解單位L∞范數下帶值約束的最短路逆問題的算法）：

系統設置有完備的日志管理功能，網站管理員登錄站群后臺后的每一步操作，都有詳細的記錄。如誰，在什么時間，用什么IP，發布了什么內容，上傳了什么圖片、附件、視頻等。對操作記錄的完備管理，是實現站群系統安全管理的重要輔助。

Step1：將圖G 轉化為圖G′，求解圖G′的最小平均圈λ*。若λ*》≥0，則μ1=0；若λ*＜0，則μ1=-λ*。

定理1μ*=max(μ1，μ2)為單位L∞范數下帶值約束的最短路逆問題的最小調整費用。

證明下面對μ1，μ2的取值分四種情況：

1）μ1=0，μ2=0

顯然圖G的路徑P0是最短路，且滿足dw(P0)≤K，其權重向量w不需要進行調整，因此μ*=max(μ1，μ2)=0 為單位L∞范數下帶值約束的最短路逆問題的最小調整費用。

2）μ1＞0，μ2=0

圖G的路徑P0不是最短路，但滿足dw(P0)≤K，由引理1 和引理2 可知，μ1= |λ*|為滿足最短路約束的最小調整費用，因此μ*=max(μ1，μ2)=μ1為單位L∞范數下帶值約束的最短路逆問題的最小調整費用。

3）μ1=0，μ2＞0

圖G的路徑P0是最短路，但不滿足dw(P0)≤K，μ2=t為滿足值約束的最小調整費用，因此μ*=max(μ1，μ2)=μ2為單位L∞范數下帶值約束的最短路逆問題的最小調整費用。

4）μ1＞0，μ2＞0

此時圖G的路徑P0不是最短路，且不滿足dw(P0)≤K。

μ*=max(μ1，μ2)≥μ1= |λ*|，由引理2 可知，|λ*|是使圖G′不存在負圈的最小調整量，故μ*的調整量可以使得圖G′不存在負圈，即滿足最短路的約束；μ*=max( )μ1，μ2≥μ2=t，t是單位L∞范數下滿足值約束的最小調整量，故μ*的調整量可以使得滿足值約束。

因此μ*=max(μ1，μ2)的調整量可以同時滿足最短路約束和值約束。

設μa滿 足 0 ≤μa＜μ*。 若μ1≥μ2，有μa＜μ1= |λ*|，由引理2 可知，|λ*|是使圖G′不存在負圈的最小調整量，故μa的調整量不可以使得圖G′不存在負圈，即不滿足最短路約束；若μ1＜μ2，有μa＜μ2=t，t是單位L∞范數下滿足值約束的最小調整量，故μa的調整量不滿足值約束。

因此小于μ*的調整量不可以同時滿足最短路約束和值約束。

綜上，μ*的調整量可以同時滿足最短路約束和值約束，且小于μ*的調整量不可以同時滿足最短路約束和值約束。因此μ*=max(μ1，μ2) 是單位L∞范數下帶值約束的最小調整費用。

綜合以上四種情況，定理1得證。

記圖G調整之后的長度向量為w*=，由定理1 可知，得到的長度向量wˉ即為單位L∞范數下帶值約束的最短路逆問題的最優解。算法1的時間復雜度為O(nm) 。

4 計算實例

下面給出一個實例，設圖G=(V，E，w)，如圖1所示。給定路徑P0為A→B→C→E→F，其中A為P0的起點，F為P0的終點，其邊長度向量w見圖1，最短路徑的長度的上界為10。現求解圖G在單位L∞范數下帶值約束的最短路逆問題的最優調整量。

將圖G調整為負權圖G′，如圖2所示。

為求圖G′的最小平均圈λ*，將其調整為有向圖G″，如圖3所示。

根據Karp 的算法求解圖G″的最小平均圈計算得=-1.40。故單位L∞范數下滿足最短路逆問題約束的最小調整費用為μ1=1.40。

計算得t=(dw(P0)-K)/ |P0|=1，故單位L∞范數下滿足值約束的最小調整費用μ2=1。因此最優 調 整 量μ*=max(μ1，μ2)=1.40 ，調 整 之 后 的 圖=(V，E，wˉ )如圖4所示。

為了驗證結果的正確性，借助二分法進行驗證：經過λ1=1 的調整，圖G不同時滿足最短路和值約束的條件，經過λ2=2 的調整，圖G同時滿足最短路和值約束的條件，依據二分法的思想再判斷經過λ3=1.5 的調整后圖G是否滿足條件，依次迭代。圖G的調整量經過9 次迭代之后誤差＜0.001，二分法計算的最優調整量為1.3998，在誤差允許范圍內與本文提出的算法相等，證明了算法的正確性。

5 結語

本文研究了單位L∞范數下帶值約束的最短路逆問題，將單位L∞范數下的最短路逆問題轉化為含負權圖G′的最小平均圈問題。給出單位L∞范數下帶值約束的最短路逆問題的算法，該算法并不需要求出所有的圈，算法的時間復雜度為O(nm)，并證明算法得到問題的最優解。給出了一個計算實例，用二分法驗證算法的正確性。該研究方法對某些最短路逆問題的求解有一定的借鑒意義。

還有許多帶值約束的最短路逆問題值得研究。如單位L∞范數下邊的長度有界帶值約束的最短路逆問題、L∞范數下的帶值約束的最短路逆問題、L1范數下帶值約束的最短路逆問題等。