/ / Znalezienie minimalnej liczby wymaganych "punktów centralnych" - algorytm, wykres, analiza skupień

Znalezienie minimalnej liczby wymaganych "punktów centralnych" - algorytm, wykres, analiza skupień

Mam zestaw "n" węzłów. Funkcja zwraca pewien rodzaj odległości między dwoma węzłami, tak że dist (a, c) może nie być dist (a, b) + dist (b, c). W oparciu o próg łączę niektóre węzły za pomocą krawędzi. Chcę wybrać minimalną liczbę węzłów tak, aby zestaw tych węzłów i ich bezpośrednie krawędzie połączone z sąsiadami obejmowały cały zestaw n węzłów. Czy możliwe jest optymalne rozwiązanie? Pisanie na papierze sprawiło, że myślę, że centralność może pomóc (stopień, bliskość?). Utworzono klastrowanie, ale węzły na tym wykresie nie mają atrybutów. Jak wybrać liczbę min węzłów? Z góry dziękuję

Odpowiedzi:

3 dla odpowiedzi № 1

Chcę wybrać minimalną liczbę węzłów tak, że zestaw te węzły i ich bezpośrednie krawędzie połączone z sąsiadami obejmują cały zestaw n węzłów

To jest Dominujący zestaw.

Ponieważ możemy łatwo zdefiniować d(u,v) = 1 dla wszystkich węzłów, w których (u, v) jest krawędzią, możemy łatwo zmniejszyć pokrycie wierzchołków do twojego problemu.

Od Dominating-Set jest NP-Complete, a powyższe jest redukcją wielomianową, więc to twój problem.

tl; dr: Twoim problemem jest NP-Complete i nie ma znanego skutecznego rozwiązania, aby rozwiązać go optymalnie.