[eside-ghost] Quereis currar en google? Haced algoritmos!

[Juanval]

yeeeeepa

On 1/30/07, Borja Sotomayor <borja en borjanet.com> wrote:
> Jelou!
>
> > Ahora en serio, yo tp tengo ni pajolera idea.. esto si que debería (en
> > mi opinion) saberse para ser ingeniero informático (tanto tecnico como
> > superior, me da igual).
>
> Efectivamente... sin embargo, con sólo saber un poco de teoría
> informática, es fácil ver que el problema que plantea Google no es más
> que un problema (bastante clásico) llamado "Nearest Neighbors", bastante
> relevante en IA y en aprendizaje automatico.
>
>         http://en.wikipedia.org/wiki/Nearest_neighbor_search
>
> La solución trivial requiere O(NK) pasos, pero hay un método que utiliza
> un arbol balanceado para particionar el espacio (multidimensional) en el
> que se realiza la busqueda, de tal manera que pasamos de una busqueda
> lineal (calcular la distancia a todos los puntos) a una busqueda binaria
> (en la que nos cargamos la mitad de los puntos en cada iteración, y
> entonces tenemos una complejidad logaritmica, no lineal).
>
> En concreto, la estructura de datos necesaria es un arbol kd:
>
>         http://en.wikipedia.org/wiki/Kd_tree
>
> La construcción del arbol requiere N*log(N) pasos, y cada "consulta"
> (cual es el punto más cercano al "bullet") require log(N) pasos. Es
> decir, para consultar K "bullets" tenemos:
>
>         O(N*log(N)) + K*O(log(N))
>
>         K <= N: O(N*log(N))
>         K >  N: O(K*log(N))
>
> Sin embargo, todo esto solo sirve para buscar el "globo" más cercano al
> "bullet" :-) Para encontrar *todos* los globos a cierta distancia (1.0)
> del "bullet", hay que utilizar algo un poco más complejo, aunque me
> parece que un kd-tree todavía permitiría encontrarlos en un tiempo mejor
> que O(KN).

Interesante... habrá que ponerse a investigar sobre  este tema...
Menos mal que tenemos gurus de estas cosas por aqui, que si no, no
sacábamos una solución decente ni en 100 años xDD

Muchas gracias por la explicación.

taluegooo