Revista Científica Ingeniería y Desarrollo, No 25 (2009)

Tamaño de la letra:  Pequeña  Mediana  Grande

Algoritmo basado en autómatas finitos para la obtención de óptimos globales en problemas combinatorios

Elías Niño, Carlos Ardila

Resumen


Resumen

En este artículo se propone un Autómata Finito Determinista de Intercambio (AFD - I) que permite modelar el espacio de soluciones factibles a problemas de naturaleza combinatoria, específicamente a problemas asociados con el orden de elementos. Con la estructura AFD - I definida, se diseña e implementa un algoritmo con cuyo uso se obtiene un óptimo global a problemas combinatorios. El problema que aquí se trata puede ser extrapolado a cualquiera de los siguientes casos: asignación de n procesos a n máquinas que trabajan en paralelo, selección de la ruta óptima en el problema del agente viajero y el problema del bin packing.


Palabras Clave / Keywords

autómata, grafo, optimización combinatoria, óptimo global

Tipo de Artículo

Artículo de investigación científica y tecnológica

Texto completo: PDF HTML

Refbacks

  • No hay Refbacks actualmente.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.