Post date: Dec 05, 2010 5:10:54 PM
Mam pytanie nt. zadania znajdowania maksymalnego zbioru niezależnego - poniewaz jest to problem NP-zupelny, w celu uzyskania rozwiazania w
sensownym czasie konieczne jest wykorzystanie algorytmu aproksymacyjnego. I tu moje pytanie - czy narzucona jest jakas konkretna jego implementacja,
czy tez mozna wykorzystac dowolny dostepny algorytm? Pytanie to dotyczy w
zasadzie rowniez dwoch pozostalych implementowanych algorytmow, ale w
zasadzie o ile tam znane sa algorytmy podajace dokladny wynik, wybor konkretnego algorytmu w przypadku maksymalnego zbioru niezaleznego rzutuje
na jakosc znalezionego rozwiazania.
Myślę, że wszystkie 10-12 osób, które chodzą na wykład, potrafi odpowiedzieć na to pytanie ;-) Problem znalezienia maksymalnego zbioru niezależnego nie jest NP-zupełny. Znajdowanie największego zbioru niezależnego owszem. Przypominam, że słowo "maksymalny" jest tu użyte w odniesieniu do zbioru wierzchołków a nie ich liczby.