Page 11 - Tlahuizcalli CB-31_Neat

aleatoria se denomina uniforme. Se define la una arista que va del 3 al 7, otra del 7 al 4, etc. y al
media 〈 〉 de la variable aleatoria como el llegar al vértice 5 la “última” arista va del 5 al 3. Es
producto punto de ambos vectores, o sea 〈 〉 = claro que sin importar en cual vértice
1 1 + ⋯ + . En particular, para una variable comencemos, la “forma” de la gráfica cíclica (o
aleatoria uniforme la definición de su media sea el conjunto de aristas que conecta a los
coincide con la del promedio. vértices) determina a σ, pero también está
determinada por el −ciclo σ. En general, se
Dadas ahora partículas en posiciones pueden escribir en los números dados por σ
( 1 , … , ) con masas ( 1 , … , ), se puede definir la como subíndices de los vértices, o sea que al
masa total como el escalar = 1 + ⋯ + , y reconstruir a partir de σ, si en alguna parte del
pesos o = / , a los que no es descabellado −ciclo hay dos números (… … ), entonces habrá
llamar “probabilidades” porque son positivos y dos vértices , conectados por la arista .
suman 1. De aquí es claro que las ( 1 , … , ) junto
con las ( 1 , … , ), definen una variable aleatoria . En caso de que la función de costo esté dada
Más aún, se tiene que la posición del centro de por la longitud de cada arista de . Si | |
masa es precisamente la media 〈 〉 de la variable denota dicha longitud, y se tienen dadas las
aleatoria . Dicho de otra manera, el movimiento coordenadas de dos vértices = ( , , ), =
del punto 〈 〉 aproxima de manera muy buena al ( , , ), entonces | | puede definirse como la
del conjunto de partículas en las posiciones distancia usual en el espacio, o sea
( 1 , … , ) y con masas ( 1 , … , ).
2
2
2
Otra razón por la que es conveniente un | | = √ ( − ) + ( − ) + ( −
)
modelo probabilístico para problemas físicos que
consideran el estudio de partículas, es que la Esta definición de distancia es la que usamos en
acción de un campo de fuerzas se extiende sobre la sección 4. Cabe mencionar que en algunas
los trozos de materia mediante un gran número de aplicaciones físicas es preferible calcular la
colisiones. En cada colisión, el movimiento cambia distancia partir de la suma | − + | − + | −
|
|
abruptamente y entonces un modelo matemático |, ver por ejemplo (Kirkpatrick, 1983)
basado en derivadas, como en el caso de las
ecuaciones de Newton no es nada eficiente, ver
por ejemplo (Sobol, 1983). Sin embargo, un hecho Escribiremos | | para indicar las longitudes de
bien conocido es que las propiedades las aristas , por lo que | | es un vector de
entradas positivas, o sea un elemento de , tal

macroscópicas de la materia cuando esta se
encuentra a temperatura constante se pueden que la longitud de es simplemente la suma de las
conocer en términos del movimiento promedio de entradas del vector | |. Denotaremos este número
sus partes. como . Esta notación se puede generalizar para
cualquier gráfica con pesos, esto es, para
3.2 Planteamiento del TSP en términos de cualquier gráfica donde la cantidad es el costo
gráficas con pesos. de ir del vértice al . De aquí es claro que si es
una gráfica cíclica con pesos, está descrita por la
En el problema TSP se trata de encontrar la pareja (σ, ). Entonces podemos plantear el
trayectoria o gráfica cíclica (de longitud mínima) problema TSP como sigue:
que une puntos, o sea que tiene el mismo
número de vértices y de aristas . En nuestro Dado un conjunto de vértices , hallar la
caso, supondremos que es una gráfica en el pareja (σ, ) que minimiza .
espacio. Se puede describir una gráfica cíclica
numerando de forma arbitraria sus vértices, de 3.3 El modelo Termodinámico del recocido y su
manera que cada arista está determinada por dos aplicación para el TSP.
números consecutivos de esta lista. Esto se
denomina un −ciclo σ. Por ejemplo, si = 10 y Antes vimos que la correspondencia entre la
se numeran los vértices de la forma media de una variable aleatoria y el centro de
σ=(3 7 4 2 8 10 1 9 6 5), quiere decir que si masa de un cuerpo rígido proveen un pequeño
comenzamos en el vértice marcado con el 3, hay “puente” entre Física y Estadística. Más aún, esto
también tiene una relación muy estrecha con el

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