"
Solución
sub-optima al Problema del Agente Viajero utilizando automatas
Celulares"
Básicamente un Autómata Celular se puede ver como una abstracción matemática
de un sistema dinámico, en el cual, tanto el espacio como el tiempo, son
discretos.
Imaginemos una red conformada por celdas o sitios descritos por variables,
que a su
vez, conforman un conjunto finito de valores discretos. El estado del
sistema (la
totalidad de la red) en un tiempo "t" está dado por el valor que toma la
variable
que describe a cada una de las celdas. A su vez, este valor depende del
valor que
tenían las celdas vecinas y del suyo propio en un tiempo inmediatamente
anterior.
El espacio, el tiempo y los valores de cada celda son todos discretos. Esto
hace
que los AC sean idóneos para ser modelados con una computadora.
En este trabajo se aplican los Autómatas Celulares a la resolución
del
Problema del Agente Viajero (TSP). El TSP se puede sintetizar
esquemáticamente de
la siguiente manera: Dado un número N de ciudades con sus respectivas
posiciones,
se debe encontrar un camino cerrado que pase por cada una de ellas una sola
vez,
minimizando la función de costo respectiva. Esta función de costo puede ser
la
distancia, el tiempo, la energía etc. Generalmente se toma la distancia
recorrida
como función de costo a considerar. La solución a este problema es
equivalente a
encontrar el camino hamiltoniano de menor costo en un grafo no dirigido.