圖的steiner最小樹問題及其求解

摘要:斯坦納樹問題是組合優化學科中的一個問題。屬于NP-難問題，即無法在多項式時間內得到最優解。本文主要討論了圖的steiner最小樹問題，并給出了近似算法，該算法是在破圈法的基礎上進行了改進，并且引用了agent的思想。最后對算法進行了分析。

關鍵詞:Steiner最小樹 NP-難題 破圈法

中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2009)25-7312-02

Graphical Steiner Minimum Tree Problem and Solusion

YANG Ling-yun

(College of Computer and Information Engineering， Henan University， Kaifeng 475001，China)

Abstract: Steiner tree problem is one of the subject of combinatorial optimization problem. It belongs to NP-hard problems that cann’t find the optimal solution in polynomial time. This article discusses the minimum steiner tree problem in graphs， and gives the approximate algorithm， which is improved on loop damage method， and quoted the agent's thinking. Finally， an analysis of the algorithm.

Key words: steiner minimum tree; NP-hard problem; loop damage method

現實生活中經常要求解決這樣的問題，即將若干給定點相連并使連線的總長最短。即最小生成樹問題(Minimum Spanning Tree—MST)。最小生成樹問題是運籌學、組合優化中的常見問題，即尋找一棵連接給定點并使樹的總長度最短的生成樹.若要求解n個點的最小生成樹，一般我們首先想到的是求連接這n個點的最小生成樹，擴展我們的思維，相象如果不拘泥于這n個點，我們再加入一些新點，是否會使我們的最小生成樹更優呢?事實證明，如果不拘泥于這n個點，而引入除這n個點之外的另外幾個點的話，則有可能使連接各區域的通信線路的總長更短。這是Steiner最小樹問題的來源。

1 問題描述

圖的Steiner最小樹(Graphical Steiner Minimum Tree，簡記GSMT)問題由Hakimi和Levin于1971年首次提出 。其定義為:給定無向圖G=(V，E)，其中V為點集，E為邊集，邊的權值(大于0)代表費用函數，假如現在有點集P?哿V，點集S?哿V，現在要求在網絡中尋找一棵包含點集P中所有點的子樹T，使得到的樹T的費用最小。稱T為圖G關于P的steiner樹，不屬于P的點稱為steiner點。這里要注意的一點，生成的steiner樹的任steiner點的度都應該大于等于2。

在實際中有廣泛的應用，例如，布置天然氣管道時，當氣源位置和用戶的地理位置確定后，如何鋪設管道使得管網布局最優問題。網絡的有線通訊問題與通訊站點數量及其相互離密切相關，通訊費用與線路長度成正比，因此有關如何布線以使整個網絡達到連通要求且線路最短的問題具有重要意義。通過增加“虛設”站點構造出Steiner最小樹的方法能夠有效解決這個問題。超大規模集成電路設計，交通線路規劃，車輛調度與編組等都屬于steiner最小樹問題。

眾所周知，Steiner樹問題是NP-難的，除非P=NP，否則Steiner樹問題沒有多項式時間的算法。那么當輸入規模很大時，我們就不可能在多項式時間內找到它的精確最優解。因此，我們開始致力于找到一個好的近似算法，給出好的近似解。

最小生成樹是連接S點集中所有點的最小長度的樹，它沒有向給定的點集中插入任何額外的點，可以在O(㏒n)時間內構造完成，并且是SMT的一個很好的近似。圖的Steiner最小樹的Steiner比為1/2。

2 算法思想

尋求連通圖支撐樹的方法，任取一個圈，從圈中去掉一邊，對余下的圖重復這個步驟，直到不含圈時為止，即得到一個支撐樹，稱這種方法為破圈法 。

Agent是在一定環境下能靈活主動地完成某個任務的實體，它具有自主性、學習性、交互性 。 Agent的自主性是指能為將來目標預先行動，學習性是指能夠將經驗轉變為自己的知識，交互性是指不同Agent之間或者Agent與環境之間能夠進行信息交流。

令集合P為給定點集，S為待選點集(即steiner點，記為s-點)，集合V=P∪S，頂點Vi與Vj間的距離記為d(vi，vj)。初始狀態為給定的原點集P及P內頂點間的連接關系(邊長，邊集)，若存在邊e(vi，vj)，則兩點間的距離d(vi，vj)即為此邊的長度，若兩點間不存在邊則給此邊一個高的懲罰值。若對S中一個點Vs，存在邊e(Vs， Vj)，e(Vs， Vi)，Vi， Vj∈P，且d(Vs， Vi)+d(Vs， Vj)

對s-點的選擇是從S集合中隨機選擇。

3 求解步驟

定義一個agent類，設置若干個agent對象，初始狀態V=P，計算P中任意兩個原點Pi與Pj之間的最短距離，記為Old_D(Pi，Pj)。最多添加的s-點總數為k。當前每個agent.hyp集合中可以包含的s-點總數的上界為add_number(0≤add_num≤m， 1≤m≤k)，初始值為1。

Class agent {

int Number_of_steiner; //當前已經添加s-點的個數

item hyp;// 保存其設想添加的s-點集合

float sum_difference;

bool activity; //agent的狀態

};

Initialize agent:每個agent.hyp初始化為空集，s-點的個數為0，Sum_Difference為0。

Repeat {

Test(){

if add>k

add=1;

for i=1 to agentNumber {

add=add_number-agent[i].Number_of_steiner;// 即目前已添加的s-點總數與當前要求達到的最大的s-點總數之間的差距

V=V+hyp;

If (add>0) { //if 1

從集合S-{hyp}中任意選取add個s-點進行有關公式1的判斷;

將使得公式1為真的點集temp加入集合V;

重新計算集合V中任意兩個原點Pi與Pj之間的最短距離，記為New_D(Pi，Pj);

計算，記為sum_Difference。

If sum_Difference>0{

agent.activity=true;

去除temp中度為1的點;

hyp=hyp+temp;

修改Number_of_steiner的值;

}

}//end of if 1

} //end of Test

Diffuse(){

for every active agent A {//suppose A

select random agent B; //suppose B

if (agentB.activity = =true) {//if 2

if(agentA.number_of_steiner = =agentB. number_of_steiner) {//if 3

if (agentA.hyp = =agentB.hyp) {

agentB.hyp置為空集;

agentB.activity=1;

}

if(agentA.sum_difference

A 復制 B的hyp及Steiner點數;

if(agentA.sum_difference>agentB.sum_difference)

B 復制 A的hyp及Steiner點數;

}//end of if 3

}//end of if 2

} end of Diffuse

if add_number

add_number++;

else{

保存sum_difference最大的集合及狀態;

Break;}

}

4 算法分析

如一家煤氣公司要給多個城鎮提供氣源，如圖1所示，現假定要給V1，V2，V3提供氣源。其余的點為steiner點。為了尋求最優解，煤氣公司現派若干人員去考查鋪設管道的具體方案。最后采用較優的方案。

通過多次實驗，得到的樹長最優值為8，如圖2所示。樹長最差值為10，樹長平均值為8.924。

5 結束語

破圈法的時間復雜度為O(n3)，假如設agent的個數為m，則本算法的時間復雜度為O(mn3)。本算法同時還涉及到設置多少個agent才合適的問題，設置的太多則影響算法的時間復雜度，相反則可能得不到預期的結果。agent的個數很難確定，所以算法還需改進。

參考文獻:

[1] Hakimi SL1Steiner problem in graphs and its imp lications1Networks，1971，1: 113-133.

[2] Kou L， Markowsky G，Berman L1 A fast algorithm for Steiner trees1 Acta Info， 1981，15:141-145.

[3] 《運籌學》教材編寫組.運籌學[M].3版.北京:清華大學出版社，2005:258.

[4] 蔡自興，徐光祐.人工智能及其應用[M].3版.北京:清華大學出版社，2007: 315.