Algorytm wyszukiwania minimalnego drzewa opinającego wybranych wierzchołków

Question

Można użyć algorytmu Prim lub algorytmu Kruskala, aby znaleźć minimalne drzewo/wykres opinający zbiór wierzchołków/węzłów i krawędzi/linków. To, czego chcę, to algorytm, który znajduje minimalny wykres spinający tej kolekcji, ale wynikowy wykres musi zawierać tylko arbitralnie wybrane węzły, zamiast wszystkich węzłów. Jest w porządku, jeśli wynikowy wykres zawiera więcej węzłów niż te, które są potrzebne.

Czy istnieje taki algorytm? Być może można po prostu użyć algorytmu Prim (lub Kruskala) po zmodyfikowaniu wykresu tak, aby zawierał tylko potrzebne węzły? Ale nie jestem pewien, jak zmodyfikować wykres, aby to zrobić, zachowując połączenie.

Załóżmy, że mamy w kształcie diamentu początkowy wykresu (z kosztami połączeń w nawiasach):

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

Teraz możemy dowolnie zdecydować, że tylko węzły A i D są potrzebne. Gdybyśmy zaczęli na A, nadal chcielibyśmy, aby zajęło lewą ścieżkę, ponieważ ((2 + 2) < (1 + 5)).

Załóżmy, że modyfikowanie wykres nieco:

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

Jeśli uznać, że tylko węzły A, D i E są potrzebne, wiemy, że tor przy minimalnym koszcie niekoniecznie jest jednym z najmniejszą spinki do mankietów. Biorąc A - B - D i A - C - E kosztuje 7, ale A - C - D i C - E kosztuje 8.

Answer 1

Co chcesz znaleźć to dyskretne Steiner tree. Gdy nie wszystkie wierzchołki na wykresie są obowiązkowe, ale drzewo może dzielić się na opcjonalnych wierzchołkach, problem jest NP-trudny.

Wikipedia mówi (link powyżej) o tym problemie: uważa się, że arbitralnie dobre współczynniki aproksymacyjne nie mogą być generalnie osiągnięte w czasie wielomianowym. Istnieje algorytm wielomianowy, który znajduje przybliżenie 1.39 minimalnego drzewa Steinera.