Recentemente ho avuto questo problema su un test: dato un insieme di punti m (tutta l'asse x) e una serie n di linee con endpoint [l, r] (nuovamente sull'asse x), trovare il sottoinsieme minimo di n in modo che tutti i punti siano coperti da una linea. Dimostra che la tua soluzione trova sempre il sottoinsieme minimo.Point coprendo problema
L'algoritmo che ho scritto perché era qualcosa per l'effetto di: (diciamo linee sono memorizzati come array con l'estremità sinistra in posizione 0 e il diritto in posizione 1)
algorithm coverPoints(set[] m, set[][] n):
chosenLines = []
while m is not empty:
minX = min(m)
bestLine = n[0]
for i=1 to length of n:
if n[i][0] <= minX and n[i][1] > bestLine[1] then
bestLine = n[i]
add bestLine to chosenLines
for i=0 to length of m:
if m[i] <= bestLine[1] then delete m[i] from m
return chosenLines
Sono solo non sono sicuro se questo trova sempre la soluzione minima. È un semplice algoritmo avido quindi il mio istinto mi dice che non lo farà, ma uno dei miei amici che è molto più bravo di me dice che per questo problema un algoritmo avido come questo trova sempre la soluzione minima. Per provare la mia trova sempre la soluzione minima, ho fatto una prova molto vaga per contraddizione in cui ho fatto un'ipotesi che probabilmente non è affatto vero. Ho dimenticato esattamente quello che ho fatto.
Se questa non è una soluzione minima, c'è un modo per farlo in meno di qualcosa come O (n!) Tempo?
Grazie
Ho problemi a seguire il tuo pseudocodice. Cosa si intende per "n [i] [0] <= m" se 'n [i] [0]' è un punto sull'asse x e 'm' è un insieme? Puoi chiarire un po 'e magari spiegare naturalmente quale sia la tua idea? Per set intendi una collezione ordinata o una collezione? Su quali criteri ordinate 'n'? – IVlad
Mi spiace, intendevo <= minX. Modificato. Probabilmente avrei dovuto usare la parola array invece di impostare anche per gli input. È ordinato che gli elementi siano accessibili in sequenza, ma non nel senso che i punti sono in ordine ascendente o discendente. Tutti gli input sono ordinati a caso, presumo. L'essenza del mio algoritmo era: lavorare da sinistra, trovare la linea di lunghezza più lunga che copre il primo punto scoperto e aggiungerla alla collezione. Ripeti fino a quando ogni punto è coperto. – Sean
Considera i punti '1, 100, 101, 102, 103, 104' e le linee' [1, 100] [10, 101] [20, 102] [30, 103] [40, 104] [101, 104 ] '. Se capisco correttamente il tuo algoritmo, scegli '[1, 100]' per coprire i primi due punti, '[10, 101]' per coprire il terzo, fino a '[40, 104]' per coprire l'ultimo . Possiamo fare molto meglio scegliendo '[1, 100]' e '[101, 104]' o '[1, 100]' e '[40, 104]'. Se ho capito bene il tuo algoritmo, allora non funzionerà su tutti i casi. – IVlad