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

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

2、的中國(guó)郵路問(wèn)題相對(duì)于傳統(tǒng)中國(guó)郵路問(wèn)題的優(yōu)勢(shì)，以及時(shí)間依賴網(wǎng)絡(luò)中中國(guó)郵路問(wèn)題的研究現(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í)例，以便對(duì)傳統(tǒng)方法不適于時(shí)變網(wǎng)絡(luò)環(huán)境的根本原因有更深地了解。 (2)給出時(shí)間依賴中國(guó)郵

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

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