Algoritmo Forest Fire - Percolação

[ElPatron]

Boa noite pessoal,

Estou aqui com uma dúvida em relação a um exercício que tenho para fazer de percolação.

Ora o enunciado é o seguinte:

Escreva um código para o método de queima. Use-o para verificar se uma dada configuração tem agregado

percolativo: (considerando uma rede de dimensões variáveis lx por ly)

Verifique se há ou não agregado percolativo;

Meça as seguintes quantidades:

o caminho mais curto: número de passos de tempo necessários para o fogo alcançar o outro

lado do sistema;

o número total de passos de tempo até o fogo parar completamente.

O código que elaborei é o seguinte(o problema que me está a dar é o de estar a iterar infinitamente, basicamente a correr um ciclo infinito, gostaria de perceber o porquê, e como posso alterar o mesmo para funcionar ou algum algoritmo alternativo onde isto não aconteça):

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include "latticeview.h"

using namespace std;

#define ImageWidth 1000  //image width
#define ImageHeight 1000 //image height

int main()
{

double N; //num total de sitios
double n; //num de sitios ocupados em media

//Metodo da queima
int k=1;
int j=0;
int l=0;
int cont=0; //contador de num minimo de iteracoes para se ter agregado percolativo na queima
int lx=5;
int ly=5;
int rede[lx*ly];
double p=0.59;  //prob de ocupar cada sitio
srand48(770983);



for(int x=0; x<lx; x++) //gerar forest
{
	for(int y=0; y<ly; y++)
	{
	double e=drand48();
	if(e<p)
	rede[x+y*lx]=1;
	else
	rede[x+y*lx]=0;
	}
}//fim do for forest
Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "forest.ppm");

// 0- vazio
// 1- ocupado
// 2- iniciar queima
// 3- a queimar
// 4- queimado
bool flag_aqueimar=true;
bool flag_topo=false;

for (int x=0; x<lx; x++)
{
if (rede[x]==1) // inicializou-se uma queima na primeira linha
rede[x]=2;
}
Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "int1.ppm");




while(flag_aqueimar==true)
{ //abrir while grande
k++;
cout << "iniciou o while flag aqueimar" << endl;

for(int i=0; i<=lx*ly-1; i++) //iniciar o for de modo a estabelecer um limite máximo de iterações
{ //abrir for grande



for (int y=0; y<ly; y++)  //passa de 2 p 3
{
for (int x=0; x<lx; x++)
{

if(rede[x+y*lx]==2)
rede[x+y*lx]=3;
//cout << "passou de 2 p 3" << endl;
}
} //fecho do for
Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "int2.ppm");
for (int y=0; y<ly; y++) //for vizinhos 3 passa o proprio a 2
{
for (int x=0; x<lx; x++)
{

if (rede[x+y*lx]==1)
{

if (x-1>=0) if(rede[x-1+y*lx]==3) //esquerda
rede[x+y*lx]=2;
if(x+1<lx) if(rede[x+1+y*lx]==3) //direita
rede[x+y*lx]=2;
if(y+1<ly) if(rede[x+(y+1)*lx]==3) //cima
rede[x+y*lx]=2;
if(y-1>=0) if(rede[x+(y-1)*lx]==3) //baixo
rede[x+y*lx]=2;
//cout << "se vizinho 3 fica 2" << endl;
}
}
} //fecho do for
Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "int3.ppm");

if (l==0)
{
cout << "iniciou o while flag topo" << endl;
cont++;
for (int x=0; x<lx; x++)
{
if (rede[x+(ly-1)*lx]==2)
{
cout << "há agregado percolativo" << endl;
cout << "numero minimo de iteracoes para chegar ao topo = " << cont << endl;

l=1;
break;
}
else
cout << "não se verificou agregado percolativo" << endl;
}
}

for (int y=0; y<ly; y++) //passa de 3 p 4
{
for (int x=0; x<lx; x++)
{

if(rede[x+y*lx]==3)
{
rede[x+y*lx]=4;
//cout << "passa de 3 p 4" << endl;
}
} //fecho do for
Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "int4.ppm");



for (int y=0; y<ly; y++) //for p contador de estados 2 ou 3 ainda existentes
{
for (int x=0; x<lx; x++)
{
if(rede[x+y*lx]==2 || rede[x+y*lx]==3)
j=j+1;
}
} //fecho do for
cout << j << endl;
Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "int5.ppm");
if(j==0) // quando j=0 o sistema acaba de queimar
{
flag_aqueimar=false;
cout << "Terminou a queima ao fim de " << k << " passos." << endl;
}


} //fecho do while grande
}

Print_lattice (rede, lx, ly, ImageWidth, ImageHeight, "fire.ppm");
} //fecho da main
return 0;
}

(Neste código usei uma pre-função de latice view, mas penso que o problema está no algoritmo e não estou a conseguir identificá-lo)

Muito obrigado e boa programação! 😉

Edited March 20, 2015 at 10:43 PM by apocsantos
geshi

[apocsantos]

Boa noite,

Podes disponibilizar a expressão matemática que estás a implementar ?

Já cheguei a fazer isto, mas em Netlogo e em prolog, mas não me recordo da expressão matemática que utilizei na altura. Se a memória não me andar a falhar muito, o "fogo" para quando os "nós" adjacentes estiverem fora do alcance, ou todos os "nós" estiverem queimados.

Se puderes disponibilizar a expressão, será mais fácil detectar o problema.

Cordiais cumprimentos,

Apocsantos