如何使用回溯法實(shí)現(xiàn)網(wǎng)絡(luò)設(shè)計(jì)問題算法的設(shè)計(jì)

　　1.問題背景及描述

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

　　2.方法介紹

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

　　2.2 回溯法的基本步驟

　?。?）確定問題類型；

　?。?）確定解空間；

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

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

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

　　3.問題分析

　　本題可以理解為北京石油公司通過管道將石油輸送到其他多個(gè)城市石油公司的網(wǎng)絡(luò)結(jié)構(gòu)，在這個(gè)網(wǎng)絡(luò)結(jié)構(gòu)中，各個(gè)石油公司為網(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?？山⑷鐖D所示的解空間（0 表示不在該點(diǎn)設(shè)置增壓器，表示在該點(diǎn)設(shè)置增壓器）：