Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)

Resumen

El ordenamiento de permutaciones por reversión de prefijos (SPBR) es un clásico problema de optimización combinatoria cuyo objetivo es ordenar una permutación de n elementos invirtiendo los bloques más a la izquierda (prefijos) de dicha permutación. En términos técnicos, se busca transformar una permutación dada pi en una permutación identidad llamada i. Podría compararse, en magnitud, a una pila de tortitas que se debe reordenar con una espátula en cualquier punto, invirtiendo su orden para que, tras varias iteraciones, la pila quede ordenada. Sin embargo, desde 2012 se ha demostrado que este problema pertenece a la clase NP-Hard, lo que lo hace inviable en términos prácticos para la construcción de una solución óptima en tiempo polinómico o inferior. En los últimos años, la comunidad académica ha tratado de utilizar algoritmos heurísticos y metaheurísticos de aproximación que proporcionen mejores resultados y se acerquen al óptimo global. Durante el desarrollo de esta investigación se ha realizado y comparado el estado del arte del problema en estudio, se diseñarán e implementarán algoritmos heurísticos y metaheurísticos basados en criterios propuestos por la literatura revisada. Asimismo, se propondrá una familia de metaheurísticos inspiradas en la vida, cuyo rendimiento se espera que sea eficiente en la búsqueda de soluciones en grandes espacios de búsqueda. Para llevar a cabo la implementación de los algoritmos, se utilizará el lenguaje de programación Python, en combinación con la herramienta Google Colab, lo que permitirá un análisis rápido y eficiente de los algoritmos. Además, se revisaron los conceptos básicos relacionados con la teoría moderna de permutaciones y sus métodos elementales de ordenación. Se evaluaron distintos algoritmos heurísticos y metaheurísticos utilizando un conjunto de resultados obtenidos en la literatura científica de los últimos 10 años. Se compararon las ventajas y desventajas de cada método y se determinó cuál es el más adecuado en función del contexto del problema en cuestión.