Seçilen köşelerin minimum genişleme ağacını bulmak için algoritma

Question

Kökler/düğümler ve kenarlar/bağlantılar koleksiyonunun minimum genişleyen ağacını/grafiğini bulmak için Prim algoritması veya Kruskal algoritması kullanılabilir. Bununla birlikte, istediğim, bu koleksiyonun minimum genişleme grafiğini bulabilen bir algoritmadır, ancak sonuçta ortaya çıkan grafik, yalnızca tüm düğümler yerine isteğe bağlı olarak seçilen düğümleri içermelidir. Ortaya çıkan grafik, ihtiyaç duyulanlardan daha fazla düğüm içeriyorsa tamamdır.

Böyle bir algoritma var mı? Belki de sadece gerekli düğümleri içerecek şekilde grafiğini değiştirdikten sonra Prim'lerin (veya Kruskal'ın) algoritması kullanılabilir mi? Ancak, bağlılığını korurken bunu yapmak için grafiğin nasıl değiştirileceğinden emin değilim. Biz keyfi sadece A ve düğüm noktalarını D ihtiyaç olduğunu karar, Şimdi

A 
(2)/ \(1) 
    B C 
(2)\ /(5) 
    D 

: Örneğin

, biz (parantez içinde bağlantıların maliyetleri ile) başlangıç ​​grafiği şeklinde bir elmas olduğunu varsayalım. Eğer A'da başlamış olsaydık, hala sol yolunu almak isterdik, çünkü ((2 + 2) < (1 + 5)).

A 
(2)/ \(1) (2) 
    B C ------E 
(2)\ /(5) 
    D 

A; D düğümleri ve E yalnızca gerekli olduğuna karar durumunda, en az maliyetle yolunu mutlaka en az bir kez olmadığını fark:

biz biraz grafiği değiştirmek ki bağlantıları. A - B - D ve A - C - E maliyetlerinin 7, ancak A - C - D ve C - E maliyetlerinin alınması 8

Answer 1

Bulmak istediğiniz şey bir ayrık Steiner tree. Grafikteki tüm köşeler zorunlu değilse de, ağacın isteğe bağlı köşe noktalarına bölünmesine izin verilir, sorun NP-zordur. Vikipedi, bu sorunun şu (üstte) olduğunu belirtmektedir: genel olarak keyfi iyi yaklaşım oranlarının polinom zamanında elde edilemeyeceğine inanılmaktadır. Minimum bir Steiner ağacının 1.39 değerini hesaplayan bir polinom-zaman algoritması vardır.