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
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:
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.
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)'. –