時間依賴網(wǎng)絡(luò)中國郵路問題的分支限界算法.pdf

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

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

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

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