關(guān)于混合Halin圖上Stacker Crane Problem算法的研究.pdf

1、本論文研究了在Halin圖的條件下求解Stacker Crane Problem(SCP)的高效率算法。
　　 SCP描述：給定一個(gè)邊賦權(quán)的混合圖G=(V,A，E)，找出包含所有弧的一個(gè)有向圈，使得該圈上的總代價(jià)不高于某個(gè)給定值。SCP在圖論中是一個(gè)經(jīng)典的環(huán)路優(yōu)化問題，在普通圖中它是NP完全的。SCP在通信網(wǎng)絡(luò)和運(yùn)輸網(wǎng)絡(luò)優(yōu)化中有很高的應(yīng)用價(jià)值。本論文中我們考慮在Halin圖的特殊條件下利用扇收縮等技巧，得到一種線性時(shí)間效率的算法

2、。在Halin中，我們考慮求解最小代價(jià)SCP：尋找一個(gè)包含所有弧的一個(gè)有向圈，使得該圈總代價(jià)是所有這類圈中的最小值。
　　 首先，我們在第3章研究普通混合Halin圖中尋找有向圈的方法，在此提出的算法就是基于后序遍歷和Halin圖的扇收縮操作，逐步縮小問題的規(guī)模而得到的一種線性時(shí)間效率的算法。其中還提出一種求Halin圖中扇內(nèi)三個(gè)端點(diǎn)間有向路徑的方法：扇擴(kuò)展。并給出該算法的時(shí)空效率分析。
　　 再次，我們在第3章的研究基