Cosa c'è di sbagliato nella mia logica per l'algoritmo divide and conquer per il problema del Closest Pair?

Question

Cosa c'è di sbagliato nella mia logica per l'algoritmo divide and conquer per il problema del Closest Pair?

#1 da (2 voti)
#2 da (1 voti)

1

Ho seguito il corso di Coursera su Algorithms e ho escogitato un pensiero sull'algoritmo divide / conquer per il problema della coppia più vicina, che voglio chiarire.

Come da algoritmo del Prof Roughgarden (che puoi vedere qui se sei interessato): Per un dato set di punti P, di cui abbiamo due copie - ordinate in direzione X e Y - Px e Py, l'algoritmo può essere dato come

closestPair (Px, Py):

Dividere i punti nella metà sinistra - Q e nella metà destra - R, e formare copie ordinate di entrambe le metà lungo le direzioni xey - Qx, Qy, Rx, Ry
Consenti a closestPair (Qx, Qy) di essere punti p1 e q1
Consenti a closestPair (Rx, Ry) di essere p2, q2
Lascia che il delta sia il minimo di dist (p1, q1) e dist (p2, q2)
Questo è lo sfortunato caso, lascia p3, q3 essere il più vicinoSplitPair (Px, Py, delta)
Restituisce il miglior risultato

Ora, il chiarimento che voglio è relativo al passaggio 5. Dovrei dire questo in anticipo, che quello che sto suggerendo, è a malapena qualsiasi miglioramento, ma se sei ancora interessato, leggi avanti.

Il prof R dice che poiché i punti sono già ordinati nelle direzioni X e Y, per trovare la migliore coppia nel passaggio 5, è necessario iterare su punti nella striscia di larghezza 2 * delta, iniziando dal basso verso l'alto, e nel ciclo interno abbiamo bisogno solo di 7 comparazioni. Questo può essere migliorato con uno solo?

Come penso sia possibile sembrare un po 'difficile da spiegare in testo semplice, quindi ho disegnato un diagramma e l'ho scritto su carta e l'ho caricato qui:

Poiché nessun altro è venuto fuori, sono abbastanza sicuro che ci sia un errore nella mia linea di pensiero. Ma ora ho pensato a questo per ORE, e dovevo solo postare questo. È tutto ciò che è nella mia testa.

Qualcuno può indicare dove sto andando male?

algorithms

posta Programming Noob 04.07.2012 - 01:03

fonte

2 risposte

Leggi altre domande sui tag algorithms

Pattern per l'accesso alla connessione MySQL È possibile sviluppare app con l'interfaccia utente di Kendo da inviare su iOS App Store? [chiuso]

score 2 · Answer 1

La semplificazione che ti consente di effettuare solo un confronto implica implicitamente il calcolo della distanza tra i punti. Non ho visto la lezione a cui ti riferisci, ma questo è un algoritmo ben noto; le ipotesi e il ragionamento alla base del passo di cui parli vanno in questo modo:

Per ogni punto, a, entro δ del limite, puoi disegnare una casella di dimensioni δ (nella dimensione x) e 2 δ nella dimensione y. Supponendo che nessun punto sia all'interno di una d in ogni regione, quella casella contiene al massimo 6 punti, quindi è necessario confrontare solo un massimo di altri 6 punti. La parte critica che ti manca è che funziona perché è una scatola. Hai già le coordinate xey di ogni punto, quindi è facile capire se si trova all'interno di un rettangolo arbitrario. Trasformando la scatola in un cerchio, crei effettivamente più lavoro. Come puoi sapere se un punto è all'interno del cerchio? Devi calcolare la distanza dal centro del cerchio. Puoi limitare il lavoro usando il trucco sopra, ma poi sei tornato dove hai iniziato.

Se non ti dispiace un suggerimento non richiesto, ti consiglio di programmare gli algoritmi a cui stai pensando, fino a quando non riesci ad arrivare al punto in cui l'implementazione degli algoritmi è un esercizio banale. Se provassi a codificare il tuo algoritmo, ti renderai presto conto che non c'è modo di scoprire quali sono i punti all'interno della cerchia che stai descrivendo senza fare più confronti. Dopo un po ', arriverai al punto in cui non sarai più inciampato da supposizioni del genere.

score 1 · Answer 2

C'è un documento chiamato A Note sul problema delle coppie più vicine di Martin Richards (IPL 82 (2002) p193-195) che ottiene il numero di confronti fino a 2 dall'altra parte.

È abbastanza facile organizzare 2 punti dall'altra parte e il punto corrente in modo che siano tutte le unità d separate e nella casella quadrata. Li fai diventare un triangolo equilatero. Ora facendo scorrere verso l'alto uno di questi microscopici verso il punto corrente, puoi rendere uno dei due il punto più vicino. Quindi sono entrambi candidati.

Uno dei punti interessanti del documento era che i test empirici sul normale algoritmo mostravano che c'era quasi sempre uno o zero punti nella casella del candidato. In questo modo è possibile ottenere l'algoritmo standard per eseguire anche i propri eliminando i punti che sono stati spinti fuori dagli schemi anziché confrontarli ciecamente con gli ultimi 7 punti all'interno della striscia.