Análisis y desarrollo de algoritmos eficientes basados en árboles para resolver el problema de vecindad

Alonso Miyazaki, Pablo Hiroshi (2017). Análisis y desarrollo de algoritmos eficientes basados en árboles para resolver el problema de vecindad. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. Industriales (UPM).

Description

Title: Análisis y desarrollo de algoritmos eficientes basados en árboles para resolver el problema de vecindad
Author/s:
  • Alonso Miyazaki, Pablo Hiroshi
Contributor/s:
  • Tapia Fernández, Santiago
Item Type: Final Project
Date: July 2017
Subjects:
Faculty: E.T.S.I. Industriales (UPM)
Department: Automática, Ingeniería Eléctrica y Electrónica e Informática Industrial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

El objetivo de este trabajo es proponer una solución al problema de la vecindad de puntos (neighborhood problem) para su aplicación en métodos numéricos sin mallado (meshfree methods), como el análisis de elementos finitos. Se determinan los rangos y situaciones óptimas de aplicación de la solución, así como la comparativa de la misma frente algoritmos existentes. El problema de la vecindad de puntos o problema de proximidad (nearest neighbor search NNS), es un problema de optimización. Consiste en determinar cuántos y qué puntos pertenecientes a un conjunto se encuentran suficientemente próximos entre sí como para considerarse vecinos. Una tarea trivial como puede ser la búsqueda del punto más cercano a otro, se puede convertir en una tarea con un coste computacional inaceptable cuando el problema escala en búsquedas del orden de cientos de miles dentro de un conjunto de millones de puntos. Métodos de fuerza bruta que calculan las distancias de cada punto del conjunto al punto objetivo, pierden todo valor a gran escala debido a su lentitud, por lo que es necesario afrontar el problema mediante otros métodos. La solución a este problema tiene numerosas aplicaciones en diversos campos de la ingeniería, así como en otras ciencias. Su generalización permite la aplicación de la misma en tareas tan dispares como el tratamiento de imágenes (donde los puntos son píxeles y la distancia es el parecido entre colores), la detección de plagios (donde los puntos son palabras y la distancia es la similitud entre estas), o métodos numéricos (donde los puntos son puntos en el espacio y la distancia es la distancia euclídea entre ellos). Este trabajo se centra en la resolución del problema para esta última aplicación. Escalar problemas de elementos finitos permite calcular y diseñar con mayor precisión estructuras o máquinas. Por ejemplo, en el campo de la ingeniería, esto se podría traducir en la fabricación de aerogeneradores y turbinas más eficientes. Concretamente, la resolución del problema de la vecindad de puntos es sumamente útil en los métodos númericos sin mallado, pues a diferencia del método clásico de análisis con mallado, los vecinos de cada punto no son fijos y es necesario recalcularlos en cada iteración. La ausencia de mallado permite resolver simulaciones de dinámica de fluidos, o de grandes deformaciones en sólidos (para materiales con comportamiento plástico), donde la situación de cada punto puede variar significativamente de una iteración a la siguiente, y es necesario determinar sus puntos vecinos de forma dinámica. Se propone primero una solución al problema, y posteriormente se comparará la misma respecto a otras soluciones existentes. En la solución propuesta, se cubren las búsquedas para d dimensiones, y se permitirán búsquedas para hallar los puntos dentro un radio r, así como los k puntos más próximos del punto objetivo. Para ello, se preprocesa dinámicamente el conjunto de datos, dividiendo los puntos del espacio en celdas y construyendo en ellas árboles de búsqueda binarios en caso de haber suficiente densidad de puntos, optimizando el empleo de métodos de fuerza bruta o búsqueda binaria según la celda. La solución se compara respecto a las existentes para un conjunto de problemas en tres dimensiones y se determina en qué casos cuál es la mejor solución, la generalidad de los resultados y su extrapolación teórica a dimensiones superiores. Así mismo, se validarán las previsiones teóricas del coste computacional de la solución propuesta respecto de los resultados obtenidos en la práctica.

More information

Item ID: 49068
DC Identifier: http://oa.upm.es/49068/
OAI Identifier: oai:oa.upm.es:49068
Deposited by: Biblioteca ETSI Industriales
Deposited on: 15 Jan 2018 12:26
Last Modified: 25 Apr 2018 14:32
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM