Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance

Los problemas de optimización discreta, también conocidos como problemas combinatorios, surgen en diversas áreas y en general se resuelven utilizando técnicas que buscan una solución en el espacio de estados implícito del problema. Debido a la alta complejidad computacional de esta clase de problema...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Sanz, Victoria María
Otros Autores: De Giusti, Armando Eduardo
Formato: Tesis Tesis de grado
Lenguaje:Español
Publicado: 2009
Materias:
Ciencias Informáticas
búsqueda y recuperación de información
Heuristic methods
Optimization
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/4008
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-4008
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
búsqueda y recuperación de información
Heuristic methods
Optimization
spellingShingle Ciencias Informáticas
búsqueda y recuperación de información
Heuristic methods
Optimization
Sanz, Victoria María
Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance
topic_facet Ciencias Informáticas
búsqueda y recuperación de información
Heuristic methods
Optimization
description Los problemas de optimización discreta, también conocidos como problemas combinatorios, surgen en diversas áreas y en general se resuelven utilizando técnicas que buscan una solución en el espacio de estados implícito del problema. Debido a la alta complejidad computacional de esta clase de problemas, las búsquedas exhaustivas se vuelven inaceptables, por lo cual se han desarrollado algoritmos heurísticos que utilizan funciones para evaluar el costo de los nodos y de este modo procesar primero los nodos que se estima están más cercanos al nodo “solución óptima”. Es de interés el desarrollo de heurísticas más potentes y algoritmos paralelos que resuelvan los problemas de optimización discreta de forma eficiente, con el fin de resolver instancias cada vez más grandes y dado que algunos problemas requieren soluciones en tiempo real, el paralelismo es en muchos casos la única forma de obtener el tiempo de respuesta esperado. En este marco, este trabajo toma como caso de estudio un problema de optimización clásico llamado Puzzle N<SUP>2</SUP>-1, y presenta una solución secuencial basada en el algoritmo A*. Se estudian variantes de la función heurística clásica (basadas en la Distancia de Manhattan) y se expone un trabajo experimental para analizar las mejoras en el rendimiento producidas, partiendo de diferentes configuraciones iniciales. Se propone una solución paralela al problema del Puzzle N<SUP>2</SUP>-1 sobre una arquitectura tipo cluster, y se analiza el speedup, la eficiencia, y la superlinealidad a medida que se escala el número de procesadores y el tamaño del problema (N). Se presenta además una generalización del problema para su aplicación a la planificación de movimientos de robots con múltiples objetivos.
author2 De Giusti, Armando Eduardo
author_facet De Giusti, Armando Eduardo
Sanz, Victoria María
format Tesis
Tesis de grado
author Sanz, Victoria María
author_sort Sanz, Victoria María
title Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance
title_short Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance
title_full Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance
title_fullStr Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance
title_full_unstemmed Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : Análisis de performance
title_sort paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster : análisis de performance
publishDate 2009
url http://sedici.unlp.edu.ar/handle/10915/4008
work_keys_str_mv AT sanzvictoriamaria paralelizaciondeproblemasdebusquedaengrafosenunaarquitecturatipoclusteranalisisdeperformance
bdutipo_str Repositorios
_version_ 1764820473014648832

Ejemplares similares