La traccia lasciata percorrendo a caso la griglia rettangolare senza però passare su una cella già percorsa è conseguenza di una passeggiata casuale autoevitante, un particolare tipo di polimino. Negli anni ’40 e ’50 Paul Flory, premio Nobel per la Chimica nel 1974, introdusse modelli in cui un polimero lineare, una catena di molecole che si muove nello spazio e, per vincoli fisici di esclusione, era descritto come un percorso autoevitante sul reticolo — un’astrazione che conserva la topologia ma semplifica la fisica.
def generaW(n):
W = [(0,0)]
while len(W) < n:
x, y = W[-1]
V = [v for v in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)] if v not in W]
if V:
W.append(random.choice(V))
else:
break
return W
plot_S(set(generaW(50)))
Contare i SAW, problema inizialmente proposto in un articolo pubblicato postumo da Orr nel 1947, è notoriamente difficile. Se $c_n$ è il numero di SAW di lunghezza $n$ che partono dall’origine in $ℤ²$, e quindi $c_1=4,c_2=12,c_3=36$, non esiste formula chiusa per $c_n$. Se ne conosce invece il comportamento asintotico $$c_n ∼ Aμ^nn^{γ-1}$$ dove:
- $A > 0$ è una costante dipendente dal reticolo,
- $\displaystyle μ=\lim_{n\to\infty}c_n^\frac{1}{n}$ è la costante di connettività (≈ 2.638 per il reticolo quadrato),
- $γ$ è un esponente critico universale, con valore congetturato 43/32 in 2D; con il metodo di Montecarlo si ottengono stime come $γ≈1.15696(4)$ in 3D e per il raggio di gyration $R_g∼n^ν$.
Nonostante decenni di ricerca, la maggior parte di questi risultati rimane non rigorosamente dimostrata — specialmente in dimensione due, dove si sospetta una connessione profonda con la teoria conforme e le curve SLE (Schramm–Loewner Evolution).
I poligoni autoevitanti (SAP), d'altra parte, furono enumerati per la prima volta da Wakefield nel 1951 [57]. Wakefield non stava studiando i SAP in sé, ma piuttosto li stava enumerando come parte
di un progetto diverso, in particolare il comportamento del modello di Ising tridimensionale.
In quello studio, i SAP sul reticolo cubico semplice contribuirono all'espansione grafica
della funzione di partizione del modello di Ising.
Qualche tempo dopo, nel 1954 e nel 1955, Wall e colleghi calcolarono alcune proprietà del SAP bidimensionale e tridimensionale, emerse come sottoprodotto
del loro studio Monte Carlo del SAW. Alcune delle configurazioni SAW generate
con i metodi Monte Carlo fallirono a causa della coincidenza del punto finale dei percorsi di prova generati con l'origine. Tali fallimenti li portarono a studiare la probabilità
di queste occorrenze, e quindi introdussero la cosiddetta probabilità di chiusura iniziale dell'anello. Questa è definita come la probabilità che un SAW termini in un sito adiacente
all'origine, in modo che l'aggiunta di un singolo legame produca un circuito autoevitante.
Questa probabilità è pari a soli $\frac{2np_n}{(q − 1)c_n}$, dove q è il numero di coordinazione del
reticolo, ovvero il numero di siti più prossimi di un dato sito. Per un reticolo ipercubico d-dimensionale, $q = 2d$. In due dimensioni circa $cost\cdot n^{1.84375}$.
I SAW sono legati a una varietà sorprendente di concetti:
- al modello di Ising e alle curve di percolazione (stessi esponenti critici),
- alla SLE(8/3), una curva aleatoria che descrive il limite continuo dei SAW in 2D,
- alla teoria dei grafi (percorsi Hamiltoniani parziali),
- alla teoria dei numeri nel conteggio di strutture combinatorie complesse.
Questo metodo per la generazione casuale di polimini suggerisce diverse varianti.
def generaW(n):
W = [(0,0)]
while len(W) < n:
x, y = random.choice(W)
V = [v for v in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)] if v not in W]
if V:
W.append(random.choice(V))
return W
def generaW(n):
W = [(0,0)]
while len(W) < n:
x, y = random.choice([(x,y) for (x,y) in W if abs(x)+abs(y) == max(abs(w[0])+abs(w[1]) for w in W)])
V = [v for v in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)] if v not in W]
if V:
W.append(random.choice(V))
return W
def generaW(n):
W = [(0,0)]
i = -1
while len(W) < n and i>=-len(W):
x, y = W[i]
V = [v for v in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)] if v not in W]
if V:
W.append(random.choice(V))
i=-1
else:
i -= 1
return W
Possiamo considerare quattro contemporanei percorsi autoevitanti a partire dai quattro vicini di (0,0).
def generaW(n):
W = [(0,0),(1,0),(0,1),(-1,0),(0,-1)]
while len(W) < n:
Wadd = []
for x, y in W[-4:]:
V = [v for v in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)] if v not in W+Wadd]
if V:
Wadd.append(random.choice(V))
W += Wadd
return W[:n]
plot_S(set(generaW4(200)))
def generaW(n):
W = [(0,0)]
while len(W) < n:
Wadd = []
for x, y in W:
V = [v for v in [(x+1,y), (x,y+1), (x-1,y), (x,y-1)] if v not in W+Wadd]
if V:
Wadd.append(random.choice(V))
W += Wadd
return W[:n]
plot_S(set(generaW(500)))
- Self-avoiding walk, From Wikipedia, the free encyclopedia