Znajdowanie największego podzbioru elementów zależnych względem siebie

0

Cześć,

wiem, że temat dużo nie mówi, ale nie wiem jak to nazwać.

Mam np taki problem.
Dany jest zbiór liczb. Znajdź największy podzbiór(o największej ilości liczb) liczb względnie pierwszych w tym zbiorze(http://pl.wikipedia.org/wiki/Liczby_wzgl%C4%99dnie_pierwsze).

Czy jest jakiś ogólny algorytm na taki problem?

2

Nie do końca rozumiem pytania (zdefiniuj "zależnych") - na przykład ja bym powiedział że liczby względnie pierwsze są właśnie wobec siebie "niezależne".

Jeśli rozmawiamy o najbardziej ogólnym przypadku, gdzie zależność to dowolna (symetryczna) relacja między dwoma elementami, to możemy zamodelować ten problem jako graf.
Wierzchołki w grafie to elementy z Twojego zbioru, a dwa wierzchołki łączy krawędź wtedy kiedy występuje między nimi ta dowolna relacja. Szukamy największej takiej grupy wierzchołków G, że każde dwa wierzchołki z G są połączone krawędzią.
Na tak postawiony problem jest dość klasyczny algorytm grafowy...
http://en.wikipedia.org/wiki/Clique_problem
...niestety NP zupełny.

W trywialny sposób można przeprowadzić redukcje w drugą stronę (czyli z dowolnego zbioru elementów z ustaloną relacją na graf), więc o ile czegoś nie przeoczyłem, wynika z tego że tak postawiony ogólny problem jest NP zupełny.

Wiesz coś może więcej o tej relacji 'zależności' dla której chcesz wykonywać algorytm (np. gdyby była przechodnia, ale to nie pasuje do podanego przykładu liczb względnie pierwszych)? Może da się jednak w bardziej specyficznym przypadku coś zrobić.

(*NP zupełny ~= nie do zrobienia szybko, o ile nie zajdzie BARDZO poważny przełom w informatyce)

0

Tak dobrze zrozumiałeś co miałem na myśli mówiąc zależne :)

Czyli jeżeli dobrze rozumiem to ten problem to problem znajdowania największej kliki w grafie. I jest on NP-Zupełny czyli nie da rady go rozwiązać w czasie wielomianowym(czyli np. n3) tylko przynajmniej wykładniczym( np. 2n) tak?

//Nie wiem czy czegoś nie pokręciłem z nazwami tych czasów

1 użytkowników online, w tym zalogowanych: 0, gości: 1