時間依賴網絡中國郵路問題的分支限界算法.pdf

1、中國郵路問題是圖論經典問題之一，在軟件測試、郵件投遞等諸多領域中都被廣泛應用。時間依賴中國郵路問題是對中國郵路問題的擴展，它考慮了時間因素，在實時軟件測試等當前許多具有時間依賴性質的熱門問題中，比中國郵路問題更具優(yōu)勢，具有重要的應用和研究價值。 本文介紹了在傳統靜態(tài)網絡中，中國郵路問題(Chinese Postman Problem簡記CPP)的分類、研究現狀、以及應用領域；然后分析了傳統中國郵路問題的局限和在時間依賴網絡環(huán)境下

2、的中國郵路問題相對于傳統中國郵路問題的優(yōu)勢，以及時間依賴網絡中中國郵路問題的研究現狀和當前遇到的困難以及研究意義；為后面研究打下了基礎。 在這篇文章中，有以下內容： (1)給出傳統方法并不適于時間依賴網絡環(huán)境的根本原因：網絡的時間依賴特性導致網絡各個邊權值的不固定。我們給出傳統方法并不適用于時變網絡(即時間依賴網絡)條件的病態(tài)實例，以便對傳統方法不適于時變網絡環(huán)境的根本原因有更深地了解。 (2)給出時間依賴中國郵

3、路問題的特性和分支限界最優(yōu)化方法。我們用定理和推論的形式給出適合求解時變無向、有向中國郵路問題的特性，并且對這些特性進行了證明，確保了它們的正確性，并以此為基礎構造問題的剪枝條件，設計了相應的分支限界最優(yōu)化方法： (3)對于FIFO的時間依賴網絡增加了一些特殊性質，并提高了算法的效率。針對FIFO(first in first out)這一類特殊的時變網絡，我們給出相應的特性以及基于此的FIFO剪枝條件，從而得到更高效的分支限界

4、最優(yōu)化方法。 (4)對算法進行了測試和分析。我們先構造該問題的解空間樹，對問題的規(guī)模有了初步的了解，同時通過一個實例簡單地演示了該算法的執(zhí)行過程，并對該問題和算法進行了分析；最后，給出了算法的測試結果，并在實驗的基礎上對該算法進行更深一部的分析。 本文首次利用分支限界方法，求解了時間依賴網絡中國郵路問題的精確解。引入了時間因素，使問題的復雜性大大增加。根據實驗結果我們可知算法對于小規(guī)模的時間依賴有向、無向中國郵路問題非常