Algoritmo basado en autómatas finitos para la obtención de óptimos globales en problemas combinatorios
Título del documento: Algoritmo basado en autómatas finitos para la obtención de óptimos globales en problemas combinatorios
Revista: Ingeniería y desarrollo
Base de datos: PERIÓDICA
Número de sistema: 000369083
ISSN: 0122-3461
Autores: 1
1
Instituciones: 1Universidad del Norte, Departamento de Ingeniería de Sistemas, Barranquilla, Atlántico. Colombia
Año:
Periodo: Ene-Jun
Número: 25
Paginación: 99-114
País: Colombia
Idioma: Español
Tipo de documento: Artículo
Enfoque: Experimental, aplicado
Resumen en español 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
Resumen en inglés This article states a Deterministic Finite Automaton of Exchange (DFA - E). It allows modeling of the space of feasible solutions to combinatorial problems, specifically, the problems associated with the order of elements. With the structure DFA - E defined, we designed and implemented an algorithm that uses it for obtaining a global solution of combinatorial problems. The problem we treat here can be extrapolated to any of the following: an allocation of n processes machines working in parallel, selecting the optimal route in the traveling salesman problem (TSP) and the problem of Bin Packing
Disciplinas: Ingeniería
Palabras clave: Ingeniería de sistemas,
Autómatas finitos,
Algoritmos,
Optimización combinatoria
Keyword: Engineering,
Systems engineering,
Finite automata,
Algorithms,
Combinatorial optimization
Texto completo: Texto completo (Ver HTML)