Resolução de problemas/A node too far

Um nó muito distante

Imagine uma rede com um sistema de transmissão de pacotes(pequenas unidades de informação que são enviadas e recebidas pela rede) e várias estações(computadores) conectadas. De maneira que possamos evitar um looping infinito nas retransmissões de pacotes que não chegaram aos seus destinos, introduzimos uma regra chamada TTL(Time To Live). O TTL garante que os pacotes serão perdidos depois de um determinado tempo. Seria interessante, porém, que pudéssemos determinar, de acordo com as limitações do TTL, as estações que não conseguem receber tais pacotes.

O problema A node too far aborda exatamente este tema. Imagine um grafo como o da figura a seguir: [[1]] Se uma mensagem com o TTL de 2 for mandada do nó 35, os nós 15, 10, 55, 50, 40, 20 e 60 serão alcançados. Os demais não serão. A entrada do problema consiste de um número N, que indica a quantidade de conexões entre as estações(nós). Após isso, virão as descrições de N pares de nós, que representam as conexões entre tais nós. Após as descrições das arestas(conexões), virá o nó de partida dos pacotes(apenas o número do nó), acompanhado do TTL do pacote. Mais de um caso poderá acontecer para um mesmo grafo. O ponto de partida para a resolução deste problema é a determinação do tipo ao qual o problema pertence. Este problema é um problema de grafos(como deu pra ver). O segundo ponto a ser analisado é a estrutura de dados para armazenarmos o nosso grafo. Por questões de simplicidade, usaremos uma matriz de adjacências de 36x36(Dado que só teremos no máximo 30 nós por grafo).

int matriz[36][36],vetor[10001],citado[10001];

O campo vetor[10001] será responsável por setar as posições às quais vão pertencer os nós. Não atribuiremos os próprios valores dos nós porque, como vimos, podemos atribuir um rótulo inteiro arbitrário ao nó(que pode ser um número muito grande). Para suportarmos uma gama tão grande de valores, precisaríamos de uma matriz de 10000x10000! Isto, como é de se supor, causaria "Memory Limit Exceded"(e também "Time Limit Exceded", dada a complexidade do algoritmo de menor caminho que iremos usar). Mas, como só teremos no máximo 30 nós em cada grafo, não precisamos armazenar uma matriz tão grande. Basta que setemos valores menores para cada nó. O campo citado[10001] irá nos auxiliar nesta tarefa, uma vez que, cada vez que um nó é citado, é atribuído um valor entre 1 e 30 a ele. Para que não venhamos a atribuir mais de um valor a um mesmo nó, verificamos se o o elemento já foi citado.

A função a seguir atribui um "infinito" a cada valor da matriz de adjacências, de modo que possamos aplicar nosso algoritmo de menor caminho:

void infinitza() {
	int i,j;
	for (i=0;i<=35;i++) {
		for (j=0;j<=35;j++) {
			matriz[i][j]=2000000;
		}
	}
	for (i=0;i<=35;i++) {
		matriz[i][i]=0;
	}
}

A função a seguir seta 0 a todos os valores dos vetores "vetor" e "citado". No caso do vetor "citado", o 0 em uma determinada posição citado[i] indica que o elemento i ainda não foi citado pela entrada:

void zera_vetor() {
	int i;
	for (i=0;i<=10000;i++) {
		vetor[i]=0;
		citado[i]=0;
	}
}

O algoritmo de menor caminho que iremos usar é o de Floyd-Warshall:

void floyd() {
	int i,j,k;
	for (k=0;k<=35;k++) {
		for (i=0;i<=35;i++) {
			for (j=0;j<=35;j++) {
				if (matriz[i][j]>matriz[i][k]+matriz[k][j]) {
					matriz[i][j]=matriz[i][k]+matriz[k][j];
				}
			}
		}
	}
}

A próxima função será a chave para a resolução do problema. Ela irá contar quantos nós não serão alcançáveis a partir do nó X que estaremos analisando, ou seja, irá verificar quais nós tem um menor caminho para o nó X que é maior que o TTL em questão(referenciado pela variável "capacity"):

int conta(int node,int capacity) {
	int i,j,counter=0;
	for (i=0;i<=35;i++) {
		if (matriz[i][node]>capacity && citado[i]==1 && matriz[node][i]>capacity) {
			counter++;
		}
	}
	return counter;
}

A seguir, temos nossa função principal. Ela implementa todas as funções que explicamos anteiormente na ordem correta, coletando os dados de entrada e aplicando os algoritmos certos para dar a saída:

int main () {
	int nodes=-1,origem,destino,capacity=0,i,q=0,counter=1,caso=1;
	while (nodes!=0) {
		counter=1;
		infinitza();
		zera_vetor();
		scanf ("%d",&nodes);
		for (i=1;i<=nodes;i++) {
			scanf ("%d %d",&origem,&destino);
			if (vetor[origem]==0) {
				vetor[origem]=counter;
				counter++;
			}
			citado[vetor[origem]]=1;
			if (vetor[destino]==0) {
				vetor[destino]=counter;
				counter++;
			}
			citado[vetor[destino]]=1;
			if (vetor[origem] != vetor[destino]) 
				matriz[vetor[origem]][vetor[destino]]=matriz[vetor[destino]][vetor[origem]]=1;
		}
		floyd();
		origem=-1;capacity=-1;
		if (nodes!=0) {
			while (origem!=0 || capacity!=0) {
				scanf ("%d %d",&origem,&capacity);
				q=conta(vetor[origem],capacity);
				if (origem!=0 || capacity!=0) {
					printf ("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",caso,q,origem,capacity);
					caso++;
				}
			}
		}
	}
	return 0;
}

Este problema poderia ser perfeitamente resolvido com o uso do algoritmo de Dijkstra(cuja complexidade é O(n²), menor do que a de Floyd-Warshall, que é O(n³)), uma vez que precisamos apenas do menor caminho de um único nó para todos os outros. Usamos o algoritmo de Floyd-Warshall apenas por sua implementação ser mais simples.

Texto explicativo escrito por: Samuel Lincoln Magalhães Barrocas

Esta página precisa ser reciclada (discuta). Ao melhorá-la, você estará ajudando o Wikilivros.