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

Odpowiedz Nowy wątek
2015-01-17 19:05
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?

Pozostało 580 znaków

2015-01-17 19:38
msm
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)

edytowany 5x, ostatnio: msm, 2015-01-17 19:44

Pozostało 580 znaków

2015-01-17 21:33
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

edytowany 1x, ostatnio: stryku, 2015-01-17 21:33
Jeśli szukasz n takich wartości że każda spośród nich jest niezależna od wszystkich innych w zbiorze i zależność nie ma jakichś dodatkowych własności -> niestety tak. Odnośnie reszty posta to dokładnie tak (chociaż czy /na pewno/ się nie da rozwiązać to problem otwarty, ale na razie się nie da i raczej się to pewnie nie zmieni). - msm 2015-01-17 22:16
Ok, a tylko się upewnię. Np. taki problem: "Dana jest tablica liczb. Znajdź w tej tablicy największy możliwy podzbiór liczb względnie pierwszych". Czyli tworzę graf(macierz np.) wierzchołkami będą liczby, a krawędzią to czy dwie liczby są względnie pierwsze. I szukam maksymalnej kliki. To jest to NP-Zupełne jeżeli dobrze rozumiem. - stryku 2015-01-17 22:23
Poczytałem trochę i ogarnąłem, że to jednak nie to samo. Dzięki za pomoc :) - stryku 2015-01-18 01:43

Pozostało 580 znaków

2015-01-17 21:40
0

http://www.ibspan.waw.pl/Sesj[...]ozdawcza_2004/sep/sep_int.pdf


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Pewnie powinienem, ale nie rozumiem jak to ma się do tego tematu? - stryku 2015-01-17 21:55
ja też nie. link bez opisu, problem nie jest powiązany w sposób oczywisty. hipergrafy? jak je wyliczyć i co ma być krawędziami? - Wibowit 2015-01-17 21:59

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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