Resolução de problemas/The perspectographer

The Perspectographer - 10661

The Perspectographer

O Problema

Perspectographer é uma rudimentar máquina. Suas partes (ou pedaços) podem se sobrepor. Por exemplo, na figura temos três pedaços A, B, C. A e C se sobrepoem, assim como B e C. Dois pedaços que se sobrepoem devem estar obrigatoriamente em níveis diferentes. Nosso problema consiste em computar o menor número possível de níveis que devem ser usados para construir a máquina descrita. Por exemplo, para a figura nós precisamos de 2 níveis: um para C, e outro para A e B.

Possível Solução

Note que este problema pode ser resolvido usando-se um grafo. Calcular o número mínimo de níveis é o mesmo que calcular o número mínimo de cores para se colorir o grafo, pois não existirão vértices vizinhos com a mesma cor, assim como não existirão pedaços sobrepostos no mesmo nível. Então nosso problema se resume a coloriro grafo em questão.

O Algoritmo

Esta função faz a coloração do grafo, sempre iniciando do vértice com maior número de vizinhos não coloridos.

 int colorir(vector< vector<unsigned> > & grafo)
 {
 	vector<int> cor(grafo.size(), -1);
 	int c = 0;
 	bool ok;
 
 	for (int v = maiorGrau(grafo, cor); v != -1; v = maiorGrau(grafo, cor))
 	{
 		ok = true;
 		for (int k = 0; k <= c; ++k)
 		{
 			ok = true;
 			for (unsigned u = 0; u < grafo.size(); ++u)
 			{
 				if (grafo[v][u] == 1 && cor[u] == k)
 				{
 					ok = false;
 					break;
 				}
 			}
 			if (ok)
 			{
 				cor[v] = k;
 				break;
 			}
 		}
 		if (!ok)
 		{
 			c++;
 			cor[v] = c;
 		}
 	}
 
 	return c + 1;
 }

Note que o algoritmo em questão usa funções auxiliares.

Temoas a função: maiorGrau
Retorna o vértice com maior número de vizinhos não coloridos.

 int maiorGrau(const vector< vector<unsigned> > & grafo, vector<int> cor)
 {
 	unsigned maior;
 	int ind = -1;
 
 	for (unsigned i = 0; i < cor.size(); ++i)
 	{
 		if (cor[i] == -1)
 		{
 			ind = i;
 			break;
 		}
 	}
 	if (ind != -1)
 	{
 		maior = nbVizNotColor(grafo, cor, ind);
 		for (unsigned i = ind + 1; i < cor.size(); ++i)
 		{
 			unsigned nb = nbVizNotColor(grafo, cor, i);
 			if (nb > maior && cor[i] == -1)
 			{
 				maior = nb;
 				ind = i;
 			}
 		}
 	}
 
 	return ind;
 }

Temoas a função: nbVizNotColor
Retorna o número de vizinhos não coloridos.

 unsigned nbVizNotColor(const vector< vector<unsigned> > & grafo, const vector<int> & cor, unsigned v)
 {
 	unsigned j = 0;
 
 	for (unsigned i = 0; i < grafo.size(); ++i)
 	{
 		if (grafo[v][i] == 1 && cor[i] == -1)
 			++j;
 	}
 
 	return j;
 }

Para Resolver o problema basta montar o grafo e chamar a função colorir(grafo), ela irá retornar o número de cores mínima.

Observações

Cuidado com os algoritmos usados para calcular o número mínimo de cores de um grafo, o problema em questão requer uma solução ótima e você pode encontrar algoritmos que calculem soluções próximas da ótima. Muitas vezes isso é feito para se ganhar eficiência.

---

Veja esse problema em: Perspectographer