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

[Borja Sotomayor]

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).

Un saludo,
-- 
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Borja Sotomayor, University of Chicago
  Ph.D. Student, Department of Computer Science
  Ryerson 257-C, 1100 East 58th Street, Chicago, IL
GT4 Tutorial: http://gdp.globus.org/gt4-tutorial/
BorjaNet:  http://www.borjanet.com/   borja en borjanet.com
·····························································
          "Dis maschine vill run und run!"
                -- Kurt Gödel (on the Turing Machine)
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::