Probabilidad Y Realidad.

Warchief · 02 de Abril de 2005, 01:30:04 PM

Saludos,

estoy trabajando en la generación de un grafo aleatorio. Todo parece ir correcto, ya lo había terminado, cuando me doy cuenta de que la probabilidad de creación de una arista y la densidad real del grafo construido así no cuadran nunca (normal, son sólo probabilidades); pero es que además, la real SIEMPRE es menor (bastante) que la probable (a pesar de que son muchos nodos).

Como muchas veces estos fallos suelen ser cosas que el propio programador no se da cuenta, a pesar de ser de lo más obvio, ¿podríais echar un vistazo a ver si conseguís descubrirme el porqué?

Por ejemplo:

Código [Seleccionar]


Sea un tablero definido como una matriz de nodos con conectividad 8:
6390 nodos => 50158 vecinos => 25079 aristas
Los ejemplos son del tipo:
Probabilidad de que esté la arista
Densidad real de aristas
Vecinos que hay(V)
    P           DR           V
86,57%  80,76%  40508
43,14%  30,51%  15302
15,99%    9,60%    4814
74,72%  65,69%  32948
...
Siempre la densidad real es menor que la probabilidad de generación (que debería dar la densidad, no?)

Sólo pongo aquí el código interesante:

METODO PARA CREAR EL GRAFO ALEATORIO:

Código [Seleccionar]



// probability = rand(); antes de llamar a este metodo

void createRandomGraph(Board* board, long probability) {	
	int i, j;

	// Connectivity 4
	if(board->getConnectivity() == 4) {
  // For every node
  for(i=0; i<board->getHeight(); i++) {
  	for(j=0; j<board->getWidth(); j++) {
    // If the sum is even
    if(!((i+j) & 1)) {
    	// Check cross
    	if(rand() < probability) board->deleteConnection(i,j, north);
    	if(rand() < probability) board->deleteConnection(i,j, south);    	
    	if(rand() < probability) board->deleteConnection(i,j, east);    	
    	if(rand() < probability) board->deleteConnection(i,j, west);    	
    }
  	}
  }
	}
	// Connectivity 8
	else {
  // For every node
  for(i=0; i<board->getHeight(); i++) {
  	for(j=0; j<board->getWidth(); j++) {
    // If the sum is even
    if(!((i+j) & 1)) {
    	// Check diagonals only
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    
    	if(rand() < probability) board->deleteConnection(i,j, southwest);    	
    }
    // If its odd
    else {
    	// Check cross
    	if(rand() < probability) board->deleteConnection(i,j, north);
    	if(rand() < probability) board->deleteConnection(i,j, south);    	
    	if(rand() < probability) board->deleteConnection(i,j, east);    	
    	if(rand() < probability) board->deleteConnection(i,j, west);    	
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    	
    	if(rand() < probability) board->deleteConnection(i,j, southwest);
    }
  	}
  }
	}
...
}

METODO QUE CALCULA LA DENSIDAD:

Código [Seleccionar]


float calculateDensity(Board* board) {
	int i,j;
	long num_neighbours=0, max_neighbours; 
	// Calculate density
	max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight();
	// substract not allowed neigbours (border)
	if(board->getConnectivity() == 4) 
  max_neighbours = max_neighbours - board->getWidth()*2 - board->getHeight()*2;
	else 
  max_neighbours = max_neighbours - board->getWidth()*6 - board->getHeight()*6 + 4;
	// count real nodes
	for( i=0; i<board->getHeight(); i++) {
  for( j=0; j<board->getWidth(); j++) {
  	num_neighbours += board->getNodeAt(i,j)->getNeighboursNumber();
  }
	}
	// et voilá
	return (((float)num_neighbours/max_neighbours)*100);
}

El invocador sería:

Código [Seleccionar]


...
p = rand();
createRandomGraph(board, p);

real = calculateDensity(board);
probable = 100-(((float)p/RAND_MAX)*100);

imprimir real y probable
...

Dónde tengo la confusión?

Gracias por echar el vistazo.

gdl · 02 de Abril de 2005, 01:47:12 PM

No entiendo tu código al 100%, pero parece que lo que haces es borrar conexiones. ¿No deberían ser los if del tipo if(rand() > probability)..?

gdl · 02 de Abril de 2005, 01:59:20 PM

Otra cosilla que he visto.

Calculas el número máximo de vecinos (aristas) como

Código [Seleccionar]

max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight();

Sin embargo, luego sólo borras en casillas alternadas

Código [Seleccionar]

// If the sum is even
   if(!((i+j) & 1)) {....

Lo que me hace sospechar que realmente el número de aristas debería ser la mitad ya que se comparte la sur de un nodo con la norte del otro, etc. <_<

Código [Seleccionar]

max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight()/2;

ethernet · 02 de Abril de 2005, 02:29:28 PM

QUOTE (gdl)

No entiendo tu código al 100%, pero parece que lo que haces es borrar conexiones. ¿No deberían ser los if del tipo if(rand() > probability)..?
[/quote]
Uhmmmmm, podría ser. Podría ser. Lo pruebo y comento.

QUOTE (gdl)

Otra cosilla que he visto.
Calculas el número máximo de vecinos (aristas) como
CODE
max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight();
Sin embargo, luego sólo borras en casillas alternadas
CODE
// If the sum is even
if(!((i+j) & 1)) {....

Lo que me hace sospechar que realmente el número de aristas debería ser la mitad ya que se comparte la sur de un nodo con la norte del otro, etc. dry.gif

CODE
max_neighbours = board->getConnectivity() * board->getWidth() * board->getHeight()/2;
[/quote]

Es una buena idea; en el código de Board::deleteConnection se llama a
node->deleteNeighbour(direction) y a
opposite->deleteNeighbour(direction)

Código [Seleccionar]


	void deleteConnection(int row, int col, TNeighbour neighbour) {
  Node* pN;
  TNeighbour opposite;
  // Need a valid cell
  assert(row >= 0 && row < height && col >= 0 && col < width);
  // delete this to neighbour connection
  nodes[row][col].deleteNeighbour(neighbour);  
  // delete neighbour to this connection  
  pN = getNeighbourPointer(row, col, neighbour, &opposite);

  if(pN != NULL) pN->deleteNeighbour(opposite);  
	}

En realidad está todo pensado en función de vecinos, sin contar aristas, ya que la información de los vecinos está duplicada como dices.

Código [Seleccionar]

enum TNeighbour {
	none      = 0,
	north   = 1,
	south   = 2,
	east   = 4,
	west   = 8,
	northeast = 16,
	northwest = 32,
	southeast = 64,
	southwest = 128,
	all    = 255	// Useful to init nodes
};

Sólo borro casillas alternas por esa razón. El procedimiento sólo decide si borrar o dejar 1 arista 1 vez. Si hiciese todas las casillas en vez de alternas, la probabilidad de borrar/dejar una artista sería p+p*p, en vez de p, ya que miraría borrar(0,0, sur) y borrar(1,0,norte), que es la misma arista.

Warchief

Visitante
En línea

Probabilidad Y Realidad.

#4

02 de Abril de 2005, 02:35:50 PM

<< No me deja editar el de antes, me sale el código html en el recuadro donde debería escribir el mensaje y no hay botones de enviar, etc :huh:>>

Añado a lo de antes.
Los nodos devuelven el número de nodos vecinos, por lo que se cuenta cada arista dos veces.

Código [Seleccionar]


	// Return number of connected neighbours
	unsigned int getNeighboursNumber() const {
  unsigned int number = 0;
  for(int i=0; i<8; i++) number = number + ((neighbours >> i) & 1);
  return number;
	}

Así que en realidad la densidad es: aristas*2/aristas_maximas*2 * 100.

Sobre si debe ser rand() > probability o rand() < probability.
probability es la probabilidad de ser borrada, por lo que está bien con "<". Pensemos en una probability de RAND_MAX. Todas las aristas serán borradas.

es por eso que al calcular la densidad esperada (probable) hago:

Código [Seleccionar]


probable = 100-(((float)p/RAND_MAX)*100); // 100 - porcentaje de borrado = densidad

Esto es correcto no?

Gracias por tu tiempo y comentarios.

Warchief

Visitante
En línea

Probabilidad Y Realidad.

#5

02 de Abril de 2005, 02:54:58 PM

Ahhh, gdl, me diste la idea de donde buscar. Creo que el fallo está claramente en:

Código [Seleccionar]


  // For every node
  for(i=0; i<board->getHeight(); i++) {
  	for(j=0; j<board->getWidth(); j++) {
    // If the sum is even
    if(!((i+j) & 1)) {
    	// Check diagonals only
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    
    	if(rand() < probability) board->deleteConnection(i,j, southwest);    	
    }
    // If its odd
    else {
    	// Check cross
    	if(rand() < probability) board->deleteConnection(i,j, north);
    	if(rand() < probability) board->deleteConnection(i,j, south);    	
    	if(rand() < probability) board->deleteConnection(i,j, east);    	
    	if(rand() < probability) board->deleteConnection(i,j, west);    	
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    	
    	if(rand() < probability) board->deleteConnection(i,j, southwest);
    }
  	}
  }

que debería ser algo como

Código [Seleccionar]


  // For every node
  for(i=0; i<board->getHeight(); i++) {
  	for(j=0; j<board->getWidth(); j++) {
    // If the sum is even
    if(!((i+j) & 1)) {
                                         IF(i&1) {
    	// Check diagonals only
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    
    	if(rand() < probability) board->deleteConnection(i,j, southwest);    	
                                        }
                                        else {
                                        // Check cross
    	if(rand() < probability) board->deleteConnection(i,j, north);
    	if(rand() < probability) board->deleteConnection(i,j, south);    	
    	if(rand() < probability) board->deleteConnection(i,j, east);    	
    	if(rand() < probability) board->deleteConnection(i,j, west);    	
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    	
    	if(rand() < probability) board->deleteConnection(i,j, southwest);
                                        }
    }
  	}
  }

Probando.

Warchief

Visitante
En línea

Probabilidad Y Realidad.

#6

02 de Abril de 2005, 03:26:55 PM

CONSEGUIDOOOOOOOOOO.

Joder q tonto estoy, por no pensar bien sobre el papel.

Código [Seleccionar]


	// Connectivity 8
	else {
  // For every node
  for(i=0; i<board->getHeight(); i++) {
  	for(j=0; j<board->getWidth(); j++) {
    // If the sum is even
    if(!((i+j) & 1)) {
    	// If row is odd
    	if(i&1) {
      // Check ****
      if(rand() < probability) board->deleteConnection(i,j, north);
      if(rand() < probability) board->deleteConnection(i,j, south);
      if(rand() < probability) board->deleteConnection(i,j, east);
      if(rand() < probability) board->deleteConnection(i,j, west);
    	}
    	// is even
    	else {
      // Check all
      if(rand() < probability) board->deleteConnection(i,j, north);
      if(rand() < probability) board->deleteConnection(i,j, south);    	
      if(rand() < probability) board->deleteConnection(i,j, east);    	
      if(rand() < probability) board->deleteConnection(i,j, west);    	
      if(rand() < probability) board->deleteConnection(i,j, northeast);    
      if(rand() < probability) board->deleteConnection(i,j, southeast);    
      if(rand() < probability) board->deleteConnection(i,j, northwest);    
      if(rand() < probability) board->deleteConnection(i,j, southwest);
    	}
    }
    // FALTABA ESTO!!!!!!!!
    else IF (i&1) {
    	if(rand() < probability) board->deleteConnection(i,j, northeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, southeast);    	
    	if(rand() < probability) board->deleteConnection(i,j, northwest);    	
    	if(rand() < probability) board->deleteConnection(i,j, southwest);
    }
  	}
  }
	}

Gracias por las notas gdl, me guiaste ;)

ethernet

Stratos
Mensajes: 3,716
Ubicación: salamanca/valladolid
En línea

Probabilidad Y Realidad.

#7

03 de Abril de 2005, 01:28:40 PM

Si quieres hacer algo medianamente serio con probabilidades no uses rand, tiene unas propiedades probabilísticas pésimas. Búscate por ahí un generador de números aleatorios decente.

saludos

http://blep.blogspot.com/

Warchief

Visitante
En línea

Probabilidad Y Realidad.

#8

03 de Abril de 2005, 02:43:17 PM

Cita de: "ethernet"Si quieres hacer algo medianamente serio con probabilidades no uses rand, tiene unas propiedades probabilísticas pésimas. Búscate por ahí un generador de números aleatorios decente.

saludos

Gracias por la nota. De momento rand me vale (Después de hacer la probabilidad tengo que reparar el grafo hacerlo sin islas y 2-connected, osea que me cargo un poco lo aletorio del comienzo, aunque esta reparación se realice también de forma aleatoria).

Con la mínima variación ya me sirve para obtener un grafo "suficientemente" distinto.

Lo único que necesito es que cada vez que se ejecute createRandomGraph se genere un grafo distinto.

Imprimir

Ir Arriba Páginas1

User actions

Foros - Stratos
► Programadores
► General Programadores (Moderador: [EX3])
► Probabilidad Y Realidad.

User actions

Imprimir

Stratos es un servicio gratuito, cuyos costes se cubren en parte con la publicidad.
Por favor, desactiva el bloqueador de anuncios en esta web para ayudar a que siga adelante.
Muchísimas gracias.

Foros