Algoritmos de búsqueda con retroceso para problemas multicriterio
Algoritmia
Publicado el 16 de Marzo del 2018 por Administrador
2.118 visualizaciones desde el 16 de Marzo del 2018
La búsqueda en grafos, con multitud de aplicaciones en el mundo real, ha propiciado el diseño de una gran cantidad de algoritmos centrados en el procesamiento de un único objetivo, magnitud representativa del coste. Sin embargo, un tratamiento realista de estos problemas requiere en muchas ocasiones contemplar diferentes objetivos de modo simultáneo. Además, es habitual que estos objetivos sean antagónicos, de tal modo que la optimización de uno de ellos se traduzca en el empeoramiento de uno o varios de los objetivos restantes. Esto hace que el coste óptimo no sea único, sino que generalmente existe un conjunto de soluciones óptimas cuyas componentes de coste están compensadas entre sí.
Esta naturaleza multiobjetivo de los problemas provoca que el rendimiento de los algoritmos empeore de modo considerable, ya que al procesamiento habitual de los nodos generados durante el proceso de búsqueda hay que añadir el tratamiento de vectores de coste (de dimensión igual al número de objetivos considerado) y el manejo de un conjunto de soluciones óptimas (cuyo tamaño en el peor de los casos será exponencial), siendo este tipo de operaciones muy costosas desde el punto de vista de tiempo y memoria.
De las dos principales clases de algoritmos exactos multiobjetivo, la correspondiente a un enfoque best-first ha sido ampliamente estudiada, dando lugar a una gran cantidad de algoritmos que persiguen reducir la complejidad espacial y temporal del proceso de búsqueda. Asimismo existen numerosas y detalladas comparativas de endimiento entre estos algoritmos. Sin embargo la clase de algoritmos depth-first, aún siendo de gran utilidad en la resolución de problemas con grafo de búsqueda en forma de árbol, presentaba un reducido número de propuestas, careciendo además de análisis comparativos entre las mismas.
Esta tesis pretende cubrir dicho hueco, realizando un estudio sistemático de algoritmos exactos multiobjetivo de tipo depth-first.
En formato pdf. Contiene 274 páginas.
Esta naturaleza multiobjetivo de los problemas provoca que el rendimiento de los algoritmos empeore de modo considerable, ya que al procesamiento habitual de los nodos generados durante el proceso de búsqueda hay que añadir el tratamiento de vectores de coste (de dimensión igual al número de objetivos considerado) y el manejo de un conjunto de soluciones óptimas (cuyo tamaño en el peor de los casos será exponencial), siendo este tipo de operaciones muy costosas desde el punto de vista de tiempo y memoria.
De las dos principales clases de algoritmos exactos multiobjetivo, la correspondiente a un enfoque best-first ha sido ampliamente estudiada, dando lugar a una gran cantidad de algoritmos que persiguen reducir la complejidad espacial y temporal del proceso de búsqueda. Asimismo existen numerosas y detalladas comparativas de endimiento entre estos algoritmos. Sin embargo la clase de algoritmos depth-first, aún siendo de gran utilidad en la resolución de problemas con grafo de búsqueda en forma de árbol, presentaba un reducido número de propuestas, careciendo además de análisis comparativos entre las mismas.
Esta tesis pretende cubrir dicho hueco, realizando un estudio sistemático de algoritmos exactos multiobjetivo de tipo depth-first.
En formato pdf. Contiene 274 páginas.