K-minimum kapsayan ağaç - K-minimum spanning tree

Yönlendirilmemiş bir grafik örneği uç maliyetlerle
4-MST
6-MST

kMinimum yayılma ağacı problemi, okudu teorik bilgisayar bilimi, tam olarak aşağıdaki değerlere sahip minimum maliyetli bir ağaç ister k köşeler ve daha büyük bir grafiğin bir alt grafiğini oluşturur. Aynı zamanda k-MST veya kenar ağırlıklı kkardinalite ağacı. Bu ağacı bulmak NP-zor, ancak bir sabit dahilinde tahmin edilebilir yaklaşım oranı içinde polinom zamanı.

Sorun bildirimi

Sorunun girdisi bir yönsüz grafik kenarlarında ağırlıklar ve bir numara k. Çıktı bir ağaçtır k köşeler ve k − 1 çıktı ağacının tüm kenarları giriş grafiğine ait olan kenarlar. Çıktının maliyeti, kenarlarının ağırlıklarının toplamıdır ve amaç, minimum maliyeti olan ağacı bulmaktır. Sorun şu şekilde formüle edildi: Lozovanu ve Zelikovsky (1993)[1] ve tarafından Ravi vd. (1996).

Ravi vd. grafik probleminin özel bir durumu olarak görülebilecek problemin geometrik bir versiyonu da düşünülmüştür. k-Minimum yayılan ağaç problemi, girdi düzlemdeki bir dizi noktadır. Yine, çıktı bir ağaç olmalıdır. k toplamı en aza indirerek, noktaların köşeleri olarak Öklid uzunluğu kenarlarından. Yani bu bir grafik kbir üzerinde minimum yayılan ağaç tam grafik Ağırlık olarak Öklid mesafeleri ile.[2]

Hesaplama karmaşıklığı

Ne zaman k sabit bir sabittir, k-Minimum yayılan ağaç sorunu çözülebilir polinom zamanı tarafından kaba kuvvet arama hepsini deneyen algoritma k-tuples of vertices.Ancak değişken için k, k-Minimum yayılma ağacı probleminin olduğu gösterilmiştir NP-zor tarafından indirgeme -den Steiner ağacı sorun.[1][2]

Azaltma, Steiner ağaç probleminin bir örneğini girdi olarak alır: köşelerinin bir alt kümesinin terminal olarak seçildiği ağırlıklı bir grafik. Steiner ağaç probleminin amacı, bu terminalleri, ağırlığı olabildiğince küçük olan bir ağaca bağlamaktır. Bu sorunu bir örneğine dönüştürmek için kMinimum yayılan ağaç problemi, Ravi vd. (1996) her bir terminale çok sayıda sıfır ağırlıklı kenarlardan oluşan bir ağaç bağlayın t ağaç başına köşe sayısı. (Bir grafik için n köşeler ve r terminaller, kullanıyorlar t = n − r − 1 ağaç başına tepe noktaları eklendi.) Daha sonra, k-bu artırılmış grafikte minimum yayılma ağacı k = rt. Bu kadar çok köşeyi bir k- yayılan ağaç, eklenen ağaçlardan biri eksik olsa bile yeterli köşe kalmadığından, eklenen her ağaçtan en az bir tepe kullanmaktır. Ancak, bu seçim için kiçin mümkündür k- tüm terminalleri bağlamak için gereken orijinal grafiğin yalnızca birkaç kenarını içerecek şekilde genişleyen ağaç. bu yüzden kToplam ağaç boyutunu yeterince büyütmek için, eklenen ağaçların yeterli sıfır ağırlıklı kenarları ile optimum Steiner ağacını birleştirerek minimum yayılma ağacı oluşturulmalıdır.[2]

Kenar ağırlıkları kümeye ait olan bir grafik için bile {1, 2, 3}, optimum çözüm değerinin belirli bir eşikten düşük olup olmadığının test edilmesi NP tamamlandı. NP-tamamlanmış olarak kalır düzlemsel grafikler. Problemin geometrik versiyonu da NP-zordur, ancak karekök toplamlarını karşılaştırmanın zorluğundan dolayı NP'ye ait olduğu bilinmemektedir; bunun yerine, indirgenebilen sorunlar sınıfında yatmaktadır. gerçeklerin varoluş teorisi.[2]

k-minimum yayılan ağaç bulunabilir polinom zamanı sınırlı grafikler için ağaç genişliği ve yalnızca iki farklı kenar ağırlığına sahip grafikler için.[2]

Yaklaşık algoritmalar

En uygun çözümü bulmanın yüksek hesaplama karmaşıklığı nedeniyle k-minimum yayılma ağacı, sorunla ilgili araştırmaların çoğu bunun yerine yaklaşım algoritmaları sorun için. Bu tür algoritmaların amacı, küçük bir polinom zamanda yaklaşık bir çözüm bulmaktır. yaklaşım oranı. Yaklaşım oranı, hesaplanan çözüm uzunluğunun, bu oranı en üst düzeye çıkaran en kötü durum örneği için optimum uzunluğa oranı olarak tanımlanır. Çünkü NP-sertlik azaltımı k-Minimum yayılma ağacı problemi tüm çözümlerin ağırlığını korur, aynı zamanda yaklaşım sertliği problemin. Özellikle, Steiner ağacı problemi NP-zordur çünkü bir yaklaşım oranı 96 / 95'ten daha iyi,[3] aynısı için de geçerlidir kMinimum yayılan ağaç problemi.

Genel problem için bilinen en iyi yaklaşım, yaklaşık 2 oranına ulaşır ve Garg (2005).[4] Bu yaklaşım, büyük ölçüde ilk-ikili şemasına dayanır. Goemans ve Williamson (1992).[5]Giriş, aşağıdaki noktalardan oluştuğunda Öklid düzlemi (herhangi ikisi ağaçta mesafelerine eşit maliyetle bağlanabilir) bir polinom zaman yaklaşım şeması tarafından tasarlanmış Arora (1998).[6]

Referanslar

  1. ^ a b Lozovanu, D .; Zelikovsky, A. (1993), "Minimal ve sınırlı ağaç sorunları", Tezele Congresului XVIII al Academiei Romano-Americane, Kişniev, s. 25. Alıntı yaptığı gibi Ravi vd. (1996).
  2. ^ a b c d e Ravi, R .; Sundaram, R .; Marathe, M .; Rosenkrantz, D .; Ravi, S. (1996), "Ağaçları kısa veya küçük kapsayan", SIAM Journal on Discrete Mathematics, 9 (2): 178–200, arXiv:math / 9409222, doi:10.1137 / S0895480194266331, S2CID  8253322. Bu çalışmanın bir ön versiyonu daha önce 5. Yıllık ACM-SIAM Ayrık Algoritmalar Sempozyumu, 1994, s. 546-555'te sunulmuştur.
  3. ^ Chlebík, Miroslav; Chlebíková, Janka (2008), "Grafiklerdeki Steiner ağacı sorunu: Yaklaşımsızlık sonuçları", Teorik Bilgisayar Bilimleri, 406 (3): 207–214, doi:10.1016 / j.tcs.2008.06.046.
  4. ^ Garg, Naveen (2005), "Bir epsilon kaydetme: grafiklerdeki k-MST problemi için bir 2-yaklaşım", Hesaplama Teorisi üzerine 37. Yıllık ACM Sempozyumu Bildirileri, s. 396–402, doi:10.1145/1060590.1060650, S2CID  17089806..
  5. ^ Goemans, M.; Williamson, P. (1992), "Kısıtlı orman problemleri için genel bir yaklaşım tekniği", Bilgi İşlem Üzerine SIAM Dergisi, 24 (2): 296–317, CiteSeerX  10.1.1.55.7342, doi:10.1137 / S0097539793242618, S2CID  1796896.
  6. ^ Arora, Sanjeev (1998), "Öklid gezici satıcı için polinom zaman yaklaşım şemaları ve diğer geometrik problemler", ACM Dergisi, 45 (5): 753–782, doi:10.1145/290179.290180, S2CID  3023351.

Dış bağlantılar