Resolução de problemas/The perspectographer
The Perspectographer - 10661
The Perspectographer
editarO Problema
editarPerspectographer é 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
editarNote 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
editarEsta 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
editarCuidado 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