1) 問(wèn)題描述 天然氣經(jīng)過(guò)管道網(wǎng)絡(luò)從其生產(chǎn)基地輸送到消耗地，在傳輸過(guò)程中，其性能的某一個(gè)或幾個(gè)方面可能會(huì)有所衰減（例如氣壓）。為了保證信號(hào)衰減不超過(guò)容忍值，應(yīng)在網(wǎng)絡(luò)中的合適位置放置放大器以增加信號(hào)（例如電壓）使其與源端相同。設(shè)計(jì)算法確定把信號(hào)放大器放在何處，能使所用的放大器數(shù)目最少并且保證信號(hào)衰減不超過(guò)給定的容忍值。 2) 基本要求 (1) 建立模型，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)； (2) 設(shè)計(jì)算法完成放大器的放置； (3) 分析算法的時(shí)間復(fù)雜度。 3) 設(shè)計(jì)思想 為了簡(jiǎn)化問(wèn)題，假設(shè)分布網(wǎng)絡(luò)是二叉樹(shù)結(jié)構(gòu)，源端是樹(shù)的根結(jié)點(diǎn)，信號(hào)從一個(gè)結(jié)點(diǎn)流向其孩子結(jié)點(diǎn)，樹(shù)中的每一結(jié)點(diǎn)（除了根）表示一個(gè)可以用來(lái)放置放大器的位置。