最小樹問題是網路最最佳化問題之一，是指如何從網路的支撐樹中求出最小樹的問題。求解最小樹問題常用破圈法和貪婪算法。最小生成樹問題是組合最佳化中的一個重要的問題。自五十年代後期Rosenstiehl, Prim和Kruskal先後給出求解這一問題的算法以來，人們對這個問題的研究興趣一直未斷，相關的理論被套用到很多領域。現在這個問題己經得到了很好的解決，其中經典的算法有破圈法、邊割法、還有避圈法。
基本介紹
- 中文名：最小樹問題
- 外文名：minimum tree problem
- 類別：數學
- 問題類別：網路最最佳化問題
- 套用：網路
- 分類：Steiner最小樹
基本概念,研究背景及意義,Steiner最小樹問題,分類,
基本概念
最小樹問題是網路最最佳化問題之一，是指如何從網路的支撐樹中求出最小樹的問題。求解最小樹問題常用破圈法和貪婪算法。最小生成樹問題是組合最佳化中的一個重要的問題。自五十年代後期Rosenstiehl, Prim和Kruskal先後給出求解這一問題的算法以來，人們對這個問題的研究興趣一直未斷，相關的理論被套用到很多領域。現在這個問題己經得到了很好的解決，其中經典的算法有破圈法、邊割法、還有避圈法。
研究背景及意義
隨著網路通信技術的日益成熟，網際網路在人們生活中發揮著越來越重要的作用，基於網路的套用和服務也是層出不窮。其中一些套用如視頻會議、網路教學、多人遊戲等，傳輸時間長、數據量大、要求網路延遲小，對網路的傳輸和處理能力要求很高。對於這樣的套用如果使用單播或廣播方式進行通信，數據需要不斷的複製，傳輸的數據量太大，傳輸的效率很低。同時在數據傳輸時需要使用大量的頻寬，對頻寬的要求很高，頻寬較低時很容易使網路阻塞。多播能夠有效的解決這些網路套用。
多播(multicast)也稱為組播，是一種從源節點向多個目的節點傳輸同一信息的通信方式。所有的目的節點組成的集合被稱為多播組，多播組中的每個成員被稱為多播組成員。多播通信有多種方法進行路由，其中最簡單的也是最常用的方法是沿樹狀結構進行路由。多播樹(multicasting tree) }'〕是一棵根為源節點的生成樹，它包含了所有的目的節點。利用多播樹進行數據傳輸的優點在於，從根節點開始數據以並行方式沿樹幹傳輸，最終到達所有的目的節點，這樣能夠加快傳輸速度。此外，在數據傳輸過程中，只在樹權處進行數據信息的複製，這樣網路中傳輸的信息最少，能夠減少占用的頻寬，提高網路利用率。
由於多播路由是根據多播樹進行路由的，因此如果能夠找到費用最小的多播樹，多播路由問題就得到了解決。尋找費用最小的多播樹可以概括為尋找給定節點集的最小生成樹，這就是S teiner最小樹問題，得到的最小生成樹稱為Steiner最小樹。Steiner最小樹問題根據不同情況又可以細分為垂直距離的、歐幾里得距離的、圖的等。由於圖的Steiner最小樹問題套用最為廣泛。
Steiner最小樹問題
Steiner最小樹問題最早被作為一個數學問題提出，是經典的組合最佳化問題。Steiner最小樹問題經歷了較長時間的發展，最終才形成完整的定義。早在1634年，法國數學家Fermat提出這樣一個問題:假設在平面上有a,b,。三個點，怎樣尋找第四個點P，使得點P到點a,b,c的距離之和最小。這個問題後來被稱為Fermat問題。
19世紀初，瑞士數學家Steiner將Fermat問題推廣為:假設在平面上有a1，a2,a3……an這n(n > 3)個點，怎樣尋找一個點P，使得點P到這n個點的距離之和最小。1909年，德國數學家Weber首次把該問題推廣套用到工廠選址問題中。假設某地有若干個倉庫，想要建造一個工廠，對每個倉庫賦一個權值用來表示該倉庫的影響因素。如何選擇廠址，使得每個倉庫的權值乘以倉庫到工廠的距離的總和最小。
1941年，Courant和Robbins在《什麼是數學》一書中對Fermat問題進行了一種更有意義的推廣:假設在平面上有a1，a2,a3……an這n,(n > 3)個點，怎樣尋找另外的若干個點，使得原有的n個點與後來加入的點組成的網路的總邊長最小。他們把這個問題稱為Steiner樹問題，並給出了一些基本性質。
在網路通信中，有一些網路套用要求數據從源節點出發，最終被多個目標節點接收，這就是多播路由問題〔細。解決多播路由問題的方法有多種，最簡單常用的方法是求解包含源節點和所有目標節點的最小生成樹。但是在許多情況下，另外加入幾個節點，得到的最小生成樹的總邊長有可能會更小，這種思想就來源於Steiner最小樹問題。
分類
Steiner最小樹問題可以分為垂直S teiner最小樹問題、歐氏S teiner最小樹問題、圖的S teiner最小樹問題，下面分別進行介紹。
垂直Steiner最小樹問題
假設在平面上有一個節點集P包含n個給定的節點，尋找一棵覆蓋節點集P中所有節點的樹T，使得樹T的總邊長儘可能的小。節點pi和pj之間的邊長用它們的曼哈頓距離(Manhattan Distance)來表示。樹T肯定包含節點集P中的所有點，也有可能包含其他的一些點，把這些後來添加的節點稱為S teiner點。總邊長最小的樹T稱為垂直Steiner最小樹。由於使用曼哈頓距離來計算，所以節點之間的邊為直線或者是折線，所有的Steiner點一定在經過樹T的水平線和垂直線的交點上。
歐氏Steiner最小樹問題
在平面上給定一個節點集合V，尋找另外的一個節點集合S，使得節點集合V∪S的最小生成樹T的總長度最小。節點vi和sj之間的邊長用它們的歐氏距離來表示。把最小生成樹T稱為歐氏Steiner最小樹。
圖的Steiner最小樹問題
圖的Steiner最小樹問題是求圖中連線給定頂點最小樹長的問題，最早是在1971年由Hakimi和Levin提出,1972年Karp證明了在一般情況下，在多項式時間內不可能得到最優解，該問題是一個NP一完全問題。
