Automi cellulari e polimini
La generazione di polimini può essere vista come automa cellulare stocastico. Se immaginiamo ogni cella del reticolo quadrato come “vuota” o “occupata”, diventa occupata se è adiacente a una cella già occupata con probabilità definita da una data regola. Il processo termina raggiunta la prestabilita dimensione.
Ad esempio si potrebbe considerare più probabile la scelta di "riprodursi" in una cella del bordo esterno con un maggior numero di elementi del polimino vicini, o al contrario dove ce ne sono meno.
def generaP(n, asociale=False):
S = {(0,0)}
B = {(1,0): 0.25, (0,1):0.25, (-1,0):0.25, (0,-1):0.25}
for _ in range(n-1):
# Select a key from B based on probabilities
x, y = list(B.keys())[np.random.choice(range(len(B)), p=list(B.values()))]
S.add((x, y))
del B[(x, y)] # Remove the chosen key from B
for b in {(x+1,y), (x,y+1), (x-1,y), (x,y-1)} - S:
B[b] = 0
# Add new neighbors to B with initial probability 1 (to be normalized later)
for (x,y) in B:
B[(x,y)] = 1/len({(x+1,y), (x,y+1), (x-1,y), (x,y-1)} & S) if asociale else len({(x+1,y), (x,y+1), (x-1,y), (x,y-1)} & S)
tot = sum(B.values())
B = {k:v/tot for k,v in B.items()}
return S
S = generaP(50)
plot_S(S)
Nel primo caso si otterrà probabilmente polimini più coesi, con un interno di area meggiore, rispetto al secondo caso.
S = generaP(50, asociale=True)
plot_S(S)
Per approfondimenti:
- Cellular automaton, From Wikipedia, the free encyclopedia