Si vas a abrir una cafetería, querrás saber ¿Dónde está la siguiente más cercana? Esta información te ayudará a entender a su competencia. Este escenario es un ejemplo de un tipo de problema ampliamente estudiado en informática llamado búsqueda del "vecino más cercano". Se pregunta, dado un conjunto de datos y un nuevo punto de datos, ¿qué punto de los datos existentes es el más cercano a su nuevo punto? [...] Y a diferencia del ejemplo de la cafetería, las preguntas de los vecinos más cercanos a menudo son muy difíciles de responder.
Comentarios
El problema de las cafeterías es sencillo de resolver. El articulo trata de "distancias" más complejas, no espaciales.
Han descubierto el concepto algebraico de distancia? Que cracks!
Buff me da pereza leer sobre grafos pero no se podria aprovechar la 'coherencia espacial'?
Es un sistema de coordenadas, n-dimensiones, se ordenan los nodos y dado un punto donde preguntar se buscan sus vecinos mas próximos que ya tenemos calculados/ordenados en esa dimension. Se repite el proceso para el resto de dimensiones y se pitagorariza para los nodos encontrados. (cada dimensión tendria su lista de coordenadas ordenada apuntando al nodo en cuestión)
Es como si se hiciese un circulo incremental buscando vecinos aprovechando que para cada dimensión ya tenemos sus coordenadas ordenadas.... no entiendo la complejidad
#2 Es una solución que te puede servir. Habría que mirar su coste. Para n datos de d dimensiones, en memoria necesitas una estructura extra de O(dn), y en tiempo requiere O(dnlogn) para ordenar y O(dlogn + m) para la búsqueda, siendo m el número de candidatos que encuentres/consideres.
Es decir, si el extra de memoria no es un problema, el tiempo de ejecución será bueno para pocas dimensiones. Sin embargo, también podrías utilizar un kdtree, que tiene menor coste computacional. Para muchas dimensiones, el método se vuelve más pesado, lo que también le pasa al kdtree. De hecho, apostaría a que ambos métodos podrían no ser mejores que la búsqueda exhaustiva para casos se d grande.
lo que hay que hacer es calcular la distancia a todas las cafeterias, y la distancia más corta esa es la cafeteria más cercana
#1 El problema de encontrar el par de puntos más cercanos es sencillo de implementar de forma naive (ilusa) , pero es un algoritmo cuadrático y toma mucho tiempo si el número de puntos es elevado.
Yo suelo contar el algoritmo "divide y venceras" , que es bastante sorprendente para los no iniciados. Una ejecución basta para ver la diferencia de tiempos a partir de 5000 puntos.
https://es.wikipedia.org/wiki/Problema_del_par_de_puntos_m%C3%A1s_cercanos