[科普中國(guó)]-最小樹(shù)問(wèn)題

基本概念

最小樹(shù)問(wèn)題是網(wǎng)絡(luò)最優(yōu)化問(wèn)題之一，是指如何從網(wǎng)絡(luò)的支撐樹(shù)中求出最小樹(shù)的問(wèn)題。求解最小樹(shù)問(wèn)題常用破圈法和貪婪算法。最小生成樹(shù)問(wèn)題是組合優(yōu)化中的一個(gè)重要的問(wèn)題。自五十年代后期Rosenstiehl, Prim和Kruskal先后給出求解這一問(wèn)題的算法以來(lái)，人們對(duì)這個(gè)問(wèn)題的研究興趣一直未斷，相關(guān)的理論被應(yīng)用到很多領(lǐng)域?，F(xiàn)在這個(gè)問(wèn)題己經(jīng)得到了很好的解決，其中經(jīng)典的算法有破圈法、邊割法、還有避圈法。

研究背景及意義隨著網(wǎng)絡(luò)通信技術(shù)的日益成熟，互聯(lián)網(wǎng)在人們生活中發(fā)揮著越來(lái)越重要的作用，基于網(wǎng)絡(luò)的應(yīng)用和服務(wù)也是層出不窮。其中一些應(yīng)用如視頻會(huì)議、網(wǎng)絡(luò)教學(xué)、多人游戲等，傳輸時(shí)間長(zhǎng)、數(shù)據(jù)量大、要求網(wǎng)絡(luò)延遲小，對(duì)網(wǎng)絡(luò)的傳輸和處理能力要求很高。對(duì)于這樣的應(yīng)用如果使用單播或廣播方式進(jìn)行通信，數(shù)據(jù)需要不斷的復(fù)制，傳輸?shù)臄?shù)據(jù)量太大，傳輸?shù)男屎艿?。同時(shí)在數(shù)據(jù)傳輸時(shí)需要使用大量的帶寬，對(duì)帶寬的要求很高，帶寬較低時(shí)很容易使網(wǎng)絡(luò)阻塞。多播能夠有效的解決這些網(wǎng)絡(luò)應(yīng)用。

多播(multicast)也稱為組播，是一種從源節(jié)點(diǎn)向多個(gè)目的節(jié)點(diǎn)傳輸同一信息的通信方式。所有的目的節(jié)點(diǎn)組成的集合被稱為多播組，多播組中的每個(gè)成員被稱為多播組成員。多播通信有多種方法進(jìn)行路由，其中最簡(jiǎn)單的也是最常用的方法是沿樹(shù)狀結(jié)構(gòu)進(jìn)行路由。多播樹(shù)(multicasting tree) }'〕是一棵根為源節(jié)點(diǎn)的生成樹(shù)，它包含了所有的目的節(jié)點(diǎn)。利用多播樹(shù)進(jìn)行數(shù)據(jù)傳輸?shù)膬?yōu)點(diǎn)在于，從根節(jié)點(diǎn)開(kāi)始數(shù)據(jù)以并行方式沿樹(shù)干傳輸，最終到達(dá)所有的目的節(jié)點(diǎn)，這樣能夠加快傳輸速度。此外，在數(shù)據(jù)傳輸過(guò)程中，只在樹(shù)權(quán)處進(jìn)行數(shù)據(jù)信息的復(fù)制，這樣網(wǎng)絡(luò)中傳輸?shù)男畔⒆钌?，能夠減少占用的帶寬，提高網(wǎng)絡(luò)利用率。

由于多播路由是根據(jù)多播樹(shù)進(jìn)行路由的，因此如果能夠找到費(fèi)用最小的多播樹(shù)，多播路由問(wèn)題就得到了解決。尋找費(fèi)用最小的多播樹(shù)可以概括為尋找給定節(jié)點(diǎn)集的最小生成樹(shù)，這就是S teiner最小樹(shù)問(wèn)題，得到的最小生成樹(shù)稱為Steiner最小樹(shù)。Steiner最小樹(shù)問(wèn)題根據(jù)不同情況又可以細(xì)分為垂直距離的、歐幾里得距離的、圖的等。由于圖的Steiner最小樹(shù)問(wèn)題應(yīng)用最為廣泛。

Steiner最小樹(shù)問(wèn)題Steiner最小樹(shù)問(wèn)題最早被作為一個(gè)數(shù)學(xué)問(wèn)題提出，是經(jīng)典的組合優(yōu)化問(wèn)題。Steiner最小樹(shù)問(wèn)題經(jīng)歷了較長(zhǎng)時(shí)間的發(fā)展，最終才形成完整的定義。早在1634年，法國(guó)數(shù)學(xué)家Fermat提出這樣一個(gè)問(wèn)題:假設(shè)在平面上有a,b,。三個(gè)點(diǎn)，怎樣尋找第四個(gè)點(diǎn)P，使得點(diǎn)P到點(diǎn)a,b,c的距離之和最小。這個(gè)問(wèn)題后來(lái)被稱為Fermat問(wèn)題。

19世紀(jì)初，瑞士數(shù)學(xué)家Steiner將Fermat問(wèn)題推廣為:假設(shè)在平面上有a1，a2,a3……an這n(n > 3)個(gè)點(diǎn)，怎樣尋找一個(gè)點(diǎn)P，使得點(diǎn)P到這n個(gè)點(diǎn)的距離之和最小。1909年，德國(guó)數(shù)學(xué)家Weber首次把該問(wèn)題推廣應(yīng)用到工廠選址問(wèn)題中。假設(shè)某地有若干個(gè)倉(cāng)庫(kù)，想要建造一個(gè)工廠，對(duì)每個(gè)倉(cāng)庫(kù)賦一個(gè)權(quán)值用來(lái)表示該倉(cāng)庫(kù)的影響因素。如何選擇廠址，使得每個(gè)倉(cāng)庫(kù)的權(quán)值乘以倉(cāng)庫(kù)到工廠的距離的總和最小。

1941年，Courant和Robbins在《什么是數(shù)學(xué)》一書(shū)中對(duì)Fermat問(wèn)題進(jìn)行了一種更有意義的推廣:假設(shè)在平面上有a1，a2,a3……an這n,(n > 3)個(gè)點(diǎn)，怎樣尋找另外的若干個(gè)點(diǎn)，使得原有的n個(gè)點(diǎn)與后來(lái)加入的點(diǎn)組成的網(wǎng)絡(luò)的總邊長(zhǎng)最小。他們把這個(gè)問(wèn)題稱為Steiner樹(shù)問(wèn)題，并給出了一些基本性質(zhì)。

在網(wǎng)絡(luò)通信中，有一些網(wǎng)絡(luò)應(yīng)用要求數(shù)據(jù)從源節(jié)點(diǎn)出發(fā)，最終被多個(gè)目標(biāo)節(jié)點(diǎn)接收，這就是多播路由問(wèn)題〔細(xì)。解決多播路由問(wèn)題的方法有多種，最簡(jiǎn)單常用的方法是求解包含源節(jié)點(diǎn)和所有目標(biāo)節(jié)點(diǎn)的最小生成樹(shù)。但是在許多情況下，另外加入幾個(gè)節(jié)點(diǎn)，得到的最小生成樹(shù)的總邊長(zhǎng)有可能會(huì)更小，這種思想就來(lái)源于Steiner最小樹(shù)問(wèn)題。

分類Steiner最小樹(shù)問(wèn)題可以分為垂直S teiner最小樹(shù)問(wèn)題、歐氏S teiner最小樹(shù)問(wèn)題、圖的S teiner最小樹(shù)問(wèn)題，下面分別進(jìn)行介紹。

垂直Steiner最小樹(shù)問(wèn)題假設(shè)在平面上有一個(gè)節(jié)點(diǎn)集P包含n個(gè)給定的節(jié)點(diǎn)，尋找一棵覆蓋節(jié)點(diǎn)集P中所有節(jié)點(diǎn)的樹(shù)T，使得樹(shù)T的總邊長(zhǎng)盡可能的小。節(jié)點(diǎn)pi和pj之間的邊長(zhǎng)用它們的曼哈頓距離(Manhattan Distance)來(lái)表示。樹(shù)T肯定包含節(jié)點(diǎn)集P中的所有點(diǎn)，也有可能包含其他的一些點(diǎn)，把這些后來(lái)添加的節(jié)點(diǎn)稱為S teiner點(diǎn)?？傔呴L(zhǎng)最小的樹(shù)T稱為垂直Steiner最小樹(shù)。由于使用曼哈頓距離來(lái)計(jì)算，所以節(jié)點(diǎn)之間的邊為直線或者是折線，所有的Steiner點(diǎn)一定在經(jīng)過(guò)樹(shù)T的水平線和垂直線的交點(diǎn)上。

歐氏Steiner最小樹(shù)問(wèn)題在平面上給定一個(gè)節(jié)點(diǎn)集合V，尋找另外的一個(gè)節(jié)點(diǎn)集合S，使得節(jié)點(diǎn)集合V∪S的最小生成樹(shù)T的總長(zhǎng)度最小。節(jié)點(diǎn)vi和sj之間的邊長(zhǎng)用它們的歐氏距離來(lái)表示。把最小生成樹(shù)T稱為歐氏Steiner最小樹(shù)。

圖的Steiner最小樹(shù)問(wèn)題圖的Steiner最小樹(shù)問(wèn)題是求圖中連接給定頂點(diǎn)最小樹(shù)長(zhǎng)的問(wèn)題，最早是在1971年由Hakimi和Levin提出,1972年Karp證明了在一般情況下，在多項(xiàng)式時(shí)間內(nèi)不可能得到最優(yōu)解，該問(wèn)題是一個(gè)NP一完全問(wèn)題。2