Biorąc pod uwagę wykres G, dlaczego jest następujący algorytm zachłanny nie gwarantowane znaleźć maximum independent set G:Dlaczego algorytm chciwy nie znajduje maksymalnego niezależnego zestawu wykresów?
Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G
S = union(S, {v})
remove v and its neighbors from G
return S
Zastanawiam może ktoś mi pokazać prosty przykład wykres gdzie algorytm ten nie powiedzie?
nie jestem pewien, że to najprostszy przykład, ale tutaj jest jeden, który nie: http://imgur.com/QK3DC
Na pierwszym etapie, można wybrać B, C, D lub F, ponieważ wszystkie one mają stopień 2. Załóżmy, że usuwamy B i jego sąsiadów. To pozostawia F i D z stopniami 1 i E z stopniem 2. Podczas kolejnych dwóch kroków usuwamy F i D i kończymy na ustawionym rozmiarze 3, który jest maksymalny.
Zamiast tego załóżmy, że na pierwszym etapie usunęliśmy C i jego sąsiadów. Pozostawia nam to F, A i E, każdy o rozmiarze równym 2. Przyjmujemy jeden z poniższych, a wykres jest pusty, a nasze rozwiązanie zawiera tylko 2 węzły, co jak widzieliśmy, nie jest maksymalne. .
Dziękuję bardzo! Nie jestem pewien, czy jest to zgodne z zasadami Q & A, ale mam inne pytanie. Załóżmy, że każdy wierzchołek wykresu ma inną liczbę krawędzi wypadków. Czy to założenie wystarczy, aby zachłanny algorytm działał poprawnie? –
Jest to w rzeczywistości niemożliwe (z wyjątkiem zdegenerowanego przypadku z 1 węzła). Łatwo to udowodnić. Załóżmy, że istnieje n węzłów, z których wszystkie mają inny stopień. W największym stopniu węzeł może mieć wartość n-1. Oznacza to, że węzły _must_ mają stopnie {0, 1 ... n-1}. Jednak nie jest możliwe, aby istniał węzeł o stopniu 0 i węzeł o stopniu n-1 (węzeł, który nie jest połączony z żadnym węzłem i węzłem, który jest połączony z każdym węzłem). Dlatego na każdym wykresie z co najmniej 2 węzłami, co najmniej 2 węzły muszą mieć taką samą liczbę krawędzi wypadków. – gms7777
Dziękujemy! Nie myślałem, kiedy napisałem komentarz :) –
Zastanawiam się, jeśli ten algorytm się nie powiedzie, jaki jest właściwy algorytm do rozwiązania problemu? –
@TravelingSalesman Myślę, że możesz znaleźć odpowiedź w tym samym artykule [wikipedia] (http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29#Finding_maximum_independent_sets). Jak widzę, ten chciwy algorytm znajduje niezależny zestaw, a ten zestaw jest stosunkowo duży, więc można go użyć do znalezienia nieoptymalnego rozwiązania. Nie jestem ekspertem, więc proszę mi nie ufać :) –
Jest OK. Dziękuję Ci. –