ALGORITMO LEXICOGRÁFICO PARALELIZABLE PARA LA BÚSQUEDA DE CAMINOS ÓPTIMOS

Felipe Maldonado, Augusto Ciurlizza, Luis Bernardo Morales

Resumen


En este trabajo se encara el desarrollo de un algoritmo que genere las permutaciones de n elementos, con el propósito de utilizarlo en procesos de búsqueda exhaustiva para la resolución de problemas de optimización combinatoria Se presenta aquí un algoritmo secuencial que genera las permutaciones de n elementos en orden lexicográfico. El número total de intercambios necesarios para generar con el algoritmo propuesto las permutaciones den elementos es 1,543n!, y al igual que el tiempo de CPU utilizado, es menor que los reportados con anterioridad. Cabe destacar además que la única información que utiliza para generar cada permutación es la permutación precedente, por lo que resulta fácilmente paralelizable bajo cualquier arquitectura SIMD. Se ha usado el algoritmo en la optimización de un proceso textil modelado como un agente viajero asimétrico y se pudieron encontrar secuencias de colores óptimas para el tenido de telas trabajando en una computadora personal. Este último hecho resulta trascendental porque el tipo de equipo necesario condiciona la aplicabilidad en el sector industrial.

Palabras clave


Algorítmo lexicográfico/ Caminos óptimos/ Optimización/ Paralelismo/ Permutaciones

Texto completo:

PDF



Revista Universidad Ciencia y Tecnología. - http://www.uct.unexpo.edu.ve
UNEXPO, Vice-Rectorado Puerto Ordaz - Dirección de Investigación y Postgrado.
Urb. Villa Asia, Final Calle China, Edificio de Investigación y Postgrado. Puerto Ordaz, Edo. Bolívar.
Telf: (0286)9625245 - (0286)9611382. email: uct-poz@unexpo.edu.ve

Universidad Nacional Experimental Politécnica ''Antonio José de Sucre'' - Vicerrectorado Puerto Ordaz.
Dirección de Investigación y Postgrado.