1.問題背景及描述

　　隨著石油在人們?nèi)粘Ｉ钪械膹V泛應(yīng)用，石油公司需要通過管道輸送大量的石油，目前，中國油氣管道正呈現(xiàn)出蓬勃發(fā)展的勢頭，已成為我國第五大運(yùn)輸業(yè)，而在石油傳輸網(wǎng)絡(luò)的設(shè)計中通常會遇到最少增壓器的問題，選題中網(wǎng)絡(luò)設(shè)計問題對石油傳輸網(wǎng)絡(luò)最少增壓器的問題有了詳細(xì)的描述，再次，我們選用回溯法來解決這個問題，并對時間復(fù)雜度進(jìn)行了分析和討論。

　　2.方法介紹

　　2.1 回溯法的基本思想確定了解空間的組織結(jié)構(gòu)后，回溯法從開始結(jié)點(diǎn)（根節(jié)點(diǎn)）出發(fā)，以深度優(yōu)先方法搜索整個解空間，在開始結(jié)點(diǎn)成為活節(jié)點(diǎn)，同時成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)，在當(dāng)前結(jié)點(diǎn)處，搜索向縱深方向移至一個新節(jié)點(diǎn)，這個新節(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再想縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時，應(yīng)往回移動（回溯）至最近的或節(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。回溯法以這種工作方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點(diǎn)時為止。

　　2.2 回溯法的基本步驟

　　（1）確定問題類型；

　　（2）確定解空間；

　　（3）確定解空間的組織結(jié)構(gòu)；

　　（4）從根節(jié)點(diǎn)出發(fā)，利用深度優(yōu)先算法來遍歷解空間；

　　（5）當(dāng)找到答案或只剩下死結(jié)點(diǎn)時，該問題完成。

　　3.問題分析

　　本題可以理解為北京石油公司通過管道將石油輸送到其他多個城市石油公司的網(wǎng)絡(luò)結(jié)構(gòu)，在這個網(wǎng)絡(luò)結(jié)構(gòu)中，各個石油公司為網(wǎng)絡(luò)的結(jié)點(diǎn)，北京公司為根節(jié)點(diǎn) S，在運(yùn)輸過程中，需要保持網(wǎng)絡(luò)中最低油壓 Pmin，因此設(shè)置了增壓器，，在設(shè)置增壓器的頂點(diǎn)處油壓可升至 Pmax，油壓從 Pmax 減至 Pmin 可是石油傳輸?shù)木嚯x至少為 d。可建立如圖所示的解空間（0 表示不在該點(diǎn)設(shè)置增壓器，表示在該點(diǎn)設(shè)置增壓器）：