Griglia infinita di uni e di zeri...

[panurge]

Immaginiamo una matrice infinita. Le varie celle possono essere bianche o nere (0 o 1 se preferite). Immaginiamo di partire da una casella, muovendoci solo in orizzontale e verticale, con la restrizione di camminare solo sulle caselle dello stesso colore di quella da cui siamo partiti. Il più delle volte definiamo così una certa "area" raggiungibile, oltre i confini della quale non possiamo andare perchè siamo bloccati da celle di colore diverso.
Uno potrebbe chiedersi: quant'è grande quest'area, in media? Dal momento che le idee combinatoriche che ho avuto al riguardo sono abbastanza difficili da portare a termine, ho provato con la foza bruta. Programmando un po' di routines in pari/gp (pace sia su di lui), sembrerebbe che l'area media oscilli intorno a valori come 57,59,62... eccetera. Abbastanza sorprendente...

Naturalmente sorgono pensieri di due tipi, che mi fanno dubitare che la risposta sia del tutto attendibile...
In primo luogo, per forza di cose la mia matrice non è infinita, dunque dovei tenere in conto l'approssimazione che faccio quando il programma va a sbattere contro il bordo e io gli dico di fermarsi.
Secondariamente, molte volte la media molto elevata che abbiamo osservato è dovuta in buona parte a un paio di valori sorprendentemente grandi, dunque proprio quei valori che, per l'osservazione precedente, avrebbero in alcuni casi potuto essere molto maggiori.
Magari, addirittura, la media potrebbe divergere, sebbene sia molto innaturale da pensare...

Insomma, adesso la solita domanda... qualcuno ha già studiato il problema?

[fu^2]

problema interessante...

Una cosa: i movimenti sono scelti in maniera completamente aleatoria tra le caselle dello stesso colore adiacenti alla casella in cui parti?...

[panurge]

Giusta domanda, credo sia il caso di spiegarsi un po' meglio:

quando parlavo di "movimento" volevo solo dare l'idea alla base del problema... in realtà, dal momento che ci interessa l'area in questione, è come se volessimo tenere in considerazione il numero di *tutte* le caselle raggiungibili da quella di partenza.
Vedendo la cosa in termini grafici (es:bitmap in bianco e nero), ci interessa sapere, in media, quanti pixel vengano colorati (mettiamo in rosso) se decidiamo di applicare il comando "riempimento" da qualche parte.

Se qualcuno ha installato pari/gp, può provare a importare il seguente file (l'ho fatto l'altro ieri, credo si possa rendere un po' più veloce... ma ci penserò prima o poi)

// questa funzione fa quello che dice: tutto in uno. Per come è stata fatta, meglio metterci dentro un argomento pari!
tuttuno(n) =
	{
	local(a);
	a=rmat(n);
	aa=nova(a,n/2,n/2,a[n/2,n/2]);
	return(howmany(aa));
	}

//questa funzione ripete un tot di volte la funzione tuttuno(n), e salva gli outputs in un vettorone, appunto.
vettorone(n,maxo) =
	{
	local(v);
	v=[];
	for(i=1,maxo, v=concat(v,[tuttuno(n)]));
	return(v);
	}

// questa funzione fa la media degli elementi nel vettorone.
avrg(v) =
	{
	local(summ);
	for(i=1,matsize(v)[2],summ=summ+v[i]);
	return(summ/(matsize(v)[2]));
	}

// genera una matrice casuali a valori in {0,1}
rmat(n) =
	{
	return(matrix(n,n,X,Y,random(2)));
	}

// genera una nuova matrice, uguale a quella in input (a), dove gli elementi raggiungibili da a[x,y] vengono sostituiti da "-1" se sono uguali a "si".
nova(a,x,y,si) = 
	{
	local(aa, aaa, fermati, buba);
	aa=a;
	aaa=aa;
	aaa[x,y]=-1;
	fermati=0;
	while(fermati==0,
			if(aa==aaa,return(aa));
			aa=aaa;
			for(i=1,matsize(aa)[1],for(j=1,matsize(aa)[2],
				
				if(aaa[i,j]==-1,


					if(j<matsize(aaa)[1] && aaa[i,j+1]==si,aaa[i,j+1]=-1);
					if(i<matsize(aaa)[1] && aaa[i+1,j]==si,aaa[i+1,j]=-1);
					if(j>1 && aaa[i,j-1]==si,aaa[i,j-1]=-1);
					if(i>1 && aaa[i-1,j]==si,aaa[i-1,j]=-1);


					);

				));

			);

	}

//questa ci dice quanti "-1" ci sono nella matrice in input.
howmany(a) =
	{
	local(ms,hm);
	hm=0;
	ms=matsize(a)[1];
	for(i=1,ms,for(j=1,ms, if(a[i,j]==-1,hm=hm+1;)));
	return(hm);
	}

Vabbé, se non avete voglia di stare a leggervi tutto il codice, provate a importarlo (scrivendo \r nomefile.gp, dove nomefile è il file di testo in cui avete copiato il codice, e salvato con estensione .gp all'interno della cartella del Pari) e scrivete:

a=rmat(20)
invio
b=nova(a,3,3)
invio
howmany(b)
invio
...e dovreste ricevere la risposta al problema.
Per fare tutto in un colpo, usate:

tuttuno(20).

Se volete ripetere tante volte l'esperimento, scrivete

vettorone(20,100)
e ottenete 100 risultati dell'esperimento.
a questo punto avrg(%) ci da la media dei valori ottenuti.

Buon divertimento... Sarebbe carino cosa succede ammettendo matrici a valori in {0,1,2,3,...n} facendo variare n...


PS: allora, proprio ora ho introdotto una nuova funzione:

procedi(n) =

	{
	local(last, quanti, media);
	quanti=0;
	media=0;
	
		while(1,
		last=tuttuno(n);
		
		
		if(quanti==0,media=last, media=(media*quanti + last)/(quanti+1)

*1.);
		quanti=quanti+1;
		print(media);
		
		)
	}

Che voi potete chiamare e lei va avanti all'infinito "aggiornando" la media di volta in volta. A questo punto basta aspettare e vedere a cosa convergono i numeri che sputa fuori...

Nel frattempo mi è venuta anche una idea per superare i limiti teorici citati nel primo post, e anche per velocizzare il tutto: sarebbe da fargli fare l'esperimento in una matrice piccola (tipo 20x20), e se viene raggiunto il bordo la matrice viene "gonfiata" con nuovi valori random... Ci proverò

A presto...

[Umby2]

"fu^2":

Una cosa: i movimenti sono scelti in maniera completamente aleatoria tra le caselle dello stesso colore adiacenti alla casella in cui parti?...

da quello che ho capito, poco importa la scelta del movimento da fare. Nel senso che ad ogni casella buona, vai a controllare tutte le altre adiacenti, e se ce ne sono altre buone continui.
Da una prima impressione penso che piu caselle vengono settate, piu' è facile che se ne trovino altre. In altre parole, inizialmente il gioco puo' terminare presto ma se poi si avvia nella direzione giusta ( e si ramifica ) piu' difficilmente si ferma.

[Umby2]

"panurge":

Insomma, adesso la solita domanda... qualcuno ha già studiato il problema?

Non penso che sia un problema di facile risoluzione ....

Un paio di domande:
- Nella simulazione da te fatte, hai usato una matrice grande quanto ? Quadrata ?
- La cella iniziale di partenza, come l'hai scelta ? A caso ? Hai preferito prendere la centrale ?

[panurge]

Grazie per l'interessamento, umby...

La dimensione della matrice è settabile dall'utente, e la casella di partenza è quella centrale. I nuovi sviluppi che mi prometto di fare sono nel P.S del precedente mio post (che magari non hai visto perchè l'ho rieditato solo ora...), che dovrebbero risolvere le difficoltà teoriche del problema, almeno spero...

[Umby2]

"panurge":

La dimensione della matrice è settabile dall'utente, e la casella di partenza è quella centrale. I nuovi sviluppi che mi prometto di fare sono nel P.S del precedente mio post (che magari non hai visto perchè l'ho rieditato solo ora...), che dovrebbero risolvere le difficoltà teoriche del problema, almeno spero...

Mi riferivo alla dimensione che hai usato nel test dove hai riscontrato i valori di media intorno al 60.
Per quanto riguarda la scelta della cella centrale, secondo me è la migliore, perchè da questa è piu' difficile incontrare i bordi (che rappresentano uno "stop" parziale della ramificazione).

[panurge]

errr, francamente non ricordo bene che valore avessi scelto... credo 50x50. Riprovandoci ora con questi parametri la media gira attorno a 57.7
Pienamente d'accordo con te sulla scelta della casella centrale.

[lukul]

Bel problemino.
Mi ricordo come tempo addietro, per gioco,mi trovavo a programmare il famoso gioco "GAME OF LIFE" di Conway .
Anche in quel caso si dovrebbe utilizzare una matrice bidimensionale di dimesione infinita ( ma sarebbe poco pratico ).
Ed allora la soluzione : .... La matrice bidimensionale può essere disposta nello spazio a mò di ciambella
(Grigori Perelmann docet).
Con una matrice toroidale l'unico problema stà nell' impostare delle condizioni al contorno idonee in maniera tale
che il tuo processo iterativo si svolge sulla superficie di uno spazio tridimensionale limitato ma senza bordi.
Buon divertimento. E mi raccomando... non demordere!!!!

[lukul]

Supponiamo che la situazione di partenza sia quella in figura: http://oi55.tinypic.com/qqnvqc.jpg .
Dalla posizione (0,0) ci si sposta
su celle dello stesso colore solo con movimenti orizzontali e verticali ma non con movimenti diagonali.
Dal momento che, come in figura, la cella (0,0) è nera non ci si potrà muovere
su quella(-1,1) ma su quelle (1,0) , (-1,-1) e (0,-1). Giusto?
E poi dovrò considerare, per proseguire il cammino, solo le celle (-2,-1), (-2,-2), (-1,-2), (0,-2), (2,0). Giusto?
Resto in attesa di una risposta per proseguire....

[Umby2]

"lukul":
Dal momento che, come in figura, la cella (0,0) è nera non ci si potrà muovere
su quella(-1,1) ma su quelle (1,0) , (-1,-1) e (0,-1). Giusto?

Direi che la cella (-1, 1) (la prima in alto a sx), pur essendo nera non andrebbe conteggiata in quanto "isolata".

"lukul":
E poi dovrò considerare, per proseguire il cammino, solo le celle (-2,-1), (-2,-2), (-1,-2), (0,-2), (2,0). Giusto?
Resto in attesa di una risposta per proseguire....

La (-2, -2) non la considererei, le altre mi sembrano corrette.

[Umby2]

"panurge":errr, francamente non ricordo bene che valore avessi scelto... credo 50x50. Riprovandoci ora con questi parametri la media gira attorno a 57.7
Pienamente d'accordo con te sulla scelta della casella centrale.

Come vedi la dimensione iniziale della matrice può portare a risultati diversi (prima parlavi di una media di 60 ora di 57)

Ti chiedo:
- Quante volte hai ripetuto la simulazione ?
- Quante simulazioni hanno "toccato il bordo" ?
- La scelta del colore iniziale l'hai stabilito in base al colore della casella di partenza ? Se non fosse così, in caso di casella iniziale non giusta, ti sei dovuto fermare subito (prima ancora di iniziare). In questo caso, hai considerato la simulazione nel calcolo della media ?

[lukul]

Ho creato una matrice random di 50*50 elementi contenente 0 ed 1.
Ho provato a colorare manualmente (conpaint) alcune regioni al suo interno
(quella blu, verde chiaro e rossa non incontrano i bordi,
mentre quella verde scuro, rosa e gialla si). Il problema a questo punto sarebbe
implementare un codice che partendo da una qualsiasi cella calcoli le aree delle
regioni colorate a patto che queste non arrivino ai bordi della matrice.
Buon divertimento...



In matlab mi è bastato fare:

a=floor(mod(randn(50,50),2));
imshow(a)

[lukul]

Ho provato, in breve tempo, ad implementere uno script Matlab (R)
per la risoluzione del problema:

close all, clear, clc

L=55;

a=floor(mod(randn(L,L),2));
imshow(a),colorbar

b=zeros(size(a)); % matrice di prova

x=1+(L/2)-.5;
y=1+(L/2)-.5;

b(x,y)=1;

iter=1;
while (iter<=10^5 | x==L-1 | y==L-1 )
    
D=a(x,y);   
A=zeros(1,4);

if a(x,y-1)==D, A(1,1)=1; end  % a sinistra
if a(x,y+1)==D, A(1,2)=1; end  % a destra
if a(x-1,y)==D, A(1,3)=1; end  % sopra
if a(x+1,y)==D, A(1,4)=1; end  % sotto

k=find(A); % trova i valori non nulli del vettore (A)

s=1+floor(mod(randn(1,1),length(k)));
K=k(s); % primo elemento di k

if K==1, y=y-1; b(x,y)=1; end
if K==2, y=y+1; b(x,y)=1; end
if K==3, x=x-1; b(x,y)=1; end
if K==4, x=x+1; b(x,y)=1; end

iter=iter+1;
end
figure(2),imshow(b), colormap(summer), colorbar

nnz(b)

Per verificarne la bontà ecco la rappresentazione grafica
di una matrice random (50*50) composta da 1 e da 0:



e l'output grafico del programma:



Il numero di caselle gialle, nella figura di sopra, è 124 (che fortuna!!!)

Ecco i valori di altri miei esperimenti:

24 4 10 77 41
32 119 58 10 27
8 78 256 37 34
66 43 8 14 13
100 89 69 35 14
112 272 9 6 37
8 63 103 12 28
60 12 18 21 46
16 51 72 8 9
67 71 71 77 9
50 5 189 27 68
13 17 6 82 10
26 120 107 42 138
88 21 90 56 13
62 52 2 2 9
196 4 52 2 31
188 28 161 5 4[/list:u:wnai0b2q]

da cui il valore medio è 52.8235 e la deviazione standard è 19.8921.
N.B. tra i valori numerici non compare 1 a causa di un problema corretto
nel codice riportato sotto.


e a questo punto mi sono un pò stancato!!!




Ecco un abbozzo di codice che itera il processo:
(n.b.: a volte lo script si arresta. Ciò accade quando si raggiungono i
bordi della matrice!)
Purtroppo ora il tempo mi è tiranno, ma spero presto di risolvere.



close all, clear, clc

L=55;
replicati=8;
prove=5;

N=zeros(replicati,prove);
for X=1:replicati
for XX=1:prove

a=floor(mod(randn(L,L),2));
% figure,imshow(a),colorbar

b=zeros(size(a)); % matrice di prova

x=1+(L/2)-.5;
y=1+(L/2)-.5;

b(x,y)=1;

iter=1;
while (iter<=10^5 | x==L-1 | y==L-1 )
    
D=a(x,y);   
A=zeros(1,4);

if a(x,y-1)==D, A(1,1)=1; end  % a sinistra
if a(x,y+1)==D, A(1,2)=1; end  % a destra
if a(x-1,y)==D, A(1,3)=1; end  % sopra
if a(x+1,y)==D, A(1,4)=1; end  % sotto

k=find(A); % trova i valori non nulli del vettore (A)

s=1+floor(mod(randn(1,1),length(k)));
if isempty(k)==1
    K=0
else
K=k(s); % primo elemento di k
end

if K==0, y=y; x=x; b(x,y)=1; end
if K==1, y=y-1; b(x,y)=1; end
if K==2, y=y+1; b(x,y)=1; end
if K==3, x=x-1; b(x,y)=1; end
if K==4, x=x+1; b(x,y)=1; end

iter=iter+1;
end
% figure,imshow(b), colormap(summer), colorbar

N(X,XX)=nnz(b);
end % prove
end % replicati



Ed ecco un caso in cui si blocca:

e l'output (alla penultima iterazione si è raggiunto il bordo):

59 2 123 5 4
76 108 27 82 24
57 8 133 58 7
50 222 48 45 4
80 1 41 43 133
86 5 232 86 121
24 120 150 41 93
1 24 113 0 0[/list:u:wnai0b2q]
Per ovviare aumentare la dimensione della matrice... ma fino a quanto???
penso non di molto.
Infatti portando la matrice a 75*75 elementi ecco altri risultati:


20 3 2 31 79
144 18 17 49 90
25 29 9 124 12
48 46 144 92 11
14 6 1 23 15
38 46 61 138 51
19 27 2 40 2
34 105 7 7 1
32 16 7 14 15
77 74 2 107 24
165 4 35 5 66
179 45 7 9 92
33 36 6 35 88
139 24 1 2 130
36 173 16 2 8[\list]
Media: 44.4533 e deviazione standard :7.8685.

Per cui il risultato corretto dovrebbe essere compreso
, come supposto dal propositore del problema,
con la confidenza del 99%, tra $ 44.4533 \pm 2.576 xx 7.8685 $.
Arrotondando l'area della regione è compresa tra 24 e 65.

In attesa di un risultato esatto oltre che approssimato (matematici al lavoro!!! ),

Vi saluto tutti con affetto augurandovi un divertente anno nuovo...

[Rggb1]

Non ho capito perché usare per forza una matrice (array bidimensionale) per fare questa simulazione; del resto, si suppone che la matrice/griglia sia infinita.

Credo sia meglio usare un metodo diretto

[fu^2]

una domanda sciocca, ma perchè l'area deve essere finita (domanda già postata nel primo messaggio della discussione)? Uno potrebb coprire su una matrice infinita un'area di pixel (come li chiami te) infinita, no? (premesso: non mi sono stato a leggere tutti i codici, ma ho visto solo i risultati delle figure postate: alcuni si interrompevano perchè era stato ragiunto il bordo)...

In tal caso la media aritmetica che state facendo voi non sarebbe finita, no?...
Tutto sommato io voto questa strada, cioè che esiste sempre almeno una distribuzione di pixel e un opportuno punto iniziale per cui l'area che si può coprire è infita. Però non ho una dimostrazione, è solo un azzardo, in questi giorni ci penso su come potrei fare (e vedere se ce la faccio).

detto questo concordo con la "politica" di Rggb

[Lord K]

Mi viene in mente una distribuzione binomiale (di Bernoulli), considerando un cammino di [tex]n[/tex] passi con probabilità di continuare pari a [tex]1/2[/tex] con infiniti lanci... risulta che il valore atteso di quella area sia [tex]\infty[/tex] anche perchè il valore atteso della binomiale è un minorante del valore che l'area percorribile.

[lukul]

Lord K: mi spiace, ma ciò che affermi contraddice i risultati numerici.

----

una domanda sciocca, ma perchè l'area deve essere finita (domanda già postata nel primo messaggio della discussione)? Uno potrebb coprire su una matrice infinita un'area di pixel (come li chiami te) infinita, no? (premesso: non mi sono stato a leggere tutti i codici, ma ho visto solo i risultati delle figure postate: alcuni si interrompevano perchè era stato ragiunto il bordo)...

fu^2: l'area "dovrebbe essere" (con elevata probabilità) finita perchè la tua matrice è binaria (consentimi questa accezione
per indicare che è composta solo dai numeri uno e da zero) e random (cioè avente una distribuzione CASUALE degli elementi)
e ti puoi muovere solo orizzontalmente e verticalmente su celle aventi lo stesso valore numerico
della cella da cui sei partito ( o 0 o 1).
Permettimi di banalizzare:

Tutto sommato io voto questa strada, cioè che esiste sempre almeno una distribuzione di pixel e un opportuno
punto iniziale per cui l'area che si può coprire è infita.

Ma a quale distribuzione ti riferisci se abbiamo detto che è random? E poi il "punto iniziale" è più logico che sia
quello centrale (a maggiore distanza dai bordi)
Supponendo la matrice come una scacchiera, i movimenti avvengono dunque solo lungo i lati delle caselle
(se queste hanno lo stesso colore) ma non lungo gli spigoli (anche se le caselle hanno lo stesso colore).
Prima o poi, con elevata probabilità , l'area che descrivi spostandoti su celle dello stesso valore
numerico si interromperà ( non potendoti muovere in diagonale ).

Per farti un esempio, ecco le aree che ho trovato in alcune simulazioni:

12 16 4 183 134
23 84 30 99 104
46 19 17 72 98
12 138 20 92 47
18 7 18 88 39
84 14 16 16 46
11 1 105 147 95
127 57 1 11 4
18 3 16 64 99
1 30 16 6 119
6 7 133 149 150
6 20 2 2 110
11 67 46 1 183
52 49 151 8 80
119 21 1 1 135
5 44 54 85 86
7 36 98 58 164[/list:u:holegd9g]

Inutile dirti che con una matrice (75*75) ci sono rarissimi casi in cui il processo si arresta
perchè si raggiunge il bordo.

[Rigel1]

A me con griglia 1000x1000 vengono medie elevate con varianze mostruose.

[lukul]

Rigel: , tu affermi che:

A me con griglia 1000x1000 vengono medie elevate con varianze mostruose.

- posta il codice che hai utilizzato per la simulazione.

[Rigel1]

Ecco il codice.

#include
#include
#include
#include


int nMinX, nMaxX, nMinY, nMaxY;
int **p;
int setcall = 0;

typedef struct { int xl, xr, y, dy; } LINESEGMENT;

#define MAXDEPTH 10000

#define PUSH(XL, XR, Y, DY) \
if( sp < stack+MAXDEPTH && Y+(DY) >= nMinX && Y+(DY) <= nMaxY ) \
{ sp->xl = XL; sp->xr = XR; sp->y = Y; sp->dy = DY; ++sp; }

#define POP(XL, XR, Y, DY) \
{ --sp; XL = sp->xl; XR = sp->xr; Y = sp->y+(DY = sp->dy); }

int GetPixel(int x, int y) {
return p[x][y];
}

void SetPixel(int x, int y, int c) {
p[x][y] = c;
setcall++;
}

// Fill background with given color

void SeedFill_4(int x, int y, int new_color)
{
int left, x1, x2, dy;
int old_color;
LINESEGMENT stack[MAXDEPTH], *sp = stack;

old_color = GetPixel(x, y);
if( old_color == new_color )
return;

if( x < nMinX || x > nMaxX || y < nMinX || y > nMaxY ) {
puts("Border");
return;
}

PUSH(x, x, y, 1); /* needed in some cases */
PUSH(x, x, y+1, -1); /* seed segment (popped 1st) */

while( sp > stack ) {
POP(x1, x2, y, dy);

for( x = x1; x >= nMinX && GetPixel(x, y) == old_color; --x )
SetPixel(x, y, new_color);

if( x >= x1 )
goto SKIP;

left = x+1;
if( left < x1 )
PUSH(y, left, x1-1, -dy); /* leak on left? */

x = x1+1;

do {
for( ; x<=nMaxX && GetPixel(x, y) == old_color; ++x )
SetPixel(x, y, new_color);

PUSH(left, x-1, y, dy);

if( x > x2+1 )
PUSH(x2+1, x-1, y, -dy); /* leak on right? */

SKIP: for( ++x; x <= x2 && GetPixel(x, y) != old_color; ++x ) {;}

left = x;
} while( x<=x2 );
}
}

int main(int argc, char *argv[]) {
// dimensione del reticolo
int d = 1000;
// numero di prove
int iter = 100;
double res[iter];

nMinX = 0;
nMaxX = d-1;
nMinY = 0;
nMaxY = d-1;

p = new int*[d];
for (int i=0; i p = new int[d];
}

// inizializza il generatore random
srand(time(0));

double s = 0, ss = 0;

for (int n = 0; n < iter; n++) {
// inizializza il reticolo con dati random fra 0 e 1
for (int i=0; i for (int j=0; j p[j] = rand() % 2;
}
}

setcall = 0;

SeedFill_4(d/2, d/2, 1 - GetPixel(d/2, d/2));

printf("%7d,", setcall);
res[n] = setcall;
s += setcall;
double s2 = setcall;
ss += s2 * s2;
}

double m = s / iter;
double var = (ss - s*s / iter) / (iter - 1);
//printf("\nSomma = %f, Somma quad = %f\n", s, ss);
printf("\nMedia = %f, varianza = %f\n", m, var);
}