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

[Ruben Gonzalez (aka EthDra)]

Me voi a tirar un poco a la piscina... pero me apetece mojarme xD
Si pensamos q los globos ia son un espacio en si mismos, si creamos el 
arbol tomando no el centro, si no los lados del cubo que circunscribe la 
esfera, acotariamos mejor la proximidad de la bala al globo y 
salvariamos el problema de los globos solapados, no? too esto lo digo de 
cabeza, por simple idea feliz, a ver que os parece, ni siquiera se si la 
complejidad seria menor :S

Se despide,
    EthDra

Borja Sotomayor 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).
>
> Un saludo,
>
>------------------------------------------------------------------------
>
>_______________________________________________
>eside-ghost mailing list
>eside-ghost en deusto.es
>https://listas.deusto.es/mailman/listinfo/eside-ghost
>

------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: https://listas.deusto.es/mailman/private/eside-ghost/attachments/20070130/e7122d3a/attachment.htm