Solución:
la idea básica del algoritmo es esta.
Tiene un conjunto de puntos P y desea encontrar los dos puntos en P que tienen la distancia más corta entre ellos.
Un simple enfoque de fuerza bruta pasaría por cada par en P, calcularía la distancia y luego tomaría el par que tenga la distancia más corta. Este es un algoritmo O (n²).
Sin embargo, es posible mejorar con el algoritmo del que estás hablando. La idea es primero ordenar todos los puntos según una de las coordenadas, por ejemplo, la coordenada x. Ahora su conjunto P es en realidad una lista ordenada de puntos, ordenados por sus coordenadas x. El algoritmo toma ahora como entrada no un conjunto de puntos, sino una lista ordenada de puntos. Llamemos al algoritmo ClosestPair (L), donde L es la lista de puntos dada como argumento.
ClosestPair (L) ahora se implementa de forma recursiva de la siguiente manera:
- Divida la lista L en su medio, obteniendo Lizquierda y yoDerecha.
- Resuelva recursivamente ClosestPair (Lizquierda) y el par más cercano (LDerecha). Deje que las distancias más cortas correspondientes obtenidas por δizquierda y δDerecha.
- Ahora sabemos que la distancia más corta en el conjunto original (representada por L) es una de las dos δs, o entonces es una distancia entre un punto en Lizquierda y un punto en LDerecha.
- Por lo tanto, aún debemos verificar si hay una distancia más corta entre dos puntos de la subdivisión izquierda y derecha. El truco es que porque sabemos que la distancia debe ser menor que δizquierda y δDerecha, es suficiente considerar de ambas subdivisiones puntos que no estén más allá de min (δizquierda, δDerecha) de la línea divisoria (la coordenada x que usó para dividir la lista original L). Esta optimización hace que el procedimiento sea más rápido que el enfoque de fuerza bruta, en la práctica O (n log n).
Si te refieres a este algoritmo, haces lo siguiente:
- Puntos de clasificación: (1,2) (1,11) (7,8)
- Construya dos subconjuntos: (1,2) (1,11) y (7,8)
- Ejecute el algoritmo en (1,2) (1,11) y en (7,8) por separado <= aquí es donde viene la recursividad. El resultado es dLmin = 9 y dRmin = infinito (no hay un segundo punto a la derecha)
- dLRmin = raíz cuadrada (45)
- resultado = min (dLmin, dRmin, dLRmin) = sqrt (45)
La recursividad consta de los mismos pasos que antes. Por ejemplo, la llamada con (1,2) y (1,11) hace:
- Puntos de clasificación: (1,2) (1,11)
- Construya dos subconjuntos: (1,2) y (1,11)
- Ejecute el algoritmo en (1,2) y en (1,11) por separado <= nuevamente llamadas de recursividad. El resultado es dLmin = infinito y dRmin = infinito
- dLRmin = 9
- resultado = min (dLmin, dRmin, dLRmin) = 9