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

Descripción

Título: Análisis y desarrollo de algoritmos eficientes basados en árboles para resolver el problema de vecindad
Autor/es:
  • Alonso Miyazaki, Pablo Hiroshi
Director/es:
  • Tapia Fernández, Santiago
Tipo de Documento: Proyecto Fin de Carrera/Grado
Fecha: Julio 2017
Materias:
Escuela: E.T.S.I. Industriales (UPM)
Departamento: Automática, Ingeniería Eléctrica y Electrónica e Informática Industrial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (2MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 49068
Identificador DC: http://oa.upm.es/49068/
Identificador OAI: oai:oa.upm.es:49068
Depositado por: Biblioteca ETSI Industriales
Depositado el: 15 Ene 2018 12:26
Ultima Modificación: 15 Ene 2018 12:26
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM