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

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

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

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

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