Page 9 - Tlahuizcalli CB-31_Neat
P. 9
II. Características generales de los algoritmos subconjuntos de vértices que se hallan agrupado
para el TSP. de manera arbitraria.
En esta sección se describen las generalidades del Los otros métodos se llaman de mejora iterativa.
algoritmo de recocido simulado, así como algunas Estos se basan en comenzar con los puntos en una
de sus relaciones con otros algoritmos usados en configuración inicial conocida, y de ahí se
optimización (Kirkpatrick, 1983) perturban un poco a configuraciones cercanas,
de manera que solo cuando la función de costo
Se puede plantear el TSP como sigue. Dada una de la nueva configuración es menor que la
cantidad de puntos distribuidos de manera anterior, esta sustituye a la antigua configuración
aleatoria, identificados con los vértices = {1, … } del sistema, de lo contrario se descarta. El proceso
dentro de un cuadrado o en un cubo tal que termina cuando ya no se puede mejorar el costo
para cualesquiera dos vértices ( , ) se puede de la configuración, y se graba el mejor resultado
definir la distancia entre ellos, con la cual se obtenido. Aquí un problema común es que el
etiqueta la arista que conecta dichos vértices. En algoritmo se quede trabado en un mínimo local,
ocasiones, en lugar distancia se introducen pesos pues por definición todas las configuraciones
. Es posible resolver el TSP si podemos hallar una cercanas tienen mayor costo, pero puede existir un
trayectoria que pase exactamente una vez por mínimo global inalcanzable desde la
todos y cada uno de los vértices, esto configuración que se tomó inicialmente, por lo que
corresponde a encontrar una gráfica cíclica con este tipo de algoritmos se corren varias veces
pesos que minimice la función de costo definida desde distintos puntos iniciales y al final se toma el
como la suma de los pesos de sus aristas. mejor resultado de todos.
Explicaremos esto en la sección 3.2.
Por otro lado, el método del recocido simulado
La dificultad comienza a la hora de hacer los permite resolver el TSP basado en un modelo de la
cálculos, pues todos los métodos que se conocen Física Estadística, la cual estudia porciones de
para dar una solución exacta del TSP tienen un materia en equilibrio térmico. Aquí los métodos
costo computacional que se incrementa matemáticos que se usan son siempre
exponencialmente respecto al valor , por lo que probabilísticos (en particular se mide el
las soluciones exactas que son calculables en comportamiento promedio de un sistema de
tiempos razonables son del orden de pocas partículas) ya que la cantidad de partículas en
centenas. En la mayoría de las aplicaciones cualquier volumen macroscópico es de un orden
prácticas interesantes, el orden de es de varias muchísimo mayor que los descritos en las
decenas o centenas de miles, por lo cual hay que aplicaciones antes mencionadas.
restringirse a métodos que sean relativamente
baratos de implementar, y que al mismo tiempo Un problema fundamental en Física Estadística
proporcionen buenas aproximaciones del ciclo se refiere a las configuraciones de posiciones y
óptimo a encontrar. velocidades que sufre un conjunto de partículas al
bajar la temperatura del medio. En un régimen de
De manera general, existen dos clases de temperaturas muy altas todas las partículas tienen
algoritmos para encontrar soluciones aproximadas un estado gaseoso, y luego van condensándose
del TSP. En primer lugar, están los del tipo divide y en líquidos y/o sólidos al descender la
vencerás, en los que se divide a en subregiones temperatura. En particular, al llegar al estado
de un tamaño manejable, donde se puedan hallar sólido puede suceder que se formen cristales, los
primero pedazos de la trayectoria óptima, y luego cuales corresponden a los estados base o de
se unen para obtener el ciclo completo. Aquí la energía mínima, estas son las configuraciones más
restricción principal es que la división se debe raras de encontrar, en tanto que los mínimos
adaptar naturalmente a la configuración de los locales de energía corresponden a cristales
puntos, por ejemplo, que se observen amorfos, como el vidrio. Una forma de
aglomeraciones entre subconjuntos de vértices a implementar lo anterior es mediante el recocido
priori. De lo contrario, la longitud de puede de una muestra, lo cual consiste en calentar el
crecer mucho al pegar trayectorias en medio a una temperatura muy alta, hasta que
tengamos una licuefacción homogénea, donde
8
Año 11 Núm. 31 enero-abril 2024 Tlahuizcalli ISSN: 2448-7260
