Ana içeriğe atla
OR Araçları

Araçlar / Graf & Rota

Steiner Ağacı Çözücü (KMB 2-Yaklaşımı)

Yönsüz ağırlıklı bir ağda terminal alt kümesini birbirine bağlayan en az toplam ağırlıklı ağacı bul. Ara düğümler (Steiner noktaları) isteğe bağlı olarak ağaca dahil edilebilir. Problem NP-zor; aracımız Kou-Markowsky-Berman (KMB) 1981 algoritmasını kullanır — yaklaşım faktörü 2. Rehbere git →

Kenarlar

Kenarlar yönsüz; (u, v) ile (v, u) aynı. Paralel kenarda en küçük ağırlık seçilir; ağırlık ≥ 0 olmalı (Dijkstra varsayımı). En fazla 200 düğüm, 1000 kenar, 30 terminal.

Terminaller

Bağlanması zorunlu düğüm adları (boşluk, virgül veya tab ile ayır). Diğer düğümler isteğe bağlı Steiner noktası olarak ağaca alınabilir.

Konuyu derinleştir

Steiner ağacı, NP-zorluk ve KMB 2-yaklaşımı

MST ile farkı, problemin NP-zor olmasının kombinatoryel kaynağı, metrik kapanış, KMB'nin altı adımı, yaklaşım faktörü 2'nin ispatı, VLSI / multicast / filogenetik uygulamaları ve aracımızdaki örnekler.

Rehberi oku →