Page 14 - Tlahuizcalli CB-31_Neat

solidificación, esta está caracterizada por el (RS 2) Al hacer un ciclo completo sobre todas
dominio de la atracción incluso por encima del las partículas, se baja en un grado la temperatura
potencial dado por la distancia al centro de la y se vuelve a correr el ciclo.
Tierra. De hecho, lo que detiene que los átomos
colapsen por efectos de la gravedad es la Naturalmente, al correr Metrópolis, se cumple
repulsión, en otras palabras, la repulsión eléctrica 0 < exp (− ∆ ) < 1. Al principio es muy grande,

no solo es la fuerza que impide que perforemos el por lo que este número es casi cero, entonces es
piso donde estamos parados, sino que es la que prácticamente imposible guardar esta
permite que podamos simplificar la dinámica de configuración. De cualquier manera, se guarda si
cuerpos sólidos aproximándola por la de su centro es mayor que y se rechaza en caso contrario, por
de gravedad, o sea por la Mecánica Clásica.
lo que en ambos casos se pasa a la partícula + 1.
IV. Implementación computacional Por otro lado, al mover la partícula esta se
traslapa con la vecindad de alguna otra , se
4.1. Seudocódigo de los Algorimos. rechaza el movimiento, por lo que no se mueve la
partícula , y se pasa a la + 1. Esto se puede
Finalmente, podemos dar un modelo entender como que hubo una fuerte repulsión que
computacional de los algoritmos Metrópolis (M) y perturba el sistema.
Recocido Simulado (RS). Pensemos en una
colección de bolitas en posiciones ( , ) a las que Por último, es claro que va a llegar un momento
vamos a dar movimiento, de forma aleatoria, donde la temperatura sea lo suficientemente baja
tomando en cuenta la ecuación de Boltzmann. para que prácticamente siempre se cumpla la

(RS 1) Primero se posiciona la temperatura en condición exp (− ∆ ) > , puesto que

su valor máximo. exp (− ∆ ) tiende a su máximo cuando baja

mucho. Esto se interpreta físicamente como que el
Para cada valor de procedemos a echar a sistema se ha recocido. En otras palabras, una vez
andar a Metrópolis: que sea muy baja, vamos a llegar a un sistema
“solidificado” donde siempre se puede recorrer la
(M) Movemos aleatoriamente la partícula (de gráfica cíclica , la cual tiene aristas dadas por
una en una) para que su centro quede en algún cualquier par de partículas ( , ) que hayan sido
punto dentro del cuadradito de lado 2 . Si no cae relacionadas en algún paso del algoritmo por la
dentro de la vecindad de ninguna otra partícula , ∆
hay dos posibilidades: condición exp (− ) > .

Si disminuye la nueva energía potencial 4.2. Cálculo del camino óptico óptimo en un
respecto a la dada antes del movimiento sistema de percolación 3D usando RS y M.
aleatorio, esto es ∆ < 0, esto se interpreta como
que la energía del sistema se liberó de manera En 1972, Richard M. Karp mostró que el
natural, por lo que se guarda esto como problema del viajero es un problema NP-duro, esto
movimiento aceptado y procedemos a mover la significa que no se puede resolver en tiempo
partícula + 1. polinomial. En el peor de los casos el tiempo de
ejecución para cualquier algoritmo que resuelva el
Si por el contrario la energía potencial aumenta, TSP aumenta de forma exponencial con respecto
∆ > 0, la comparamos con un número al número de ciudades, ya que se tiene que
pseudoaleatorio entre 0 y 1, generado considerar ( − 1)!/2 rutas posibles (donde es el
previamente a partir de dar una v.a. uniforme , (o número de ciudades). Así, a medida que el
sea que las entradas ( 1 , … , ) tienen número de ciudades aumenta, el cálculo para
probabilidades 1/ ), y se guarda como encontrar recorridos óptimos se vuelve muy
movimiento aceptado si y solamente si se cumple complejo computacionalmente (Edmons, 1972)

que exp (− ∆ ) > .
En los últimos años, el estudio de las estructuras
desordenadas ha sido de gran interés para la
investigación.

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