article
Algoritmo basado en autómatas finitos para la obtención de óptimos globales en problemas combinatorios
Algorith based on finite automata for obtaining global optimum combinatorial problems
Autor
Elías Niño; Universidad del Norte
Carlos Ardila; Universidad del Norte
Institución
Resumen
ResumenEn 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. AbstractThis 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.