Inserire un algoritmo per il problema successivo: Dato l'insieme S di n punti nel piano 2D, un punto (x1, y1) domina un altro punto (x2, y2) se x1> x2 e y1> y2. Trova il più grande insieme di punti M tale che M sia un sottoinsieme di S e nessun punto di M sia dominato da un altro punto di S.Algoritmo per il massimo set non dominato
risposta
Ordina tutti i punti aumentando le coordinate x. Se due punti hanno la stessa coordinata x, ordinali diminuendo le coordinate y. Ora, si può dimostrare che un sottoinsieme di punti non è dominato se e solo se le loro coordinate y non sono in aumento nella nostra sequenza ordinata, cioè ogni coordinata y è inferiore o uguale alla precedente nella sottosequenza.
Quindi l'algoritmo sarebbe:
- Ordinare i punti come descritto sopra. Ora: O (n * logn).
- Trova la più lunga sottosequenza non crescente di coordinate y. Ora: O (n * logn). Questo può essere fatto adattando l'algoritmo per trovare lo longest increasing subsequence.
Ciò fornisce il più grande set possibile in O (n * logn).
Credo che il # 2 dovrebbe chiedere la "sottosequenza non crescente più lunga", non è così? –
@ JanDvorak Hai ragione, grazie. – interjay
Il vero problema richiede che nessun punto di M sia dominato da un altro punto in S. – user1256960
C'è un algoritmo di divisione e conquista che esegue questo nel tempo O (n * logn).
Dividiamo i punti in due metà, di dimensione n/2 ciascuno, in base alle loro coordinate x. Troviamo il punto non dominato impostato in entrambe le metà. Devi osservare che tutti i punti non dominati trovati nella metà destra esisteranno nella nostra lista finale.
Con questa osservazione possiamo scrivere il nostro passo di combinazione, rimuovere tutti i punti non dominati nella metà sinistra che sono y coordinati meno della massima coordinata y del punto nell'insieme non dominato nella destra metà. Abbiamo il set di punti non dominati.
Algoritmo:
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
Equazione per tempo:
T(n) = 2T(n/2) + O(n) which is O(n*logn)
si può migliorare ulteriormente per O (n * Logh) dove H è il numero di punti non dominati , richiede più informazioni sul problema ed è una buona estensione su cui puoi lavorare.
- 1. Algoritmo set indipendente massimo
- 2. Algoritmo per determinare il massimo divertimento
- 3. Algoritmo per trovare il percorso che minimizza il peso massimo tra due nodi
- 4. Come trovare il valore massimo del set di variabili
- 5. bisogno di assistenza con algoritmo per trovare il percorso massimo in un DAG
- 6. Come è chiamato questo algoritmo, per trovare il percorso massimo su un grafico Aciclico Diretto?
- 7. Algoritmo per simulare il daltonismo?
- 8. Algoritmo per il completamento automatico?
- 9. Algoritmo: Rimuovere il minor numero di elementi possibili da un set per far valere nessun sottoinsiemi
- 10. Binario Ricerca per la lista, ma non per il set
- 11. Qual è il ritardo massimo per setInterval?
- 12. Algoritmo per raggruppare un'espressione per massimizzarne il valore
- 13. Impostazione massimo di connessioni per il web
- 14. Algoritmo per trovare il percorso in un albero non indirizzato
- 15. Algoritmo per determinare il tasso di cambio
- 16. Algoritmo di bilanciamento per uniformare le differenze?
- 17. consiglio algoritmo per trovare articoli massimo entro un periodo di tempo
- 18. Qual è il limite massimo per group_concat_max_len in MySQL?
- 19. Miglior algoritmo per il matchmaking per una classifica di crowdsourcing?
- 20. Algoritmo per trovare sottoinsiemi comuni
- 21. algoritmo per trovare il più grande calo in un array
- 22. Algoritmo per il raggruppamento basato sulle preferenze
- 23. COLLATION 'utf8_general_ci' non è valido per il personaggio SET 'latin1'
- 24. Set HtmlFieldPrefix per id, ma non il nome
- 25. Sintassi non valida per il set di operazioni
- 26. Clips massimo e massimo
- 27. Trovare il valore massimo massimo di scrollTop su un div?
- 28. Algoritmo per il calcolo del colore inverso
- 29. algoritmo per il confronto di immagini
- 30. Algoritmo per il calcolo del coefficiente binomiale
Un bel piccolo problema, grazie. –
user1256960, ho modificato la domanda aggiungendo i nomi dei set S e M. Nell'ultima frase, cambia "un altro punto di M" in "qualsiasi punto di S" se questo è ciò che intendi. (La domanda originale era ambigua se gli altri punti sono in S o in M.) –
Questo è fondamentalmente un problema di set indipendente massimo su un grafico vincolato. Il problema generale è NP-completo, quindi non puoi andare peggio di 'O (2^n)'. –