FInd algorytm dla następnego problemu: Biorąc pod uwagę zestaw S n punktów w płaszczyźnie 2D, punkt (x1, y1) dominuje inny punkt (x2, y2), jeśli x1> x2 i y1> y2. Znajdź największy zestaw punktów M taki, że M jest podzbiorem S i żaden punkt M nie jest zdominowany przez inny punkt S.Algorytm dla maksymalnego zestawu zdominowanego
Odpowiedz
Sortuj wszystkie punkty, zwiększając współrzędne x. Jeśli dwa punkty mają tę samą współrzędną x, posortuj je, zmniejszając współrzędne y. Teraz można pokazać, że podzbiór punktów jest zdominowany wtedy i tylko wtedy, gdy ich współrzędne y są nie rosnące w naszej posortowanej sekwencji, co oznacza, że każda współrzędna y jest mniejsza lub równa poprzedniej w podciągnięciu.
Więc algorytm będzie:
- Uporządkuj punkty jak opisano powyżej. Czas: O (n * logn).
- Znajdź najdłuższy nie zwiększający się podciąg współrzędnych y. Czas: O (n * logn). Można to zrobić, dostosowując algorytm do znajdowania longest increasing subsequence.
Daje to największy możliwy zestaw w O (n * logn).
Uważam, że # 2 powinien prosić o "najdłuższy nierozszerzający się podciąg", nieprawdaż? –
@JanDvorak Masz rację, dziękuję. – interjay
Rzeczywisty problem zadaje pytanie, czy żaden punkt M nie jest zdominowany przez inny punkt w S. – user1256960
Istnieje algorytm dziel i podbijaj, który wykonuje to w czasie O (n * logn).
Podzielmy punkty na dwie połówki, o wielkości n/2 każda, na podstawie ich współrzędnych x. W obu połowach znajdujemy niedominowany punkt. Musisz zauważyć, że wszystkie niedominowane punkty znalezione w prawej połowie pojawią się na naszej ostatecznej liście.
Dzięki tej obserwacji możemy napisać nasz krok łączenia, usunąć wszystkie niedominowane punkty w lewej połowie, które mają współrzędną y mniejszą niż najwyższa współrzędna y punktu w niedominowanym zbiorze po prawej stronie pół. Mamy zestaw niedominowanych punktów.
Algorytm:
Find the median along x axis - O(n) time
Find non-dominated points in the right half - T(n/2)
Find non-dominated points in the right half - T(n/2)
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points
Równanie czasu:
T(n) = 2T(n/2) + O(n) which is O(n*logn)
Można to poprawić dodatkowo O (N * logH), w którym H oznacza liczbę nie zdominowanych punktów , wymaga więcej wglądu w problem i jest dobrym rozszerzeniem, nad którym możesz popracować.
- 1. Dlaczego algorytm chciwy nie znajduje maksymalnego niezależnego zestawu wykresów?
- 2. Zwiększanie maksymalnego rozmiaru zestawu wyników JvisualVM OQL
- 3. efekt uboczny zwiększania maksymalnego rozmiaru i maksymalnego rozmiaru sterty
- 4. ElasticSearch - Określanie maksymalnego rozmiaru odłamka
- 5. Efektywny algorytm do przekształcania zestawu znaków w nfa/dfa
- 6. Algorytm tfidf dla Pythona
- 7. Algorytm dla div kerningu
- 8. Czy istnieje algorytm wielomianowy do znalezienia maksymalnego ważonego idealnego dopasowania na ogólnym wykresie?
- 9. Zamówienie według warunku maksymalnego dopasuj
- 10. Właściwy sposób aktualizowania rekordów w wzorcu MVVM dla maksymalnego skuteczności
- 11. TTL dla zestawu elementów
- 12. Maksymalny niezależny algorytm setu
- 13. Najłatwiejszy sposób symulacji maksymalnego obciążenia procesora?
- 14. Algorytm różnicowy C# dla tekstu
- 15. Algorytm rekursywny dla czterobarwnego twierdzenia
- 16. Algorytm dla linii łączących prostokąty
- 17. Algorytm wyszukiwania, ale dla funkcji
- 18. Algorytm dla "gładkich" liczb losowych
- 19. Algorytm odnajdywania ścieżek dla pociągów
- 20. Algorytm dla schematu cenowego Fogbugz
- 21. Algorytm podpróbkowania Chroma dla jpeg
- 22. Algorytm dla itertools.combinations w Pythonie
- 23. Najlepszy algorytm kompresji dla XML?
- 24. Java, identyfikator zestawu dla JButton
- 25. Kod zestawu dla sin (x)
- 26. Ikona zestawu Mapbox dla featureLayer
- 27. Niedozwolona składnia dla operacji zestawu
- 28. Algorytm wykrywania kodowania znaków
- 29. Algorytm ustalania wartości szczytowej
- 30. Ogólny algorytm dla rastrowego obrazu wektorowego
Ładny mały problem, dzięki. –
user1256960, Edytowałem pytanie, dodając ustawione nazwy S i M. W ostatnim zdaniu zmień "inny punkt M" na "dowolny punkt S", jeśli o to ci chodzi. (Pierwotne pytanie było niejednoznaczne na temat tego, czy inne punkty są w S, czy w M.) –
Jest to zasadniczo maksymalny niezależny problem związany z ustawionym wykresem. Ogólny problem to NP-zupełny, więc nie można gorzej niż 'O (2^n)'. –