Algoritmo de pivote

El algoritmo pivote es una forma de algoritmo de Monte Carlo que se utiliza para generar configuraciones de caminos autoevitantes , típicamente en una red . ^{[ 1 ]} El algoritmo generalmente comienza con una línea recta que consta de N puntos en la red y la transforma en una forma desorganizada conocida como camino, en la que no hay dos puntos en el camino que ocupen el mismo sitio en la red. En dos dimensiones, opera según los siguientes pasos:

1. Seleccione un punto aleatorio p entre 1 y N alrededor del cual pivotar. Esto divide el recorrido en dos, uno de longitud p y otro de longitud ( N − p ).
2. Seleccione aleatoriamente de qué lado del punto pivotar.
3. Seleccione aleatoriamente una transformación, como una rotación de 90, 180 o 270 grados o una reflexión sobre el eje horizontal o vertical, y aplíquela a los puntos del lado seleccionado del punto de pivote.
4. Comprueba si dos puntos cualesquiera ocupan la misma posición en la red. Si es así, descarta el pivote y vuelve a intentarlo. Si no, procede con otro pivote.

Las configuraciones generadas por el algoritmo proporcionan información sobre la combinatoria de los caminos autoevitantes y se utilizan para comprender la física de los polímeros , que pueden aproximarse como caminos autoevitantes. El algoritmo fue inventado por Moti Lal en 1969. ^{[ 2 ]} Puede implementarse de manera eficiente, con una complejidad computacional que permite generar caminos de longitud N en un tiempo proporcional al logaritmo de N , conocido como tiempo logarítmico . ^{[ 1 ]}