Page 12 - Tlahuizcalli CB-31_Neat

problema del TSP. En efecto, se puede hacer lo intervengan en la función de costo, ya que esto
mismo que al definir el centro de masa, porque equivale a estudiar todos los campos de fuerzas
como = 1 + ⋯ + es la suma de las entradas de que intervienen para dar una función de
| | (o sea la longitud ), en principio lo único que potencial, o sea una función que calcula cuánta
restaría sería generar (pseudo)aleatoriamente el energía cuesta recorrer la trayectoria , en el
vector ( 1 , … , ) para que fuera posible definir una sentido de cualquier teoría física que se modele a
variable aleatoria , haciendo = / . A partir de partir de campos, no solo la que se aplique para
esto, es claro que se puede calcular la media hacer carreteras. En este sentido, el algoritmo
〈 〉 = 1 1 + ⋯ + Metrópolis sirve para resolver todo tipo de
problemas cuya solución esté dada por la
Sin embargo, hay una relación entre estos obtención de un vector de las probabilidades
conceptos que es muchísimo más útil para resolver ( 1 , … , ), no solamente el TSP y no solo como parte
el TSP. Dado un vector ( 1 , … , ), por ejemplo uno del recocido simulado, solamente se requiere
generado (pseudo)aleatoriamente, y también una conocer el número 〈 〉 y generar
cantidad a la que se quiera identificar con 〈 〉, (pseudo)aleatoriamente el vector ( 1 , … , ).
pero que como en nuestro caso, no se tenga el
vector de las probabilidades ( 1 , … , ), necesario Sin embargo, lo más importante de las
para poder tener una variable aleatoria que funciones de costo es que están muy relacionadas
cumpla que 〈 〉 = 1 1 + ⋯ + , resulta que el con las . Una vez dada la dependencia explícita
algoritmo Metrópolis es el que permite hallar las entre las y las , quedará solo el problema de
a partir de los datos de entrada ( 1 , … , ) y 〈 〉. Más hallar las probabilidades ( 1 , … , ). Vamos a
aún, este algoritmo se deduce de manera natural resolver ambos problemas, codificando un modelo
a partir de dar un modelo computacional para el físico dentro del algoritmo de recocido simulado.
fenómeno físico del recocido, o sea al plantear el Recordemos que la temperatura de un sistema de
algoritmo del recocido simulado. Veamos esto en partículas no es otra cosa que una medida de la
su relación con el TSP con un ejemplo. energía cinética de estas. Veamos el ejemplo
“atmosférico” (el cual se explica originalmente en
Supongamos que la trayectoria es una (Feyman, 1998) para deducir la Ley de Boltzmann)
carretera que pasa por ciudades. Por para entender de manera más precisa la relación
comodidad supongamos que existe un mapa entre altura y temperatura; y de ahí la relación
topográfico de la región por donde pasa , tal que entre las funciones de costo y las probabilidades.
las posiciones de las ciudades corresponden a
puntos ( 1 , … , ) dentro de un cubo de volumen Si se tiene una atmósfera de masa a
fijo, esto para representar la altura sobre el nivel del temperatura constante en un campo
mar de la región, por lo que estamos pensando gravitacional (por simplicidad sea = 9.8 /
2
que podemos ver el mapa en 3D. Supongamos la constante usual de la gravedad), esto implica
también que se conoce el número 〈 〉. En cada que no hay viento, entendiendo por viento a un
segmento de al ir de a se consume una conjunto de masas de aire que se mueven a
energía , y otra al recorrerlo en sentido distintas velocidades unas respecto a otras como
contrario. Como dicho mapa indica las distintas efecto solamente de las diferencias de
alturas del terreno, podemos suponer (para temperaturas entre ellas. En otras palabras,
simplificar) que las se pueden calcular en suponemos que el movimiento promedio es
función solamente de la altura. Por ejemplo, si constante. Sin embargo, la presión no es
está a más altura que , o sea “tiene más constante, esto por causa de la gravedad: si
energía potencial” que , entonces bajamos al ir pensamos que hay partículas de aire tenemos
de a y viceversa, por lo que en dicho caso que = (donde es otra constante) pero no
< . Este enfoque simplificado no solo sirve con es constante, aquí solo depende de la altura ℎ, y
como a mayor altura hay menos presión, entonces
mapas topográficos, las energías pueden tener hay menor número de partículas, por lo que
significados más generales, como la distribución pequeños cambios en n, dados por el diferencial
de la presión atmosférica (como veremos más d , son directamente proporcionales a pequeños
adelante) y se conocen como funciones de costo. cambios en P, o sea a d , esto es, d = d . La
De hecho, este modelo es tan flexible que frase “a mayor altura menos presión” se vuelve
podemos agregar un sinfín de variables que

11
Tlahuizcalli ISSN: 2448-7260 Año 11 Núm. 31 enero-abril 2024