Kuratowski e a planaridade de grafos

Julho 14, 2012

Kazimierz Kuratowski (1896-1980) foi um matemático polonês cuja pesquisa se concentrou na área de topologia.

Ele viveu em um época e local diretamente afetados por duas guerras mundiais. Em 1913 foi estudar engenharia na Escócia mas seus estudos foram logo interrompidos devido ao início da primeira guerra. Entre 1927 e 1934 ele lecionou na politécnica de Lviv, onde frequentava a Cafeteria Escocesa, um estabelecimento famoso por ser o local onde se reuniam membros da escola de matemática de Lviv.

A partir de 1934 ele se transferiu para a Universidade de Varsóvia. Durante a segunda guerra ele passou a dar aulas clandestinamente pois a educação superior na Polônia foi proibida durante a ocupação alemã. Com a reabertura da Universidade em 1945, Kuratowski voltou a lecionar, tendo depois ocupado diversos cargos importantes e contribuído com a reconstrução da vida científica na Polônia [1].

Neste post gostaria de falar sobre um resultado obtido por Kuratowski em teoria dos grafos, mais especificamente na caracterização de grafos planares.

Grafos Planares

Grafos planares formam uma classe de grafos com a propriedade que existe algum desenho deles no plano de forma que suas arestas não se cruzem.

Exemplos de grafos planares são o K_4 (grafo completo de 4 vértices) e árvores, como mostra a Figura 1.

Figura 1: exemplo de grafos planares

Exemplos de grafos não planares são o K_5 (grafo completo de 5 vértices) e o K_{3,3} (grafo bipartido completo com ambas partições de tamanho 3), conforme a Figura 2.

Figura 2: Exemplos de grafos não-planares

Teorema de Kuratowski. Kuratowski mostrou que um grafo é planar se e somente se ele não contém um subgrafo que é uma subdivisão do K_5 e nem do K_{3,3}.

Uma subdivisão de um grafo consiste em colocar vértices “no meio” das arestas. Por exemplo, na Figura 3 temos uma subdivisão do K_{3,3} e segundo o teorema de Kuratowski, este não é um grafo planar.

Figura 3: Uma subdivisão do K_{3,3}

Característica de Euler. Grafos planares possuem a característica de Euler. Dado um desenho de um grafo planar conexo, com v vértices, e arestas e f faces, então v - e + f = 2

Grafos-moeda. (coin graphs) Comentei brevemente sobre grafos-moeda em um post sobre grafos de discos (disk graphs). Voltamos a falar dessa classe de grafos pois o teorema de Koebe diz que grafos-moeda e grafos planares são equivalentes [3].

Mais especificamente, o teorema diz que dado um grafo planar G, existe um conjunto de discos cujo grafo moeda é G. O grafo moeda de um conjunto de discos é um grafo com um vértice para cada disco e uma aresta entre dois vértices se seus discos correspondentes se tocam (lembrando que não é permitida sobreposição dos discos).

Por outro lado, dado um conjunto de discos no plano, podemos desenhar um grafo planar. Desenhe cada vértice do grafo no centro de cada disco e ligue por um segmento de reta os centros de dois discos que se tangenciam. É possível ver que o grafo desenhado é planar e ainda, todas as arestas são linhas retas.

A conclusão é que para todo grafo planar existe um desenho que utiliza apenas linhas retas para representar as arestas, que é justamente o que afirma o Teorema de Fáry.

Teste de Planaridade

Embora Kuratowski tenha dado uma caracterização bastante simples de grafos planares, não é trivial verificar essa condição para um grafo qualquer.

Foram desenvolvidos diversos algoritmos de teste de planaridade lineares no tamanho do grafo, ou seja, O(V + E) (portanto assintoticamente ótimos). O primeiro desses algoritmos a ser publicado foi desenvolvido por Hopcroft e Tarjan [4] (ganhadores do prêmio Turing em 1986).

Essa primeira versão era bastante complexa e portanto novas abordagem foram publicadas ao longo dos anos buscando um algoritmo mais simples. Um breve histórico pode ser conferido na Wikipedia.

A mais recente data de 2004 e é devida a Boyer e Myrvold [5], sobre a qual falaremos a seguir.

O Algoritmo de Boyer e Myrvold

Vamos analisar alguns conceitos chaves desse algoritmo, sem entrar em detalhes, pois o intuito do post é apenas passar uma ideia geral do algoritmo. Para mais detalhes, consulte [5, 6].

Considere um grafo G = (V, E) não direcionado. Sem perda de generalidade, vamos supor que G é conexo. Se não for, é fácil ver podemos analisar a planaridade de cada componente separadamente.

1. Busca em profundidade

Inicialmente fazemos uma busca em profundidade (DFS) sobre G, gerando a árvore da DFS, cujas arestas são denominadas arestas da árvore. As arestas que ficaram de fora são as chamadas arestas de retorno. Note que como o grafo é não direcionado, as arestas de retorno sempre unem um vértice com seu ancestral na árvore da DFS.

2. Componentes biconexas

Antes de prosseguir, vamos relembrar dois conceitos: um ponto de articulação em um grafo conexo é um vértice cuja remoção origina duas ou mais componentes conexas. Uma componente biconexa é uma componente conexa que não tem pontos de articulação.

O algoritmo sempre trabalha com as componentes biconexas do grafo, replicando o ponto de articulação em cada uma delas. Note que em uma árvore, todo nó interno é um ponto de articulação e portanto inicialmente temos uma componente biconexa para cada aresta da árvore. Denotaremos esse grafo intermediário de \tilde G.

3. Adição das arestas de retorno

O restante do algoritmo consiste basicamente em adicionar as arestas de retorno uma a uma sempre garantindo que não haja cruzamento delas ou caso contrário conclui que o grafo não é planar. A ideia central é deixar “livres” os vértices que ainda têm arestas por adicionar.

Os vértices são então processados em ordem contrária a que foram processados na DFS. Assim, os filhos são sempre processados antes do pai na árvore da DFS. Consideremos então o processamento de um vértice v. Vamos adicionar as arestas de retorno de v a seus descendentes.

4. Aglutinação das componentes

Ao adicionar uma aresta de retorno, duas ou mais componentes biconexas podem ser aglutinadas. No exemplo da Figura 4, a inclusão da aresta de retorno (v, w) fará com que as duas componentes da Figura 4 (c) se tornem uma única componente, como pode ser observado na Figura 4 (d).

Figura 4: (a) Grafo real; (b) r é um ponto de articulação pois sua remoção gera duas componentes; (c) representamos as componentes biconexas; (d) ao adicionar a aresta de retorno (v, w) é preciso inverter a componente inferior para que a aresta (x, y) possa ser adicionada posteriomente.

5. Espelhamento das componentes

Outra operação necessária é a chamada espelhamento de uma componente biconexa. Voltando ao exemplo da Figura 4, temos que a aresta (x, y) será adicionada posteriormente (supondo que x é ancestral de v na árvore da DFS).

Porém, se adicionarmos a aresta (v, w) no grafo da Figura 4 (c), isolaremos x de y (note que não podemos “passar” a aresta entre r e sua cópia porque as componentes serão aglutinadas). Uma alternativa é “espelhar” a componente inferior como é feito na Figura 4 (d). Desta forma, os vértices x e y ainda podem ser conectados por uma aresta.

6. Ordem de adição das arestas de retorno

Como dissemos, o algoritmo itera sobre os vértices na ordem inversa da que foram processados pela DFS. Porém, um vértice v pode ter mais de uma aresta de retorno a adicionar a seus descendentes. Qual a ordem em que essas arestas devem ser adicionadas?

O algoritmo executa uma outra busca em profundidade a partir de v percorrendo apenas os vértices que estão na face externa e vai adicionando as arestas conforme vai encontrando os vértices com os quais v tem arestas de retorno a adicionar.

Se a busca terminar sem ter adicionado todas as arestas de retorno de v, então o grafo não é planar.

Conclusão

Esse algoritmo é bastante complicado e usa muitos truques para alcançar a complexidade linear no tamanho do grafo de entrada. Para quem tem mais interesse nos detalhes do algoritmo, pode consultar o artigo original [5]. Para detalhes de implementação, é possível estudar o código-fonte desse algoritmo da biblioteca de grafos da Boost [7].

No problema atacado durante meu mestrado, usamos uma ideia parecida com essa de trabalhar com componentes biconexas com o ponto de articulação replicado em cada uma delas. Mais especificamente, na tentativa de diminuir o tamanho das instâncias de entrada, fizemos a decomposição em componentes biconexas que podem ser resolvidas de maneira independente. Comentei sobre essa estratégia em um post anterior.

Referências

[1] Wikipédia – Kazimierz Kuratowski
[2] Wikipedia – Planarity Testing
[3] Kontaktprobleme der konformen Abbildung – Koebe P.
[4] Efficient Planarity Testing – Hopcroft J., Tarjan R.
[5] On the cutting edge: Simplified O(n) Planarity by Edge Addition – Boyer, Myrvold. (pdf)
[6] Dr Dobbs: Planarity By Edge Addition
[7] Boost: Boyer-Myrvold Planarity Testing


SRM 527

Dezembro 25, 2011

Depois de quase 5 anos competindo no Topcoder, finalmente meu rating ficou amarelo (+1500) \o/. Entretanto, não acredito que eu vá sustentar essa cor por muito tempo.

Como de costume comecei pelo problema fácil (275). Como não consegui pensar em nenhuma solução além de uma força-bruta complicada e como a pontuação do problema médio estava menor do que o de costume (450 contra 500), resolvi lê-lo. Então vamos começar por ele.

P8XMatrixRecovery

(Enunciado do problema)

Minha primeira ideia foi modelar como emparelhamento bipartido máximo de custo mínimo, mas não estava conseguindo modelar a função objetivo.

Depois de pensar mais, acabei lembrando de uma técnica que consiste em fixar um parâmetro do problema visando simplificá-lo. Um caso especial dessa técnica é o uso de busca binária num problema de otimização para transformá-lo em um problema de decisão.

Um problema que me lembro que pode ser resolvido com a técnica mais geral é o seguinte: encontrar o emparelhamento máximo de um grafo bipartido de forma que se minimize o custo da aresta de maior custo (a versão clássica do emparelhamento máximo de custo mínimo seria minimizar a soma dos custos das arestas).

A solução é, para cada possível custo de aresta C, criar um subgrafo G' contendo apenas as arestas de custo menores ou iguais a C. A resposta será o menor C para o qual existe um emparelhamento máximo em G'.

No problema em questão, podemos ter várias permutações de colunas que mapeiam uma matriz na outra, por causa dos caracteres coringas (‘?’). Entretanto, o problema pede a lexicograficamente menor. A ideia é fixar o primeiro caractere ‘?’ em ‘0’ e verificar se ainda existe um mapeamento.

Se sim, então podemos manter o caractere em ‘0’ e proceder para o próximo caractere ‘?’. Caso contrário, não existe nenhum mapeamento com ‘0’ e como o enunciado diz que sempre existe uma solução, então tem que existir alguma com ‘1’ e portanto podemos trocar para esse valor. Fazendo isso para todo caractere ‘?’ encontraremos a matriz lexicograficamente menor.

Para decidir se existe um mapeamento podemos resolver o problema do emparelhamento máximo bipartido. Criamos duas partições com vértices correspondendo a cada coluna de cada matriz. Adicionamos uma aresta entre dois vértices se as colunas correspondentes são iguais. Note que o “igual” nesse caso deve levar em conta que ‘?’ é igual a ‘?’, ‘0’ ou ‘1’. Se houver um emparelhamento perfeito, significa que existe uma bijeção entre as colunas das duas matrizes.

O emparelhamento máximo bipartido pode ser resolvido através do algoritmo de caminhos de aumento (augmenting paths) com complexidade O(NM) onde N é o número de vértices e M é o número de arestas.

Note que devemos resolver o problema do emparelhamento para cada ‘?’. No pior caso podemos ter matrizes só com ‘?’ (N^2) e nesse caso o grafo bipartido teria O(N^2) arestas, levando a uma complexidade total O(N^5). No problema o valor de N era igual a 30. Eu achei que ia estourar, mas minha solução acabou passando (código no github).

P8XGraphBuilder

(Enunciado do problema)

Depois que resolvi o problema médio, voltei a pensar na solução para esse problema. Cheguei a pensar na seguinte proposição:

Proposição: Dado um vetor de N elementos com valores maiores ou iguais a 1 e de tal forma que a soma desses elementos seja 2(N-1), é possível construir uma árvore de N vértices, de forma que exista uma correspondência entre os graus dos vértices e os elementos desse vetor.

Por exemplo, se N = 4, temos os vetores [3, 1, 1, 1] e [2, 2, 1, 1] e suas permutações. Dado um vetor, seu custo é dado pela soma dos pesos de seus elementos. O problema original então se reduz a encontrar o maior custo de um vetor satisfazendo as restrições da proposição.

É possível resolver esse novo problema através de programação dinâmica. Podemos definir C(n, s) como a melhor solução de um vetor de n elementos e somando exatamente s. A recorrência fica:

C(n, s) = \max_{d=1}^{N-1} C(n - 1, s - d) + b(d)

Onde b(d) é o valor do elemento d (dado pelo vetor scores). A base é quando n = 0. Nesse caso, se s = 0, temos 0, caso contrário não existe solução e retornamos -\infty.

Durante a prova, não tinha cheguei a provar a proposição, mas ela me pareceu correta. Mas infelizmente não tive tempo de implementar essa solução, que agora adicionei ao github.

Pra fins de completude, vou apresentar agora a prova da proposição.

Prova: Primeiro, sem perda de generalidade, vamos supor que os elementos do vetor estão ordenados em ordem não-crescente. Vamos usar um argumento construtivo. Dado um vetor v = \{d_1, d_2, \cdots, d_N\}, seja k o número de elementos com valor maior ou igual a 2. Crie um nó raíz com d_1 filhos. Faça um desses filhos ter d_2 - 1 filhos, um dos “netos” ter d_3 - 1 filhos e assim sucessivamente, até um nó ter d_k - 1 filhos.

Por exemplo, dado o vetor v = {4,4,3,1,1,1,1,1,1,1} construímos a árvore da figura abaixo.

Árvore com graus {4,4,3,1,1,1,1,1,1,1}

Temos uma árvore onde k nós têm grau igual aos primeiros k elementos de v e o resto dos nós têm grau 1. Resta provar que o número desses nós de grau 1 é exatamente N - k, ou equivalentemente, que essa árvore tem N nós. É fácil ver que o número de filhos “gerados” é a soma d_1 + (d_2 - 1) + (d_3 - 1) + \cdots + (d_k - 1) = (\sum_{i = 1}^k d_i) - k + 1.

O único vértice que não foi contado acima foi a raíz, então se N' é o número de nós da árvore gerada, temos N' = (\sum_{i = 1}^k d_i) - k + 2.

Usando a restrição de que o vetor deve somar 2(N-1), com um pouco de álgebra:

\sum_{i = 1}^k d_i + \sum_{i = k+1}^N d_i = 2N - 2

\sum_{i = 1}^k d_i + (N-k) = 2N - 2

Concluímos que N = (\sum_{i = 1}^k d_i) - k + 2 e que N' = N


Google Code Jam 2011

Setembro 18, 2011

O Google Code Jam é uma competição de algoritmos anual promovida pelo Google, que acontece desde 2007 se não me engano. Esse ano eu fui até o round 2, mas acabei não me classificando entre os 500 primeiros para avançar ao round 3:( Entretanto, acabei ganhando um prêmio de consolação por ter ficado entre os 1000 primeiros, que é a camiseta do evento.

Camiseta (frente)

Embora a competição tenha acabado em Julho, a camiseta só chegou a algumas semanas. O desenho na parte de trás são linhas de código em diversas linguagens de programação e tem o formato do Japão que é onde foi a final mundial, na qual o japonês Makoto Soejima (rng_58 no topcoder) sagrou-se vencedor.

Detalhe da parte de trás

Com a chegada da camiseta, lembrei que eu tinha ficado de estudar a solução dos problemas do round 2 que eu não havia conseguido resolver. Felizmente os problem setters apresentam a solução, mas também vou descrevê-las aqui do meu jeito.

C. Expensive Dinner

O enunciado desse problema está aqui. A solução está baseada em três proposições principais.

Proposição 1: Dado um grupo de amigos x_1, x_2, \dots, x_i, o valor da conta é sempre LCM(x_1, x_2, \dots, x_i) não importa a ordem em que eles cheguem. LCM representa o mínimo múltiplo comum.

Prova: Seja y o valor da conta.

Parte 1 – mostrar que y \ge LCM(x_1, x_2, \dots, x_i)
Essa parte é direta, dada a definição de mínimo múltiplo comum e que a conta tem que ser divisível por todo x_i.

Parte 2 – mostrar que y \le LCM(x_1, x_2, \dots, x_i)
Quando um amigo x_i pede alguma coisa, o valor da conta vai para o próximo múltiplo de x_i. Como LCM(x_1, x_2, \dots, x_i) é múltiplo de todos, o valor da conta não poderá “pular” esse valor e uma vez que esteja nesse valor, todos estarão satisfeitos e a conta não irá mais aumentar.

Juntando as partes 1 e 2, provamos a proposição.

Seja M o número de vezes que o garçon é chamado e M_{\max} e M_{\min} o maior e o menor valor possível de M, respectivamente. O problema pede M_{\max} - M_{\min}. Sejam p_1, p_2, \dots, p_P os P primos menores ou iguais a n (o número de amigos). Além do mais, seja e_i o maior inteiro tal que p_i^{e_i} \le n.

Proposição 2: M_{\max} = 1 + \sum_{i=1}^P{e_i}

Prova: vamos quebrar em duas partes novamente.

Parte 1 – mostrar que M_{\max} \ge 1 + \sum_{i=1}^P{e_i}
Para isso basta exibir um caso onde M = 1 + \sum_{i=1}^P{e_i}. Esse é o caso em que os amigos chegam na ordem 1, 2, \dots, n. Considere a chegada de x_i tal que x_i = p_i^k. É fácil ver que LCM(x_1, x_2, \dots, x_{i-1}) não é divisível por p_i^k e portanto o garçon terá de ser chamado. Quantos x_i existem satisfazendo x_i = p_i^k? Justamente \sum_{i=1}^P{e_i}. Além disso, quando x_1 = 1 chegar a primeira vez, o garçon também deverá ser chamado. Portanto, o número de vezes que o garçon foi chamado é pelo menos 1 + \sum_{i=1}^P{e_i}

Parte 2 – mostrar que M_{\max} \le 1 + \sum_{i=1}^{e_i}
Pela Proposição 1, o valor final da conta deverá ser LCM(x_1, x_2, \dots, x_n), que é igual a \prod_{i=1}^P p^{e_i}. Para qualquer ordem de amigos, temos LCM(x_1, x_2, \dots, x_i) = k \cdot LCM(x_1, x_2, \dots, x_{i-1}) para um inteiro k. É fácil ver que se um garçon for chamado, então k > 1, ou seja, estamos aumentando a potência que algum fator primo até chegarmos em \prod_{i=1}^P p^{e_i}, logo o garçon não pode ser chamado mais do que o número total de fatores na conta final, ou seja, \sum_{i=1}^{e_i} (+1 por causa da primeira chamada).

Juntando as partes 1 e 2, provamos a proposição.

Proposição 3: M_{\min} = P

Prova: vamos quebrar em duas partes novamente.

Parte 1 – M_{\min} \le P
Para isso basta exibir um caso onde M = P. Considere uma ordem onde os P primeiros amigos a entrarem são exatamente aqueles iguais a p_i^{e_i} para todo i = 1, \dots, P. É fácil ver que depois que eles entratem, o valor da conta será já LCM(x_1, x_2, \dots, x_n) e todo mundo que entrar depois já estará satisfeito, tendo o garçon sido chamado apenas P vezes.

Parte 2 – M_{\min} \ge P
Vamos por contradição: suponha que existe uma ordem de P-1 ou menos amigos tal que LCM(x_1, x_2, \dots, x_{P-1}) = LCM(x_1, x_2, \dots, x_n) = \prod_{i=1}^P p^{e_i}. Note que, para cada p_i, deve existir um amigo com fator p_i^{e_i} (caso contrário o LCM seria menor). Pelo princípio das casas dos pombos, como existem apenas P-1 amigos e P primos, há de haver algum amigo múltiplo de p_i^{e_i} e p_j^{e_j}. Entretanto, ambos p_i^{e_i} e p_j^{e_j} são maiores que \sqrt{n}. Isso implica que esse amigo tem valor maior que n, uma contradição.

Juntando as partes 1 e 2, provamos a proposição.

Dadas essas proposições, o problema se reduz a calcular (1 + \sum_{i=1}^P {e_i}) - P para todo primo P \le n. Considerando que podemos calcular e_i em O(\log(n)), levando a um algoritmo O(n \log(n)). Porém, como n pode ser até 10^{12}, temos que fazer melhor.

A sacada é reescrever a equação como 1 + \sum_{i=1}^P ({e_i} - 1). Isso quer dizer que só estamos interessados em fatores primos com potências maiores que 1. Logo, podemos nos restringir a primos menores ou iguais a \sqrt{n}, levando a um algoritmo O(\sqrt{n} \log(n)).

Depois dessa teoria toda, o algoritmo fica bem simples. Aqui está minha versão em C++, usando o crivo de eratóstenes para encontrar os primos.

D. A.I. War

Este problema se reduz para o seguinte problema: Dado um grafo G(V, E), encontrar o menor caminho entre s e t em um grafo não-direcionado e não-ponderado. Se houver várias soluções, escolha o caminho com maior vizinhança. Consideramos a vizinhança de um caminho como a união das vizinhanças dos vértices desse caminho, excluindo os vértices do próprio caminho. O problema pede para imprimir o comprimento desse caminho e o tamanho de sua vizinhança.

Vamos denotar por N o número de vértices nesse grafo e M o número de arestas.

Primeiramente encontramos as menores distâncias a partir de s, para todos os vértices, através de uma busca em largura. Denotamos por dist(v) a menor distância de s a v. O tamanho do menor caminho é dist(t).

Construímos então um grafo direcionado G' = (V, A), com mesmo conjunto de vértices do grafo de entrada e um arco (u, v) \in A se a dist(u) + 1 = dist(v). Podemos argumentar que todo caminho mínimo s-t no grafo original corresponde a um caminho direcionado de s a t nesse novo grafo.

Solução para o caso pequeno: podemos fazer uma força bruta a partir de s e, sempre que chegarmos em t, calculamos o tamanho da vizinhança desse caminho. Dessa forma estamos enumerando explicitamente todos os possíveis menores caminhos. Fiz uma estimativa e me pareceu que no pior caso, haverá cerca de O(\sqrt{N}^{\sqrt{N}}) caminhos. No caso fácil, P=36, o que dá uma ordem de 50k operações. No caso difícil, P=400, o que torna a abordagem inviável. De qualquer maneira, eis aqui minha solução para o caso fácil.

Solução para o caso geral: uma ideia é usar programação dinâmica para guardar o tamanho da vizinhança para um dado caminho, mas note que não basta representar um caminho por seu último vértice, pois ao adicionar um vértice a este caminho, sua contribuição para o tamanho da vizinhança pode depender de mais vértices nesse caminho.

A observação chave é que na verdade, a contribuição de um novo vértice c só depende do último e penúltimo vértice desse caminho. Para entender porque, suponha que dist(c) = D + 1 e sejam b e a o último e penúltimo vértices de um caminho, respectivamente. Então dist(b) = D e dist(a) = D-1. Se c possuísse vizinhança comum com algum vértice x tal que dist(x) \le D-2, então o menor caminho até c seria menor ou igual a D, uma contradição.

Logo, é suficiente representar um caminho por seus dois últimos vértices. Seja f(b, c) o tamanho da maior vizinhança de um caminho terminado em b \rightarrow c. Podemos definir a seguinte recorrência:

f(b, c) = \max \{ (a, b) \in A(G') | f(a, b) + g(c, a, b) \}

Aqui, g(c, a, b) é o número de vértices na vizinhança de c que não está contido nem na vizinhança de a nem na de b. O caso base é f(s, c), onde o valor é simplesmente o tamanho da união da vizinhança de s e c.

Se pré-computarmos g(c, a, b), podemos resolver a recorrência acima em O(N) e como cada par (b, c) deve pertencer a A(G'), o algoritmo tem complexidade O(NM).

Porém, calcular g(c, a, b) é a parte mais demorada. A solução mais simples seria enumerar todas as triplas de vértices e processar cada vértice v vizinhança de c, levando a um algoritmo O(N^4), o que dá na ordem de 25 \times 10^9, que é muito lento.

A sacada é usar o fato que c e v devem ser adjacentes, assim como os vértices a e b. Assim, para cada par de arestas e_1 e e_2, supomos e_1 = (c, v) e e_2 = (a, b). Usando uma matriz de adjacência, podemos verificar se v pertence à vizinhança de a e b em O(1), levando a uma complexidade total de O(M^2) ~4M operações. O editorial do Google Code Jam apresenta essa e outras 3 alternativas para pré-computar g(c, a, b). Minha implementação da solução apresentada se encontra aqui.


Mapas de símbolos proporcionais e a meia integralidade da cobertura de vértices

Julho 31, 2011

O problema que ataquei no mestrado consistia em achar uma ordem de empilhamento entre símbolos em um mapa, de modo a maximizar uma dada função objetivo. Não se sabe a complexidade desse problema e por isso usei programação linear inteira.

Há uma variante desse problema, que consiste em maximizar uma outra função objetivo, para a qual existe um algoritmo polinomial.

Depois de obter as soluções para o meu problema, precisei fazer uma comparação entre as soluções desses dois problemas. Aconteceu que a diferença visual entre as duas soluções não é tão perceptível, sendo que apenas alguns discos estão em posição diferente. Para se ter uma idea, veja um dos casos


Jogo dos 7 erros ;) (clique na imagem para aumentar)

Decidi fazer um programa para destacar apenas os discos que mudaram de lugar. A minha primeira ideia foi marcar todos os discos que estavam em níveis diferentes entre as duas soluções.

Isso não funciona bem quando temos duas componentes disjuntas de discos, por exemplo na figura abaixo, com duas componentes disjuntas {A, B, C} e {D, E}. Note que as ordens {A > B > C > D > E} e {D > E > A > B > C} resultam visualmente na mesma figura, embora nenhum disco esteja exatamente na mesma posição na ordenação e portanto o programa vai marcar todos os discos.

Desenho que pode ser representado por mais de uma ordem dos discos

Uma segunda ideia foi marcar, considerando todos os pares de discos que se interceptam, apenas aqueles em que a ordem relativa do par foi invertida. Com essa estratégia, nenhum disco do exemplo acima seria destacado, o que está de acordo com nossas expectativas.

Porém, essa abordagem ainda apresenta um efeito indesejável. Se tivermos uma pilha de discos, onde todos se interceptam e um disco que está no topo em uma solução aparece na base na outra, sendo que todos os outros discos permaneceram intactos, como por exemplo {A > B > C > D} e {B > C > D > A}, ainda assim todos os discos serão destacados pois todos os pares formados com A tiveram sua ordem relativa invertida. Note que seria suficientemente informativo destacar apenas o disco A.

Assim, para todo par de discos que se intercepta, basta destacarmos um deles. Como então destacar o menor número possível para diminuir a poluição visual?

Se olharmos para o grafo de discos desse problema, existem algumas arestas que queremos destacar (cobrir), usando pelo menos um dos vértices mas tentando minimizar a quantidade desses vértices. Soa familiar?

Sim, reduzimos para o problema da cobertura de vértices (vertex cover).

Cobertura de vértices

O problema da cobertura de (arestas por) vértices é sabidamente NP-difícil. Assim, é pouco provável um algoritmo polinomial para resolvê-lo de maneira ótima. No meu trabalho, usei uma heurística simples: percorra os vértices começando por aqueles de maior grau. Se todas as arestas incidentes a esse vértice já foram cobertas por algum vértice da cobertura, ignore-o. Caso contrário adicione-o à cobertura.

Aplicando esse algoritmo nas figuras do começo do post, ficamos com o seguinte resultado:

Ficou mais fácil encontrar as diferenças entre as soluções (clique na imagem para aumentar)

Esse método ainda tem um problema que é quando um par de discos tem sua ordem relativa trocada, mas a parte que foi visualmente modificada está encoberta por um outro disco. Um exemplo disso pode ser visto no canto inferior direito da figura acima. Para consertar esse problema teríamos que fazer um pré-processamento e só considerar vértices cujos discos têm alguma parte do seu borda diferente entre uma solução e outra.

Modelo de programação linear

Como não poderia deixar de ser, apresento aqui o modelo de programação linear inteira da versão mais geral desse problema, na qual os vértices têm um custo associado. Dado um grafo G = (V, E) com uma função de custo c : V \rightarrow \mathbb{R}^+, definimos a variável binária x_v para cada v \in V, que vale 1 se o vértice v está na cobertura e 0 caso contrário. O modelo então fica:

Sujeito a

(1) Para todo (u, v) \in E,

(2) Para todo v \in V,

Meia integralidade

O modelo apresentado tem uma propriedade interessante chamada de meia-integralidade. Isso quer dizer que, dada a relaxação linear desse modelo, existe uma solução ótima onde os valores das variáveis x_v são 0, 1/2 ou 1. A prova é relativamente curta e está descrita na Seção 14.3 de [1].

Assim, dada uma solução fracionária do modelo, podemos usar a técnica de arredondamento, criando uma solução x'_v com x'_v = 1 sempre que x_v \ge 1/2. É possível mostrar que essa solução é uma cobertura de vértices válida e que seu custo não é maior do que 2 vezes o valor da solução ótima, resultando em um algoritmo 2-aproximado.

Referências

[1] Approximation Algorithms – Vijay V. Vazirani (2003)


Formulações do TSP

Março 4, 2011

O problema do caixeiro viajante (do inglês Traveling Salesman Problem, abreviado como TSP) é o problema mais conhecido e estudado em otimização combinatória. Creio que alguns dos motivos para isso seja sua definição simples, sua dificuldade e sua aplicabilidade prática.

A definição é de fato simples. Imagine que você tem n cidades e entre cada par de cidades existe uma rodovia com uma dada distância. Você deseja partir de uma das cidades, percorrer as outras exatamente uma vez e então retornar para a cidade de origem de forma a minimizar a distância percorrida. Em termos de teoria de grafos, dado um grafo completo de n vértices e custo nas arestas, encontrar um ciclo com exatamente n vértices de menor custo.

O TSP é conhecidamente NP-difícil. Porém, entre os problemas NP-difíceis, há ainda uma diferença na dificuldade entre eles. Algoritmos de aproximação podem dar uma noção dessa diferença. Alguns problemas admitem algoritmos com fatores de aproximação arbitrariamente próximos de 1, enquanto outros não admitem sequer fator de aproximação constante.

O problema da mochila por exemplo, é um dos problemas NP-difíceis mais “tratáveis”. Ele pertence à classe dos PTAS (Polynomial Time Approximation Scheme), o que significa que ele pode ser aproximado por um fator tão próximo de 1 quanto se queira, embora o tempo de execução aumente em função dessa proximidade. Por outro lado, a versão geral do TSP não pode ser aproximada por um fator constante a menos que P = NP. Por isso, o algoritmo do TSP é um dos problemas mais difíceis da computação, embora afirma-se que abelhas saibam resolvê-lo.

Formulações

Há pelo menos três formulações de programação linear inteira para esse problema. Uma delas foi publicada em 1960, por Miller, Tucker e Zemlin e que denominaremos MTZ, é baseada em fluxos em redes. Considere um grafo direcionado completo D(V, A) de n nós e custo nas arestas. Seja uma variável binária que vale 1 se a aresta (i,j) está na solução, e 0 caso contrário. Denotando o custo de uma aresta (i,j) por , a função objetivo é simplesmente

Como queremos encontrar um ciclo que passe por todos os vértices, cada vértice deve ter exatamente uma aresta entrando e outra saindo, o que é gatantido com as seguintes restrições

(1) Para todo

(2) Para todo

Somente com essas restrições, as soluções serão coberturas de vértices por ciclos, ou seja, teremos um ou mais ciclos de forma que cada vértice estará contido em exatamente um ciclo. A ideia dos autores de [1] é introduzir variáveis representando potenciais de um vértice v. Sempre que uma aresta (i,j) é usada, o potencial do vértice j tem que ser maior do que i. Isso criará um impedimento na criação de ciclos, da mesma maneira do modelo para o caminho mais longo, conforme esse post anterior.

Porém, isso também impedirá a formação do ciclo que estamos procurando. O truque é não usar essa restrição sobre um dos vértices, por exemplo o vértice 1. Dessa forma as desigualdades impedirão quaisquer soluções que contenham subciclos que não incluam o vértice 1. As únicas soluções que satisfarão isso, além de (1) e (2), são os ciclos de tamanho n. A desigualdade fica,

(3) Para todo

Onde M é uma constante suficientemente grande. Se , a desigualdade fica redundante. Se , forçamos .

A segunda que vamos apresentar é devido a Dantzig, Fulkerson e Johnson, ou DFJ. O modelo possui as variáveis e as restrições (1) e (2). A diferença fica por conta da eliminação de subciclos.

(4) Para todo

É possível mostrar que se, para um subconjunto não-próprio S de V, existem |S| ou mais arestas, então existe pelo menos um ciclo. O problema é que o número de desigualdades (4) é exponencial e para isso um algoritmo de planos de corte, como o Branch and Cut, deve ser usado. Uma maneira de reduzir o número dessas desigualdades é observar que se uma solução satisfaz (1) e (2) e existe um subciclo de tamanho maior do que |S|/2, então existe um subciclo de tamanho menor do que |S|/2, de forma que podemos considerar as desigualdades (4) apenas para

Uma outra maneira de se eliminar subciclos é através das desigualdade chamadas cut set constraints, dadas por

(5) Para todo

A ideia aqui é que dada uma cobertura por ciclos contendo subciclos, existe uma maneira de separar o conjunto de vértices em 2, de forma que cada subciclo fique exatamente de um dos lados, ou seja, nenhum aresta “cruza” essa partição. Note que o número de desigualdades (5) também é exponencial.

Conclusão

Embora o modelo MTZ tenha sido desenvolvido depois do DFJ, e tenha um número polinomial de desigualdades, na prática o DFJ é bem mais eficiente. A explicação pode ser dada pela combinatória poliédrica, já que é possível mostrar que o modelo DFJ está contido no MTZ. Em um post futuro, pretendo apresentar um esboço dessa prova.

Uma questão que surgiu ao estudar as formulações é a relação entre os modelos com a desigualdade (4) e (5). Serão eles equivalentes? Um está contido no outro? Essa é outra pergunta que pretendo pesquisar.

Referências

[1] Miller, Tucker and Zemlin — Integer Programming Formulation of Traveling Salesman Problems
[2] Dantzig, Fulkerson and Johnson — Solution of a Large-Scale Traveling-Salesman Problem


Topcoder: SRM 495

Fevereiro 13, 2011

O post era pra ter saído na Sexta, mas acabou atrasando :/ Bom, hoje vou comentar sobre os problemas não resolvidos durante o SRM 495. Consegui fazer o fácil de 300 pontos, mas demorei bastante tempo e tive que ressubmeter. Aí meu rating acabou caindo.

Carrot Boxes

Descrição. Há N caixas numeradas de 0 a N-1. Todas as caixas, exceto uma, possuem uma cenoura. Deseja-se descobrir a caixa vazia sem abri-la.

Algumas caixas possuem informações sobre o conteúdo de outras caixas e essa informações são conhecidas a priori. É dado um vetor<string> information, onde o j-ésimo caractere da i-ésima string é ‘Y’ se abrir a i-ésima vai revelar se a j-ésima caixa contém ou não uma cenoura, ou ‘N’ caso contrário.

Retornar a maior probabilidade para descobrir a caixa vazia sem ter que abri-la. (Texto original)

O autor do editorial descreveu a solução desse problema de forma tão bem detalhada e exemplificada que nem vale a pena explicar do meu jeito. Implementei a solução descrita em C++. Uma coisa que achei legal da solução é que se você pode se dar ao luxo de rodar um Floyd-Warshall O(n^3), depois fica bem simples determinar componentes fortemente conexas.

Strange Elevator

Descrição resumida. Considere um prédio de H andares e um elevador formado por N compartimentos (não necessariamente consecutivos). Quando parado, cada parte fica em um andar distinto e quando o elevador se move, todas as partes movem junto. Cada andar deve ser coberto por exatamente um compartimento do elevador. (Texto original)

Podemos representar um elevador pelos andares em que cada compartimento está, quando o compartimento mais baixo está no primeiro andar (denotado aqui por nível 0). Por exemplo, se H = 6 e N = 3, os elevadores (0, 2, 4) e (1, 3, 5) são respectivamente:

O problema pede para, dados N e H, encontrar quantos elevadores válidos podem ser formados. Para H = 6 e N = 3, há duas possibilidades, (0, 2, 4) e (0, 1, 2). Observe que (0, 2, 3) não é válido, pois o elevador, ao subir um andar, irá para os andares (1, 3, 4) e o andar 3 terá sido coberto por dois compartimentos diferentes.

Solução. Está bem detalhada no editorial, então vou tentar resumir aqui.

Proposição 1: Definimos como bloco um conjunto contínuo de compartimentos. Em um dado elevador, todos os blocos têm mesmo tamanho L.

Proposição 2: O espaço de separação entre dois blocos consecutivos é múltiplo de L.

A ideia básica das provas das duas proposições acima é que se elas não forem verdade, então necessariamente algum andar será coberto por mais de um compartimento ou algum andar não será coberto.

Problemas de contagem geralmente envolvem algum tipo de programação dinâmica (exceto quando existe uma fórmula fechada). De fato, a solução apresentada divide a matriz de PD em duas partes: C1(H, N) e Cn(H, N) a primeira corresponde ao número de elevadores válidos para um prédio de H andares e N caixas quando os blocos têm tamanho L = 1, enquanto a segunda quando os blocos têm tamanho L > 1.

A sacada do problema consiste em definir a relação de recorrência. A primeira observação é um corolário das Proposições 1 e 2: Como os blocos têm tamanho L e os espaços têm tamanho múltiplos de L, então H deve ser múltiplo de L. Dado isso, podemos “escalar” o problema dividindo todas as dimensões por L. Ou seja, o número de elevadores válidos para H andares, N caixas e blocos de tamanho L, é o mesmo para H/L andares, N/L caixas e blocos unitários. Logo, podemos definir a recorrência de Cn(H, N) da seguinte forma:

(1)

Para definir a recorrência de C1(H, N) é mais complicado. Considere o vetor offbox que representa o offset dos compartimentos (boxes), ou seja, é o andar que cada compartimento ocupa quando o compartimento mais embaixo está no primeiro andar. Esse vetor tem tamanho N. Seja offlift o offset do elevador, ou seja, é o andar ocupado pelo compartimento mais embaixo. Esse vetor tem tamanho H/N que é o número de vezes que um elevador com N caixas pára.

Observe que se o elevador é válido, então para todo andar a, existe exatamente um par (i, j) tal que a = offbox[i] + offlift[j] e que esses dois vetores caracterizam unicamente um dado elevador. É fácil ver que se offbox e offlift representam um elevador válido para H andares e N caixas, trocando os papéis deles, vai gerar um elevador, denotado por dual, válido com H andares e H/N caixas.

Considere então um elevador com blocos de tamanho 1. Temos que offbox[0] = 0 e offbox[1] > 1, já que a primeira e a segunda caixa não podem estar contíguas. Além do mais, o primeiro compartimento é o único capaz de visitar o segundo andar, ou seja o elevador deve parar também no primeiro andar e offlift[1] = 1. Trocando os papeis dos vetores, temos offbox[0] = 0 e offbox[1] = 1, ou seja, é um elevedor com L > 1. Assim, todo elevador para H andares, com N caixas e L = 1, corresponde a um elevador para H andares, H/N caixas e L > 1.

Exemplo de configurações duais. O primeiro é offbox = {0, 2, 4} e offlift = {0, 1}. O segundo é offbox = {0, 1} e offlift = {0, 2, 4}.

Por outro lado, é fácil ver que todo elevador para H andares, H/N caixas e L > 1, corresponde a um elevador para H andares, N caixas e L = 1. Lembrando que cada um desses vetores caracteriza unicamente um elevador, não é difícil de acreditar que há uma bijeção entre essas duas configurações, o que equivale a afirmar que o número de elevadores válidos em cada uma delas é exatamente o mesmo, permitindo finalmente que escrevamos a recorrência de C1(H, N)

(2)

Como H e N sempre diminuem, as recorrências em (1) e (2) são suficientes para resolver o problema que é simplesmente C1(H, N) + Cn(H, N).

Ainda está faltando o caso base. Como H começa maior do que N e nunca diminuímos H mais do que N, fica claro que H não chegará em 1 antes de N. Logo, basta tratar o caso em que N = 1. Só há um possível elevador para N = 1 com blocos de tamanho 1 e claramente não existem elevadores com N = 1 para blocos de tamanho maior do que 1.

Outro cuidado que devemos tomar é que só existe solução se N dividir H, então precisamos fazer essa verificação antes de rodar o algoritmo.

Finalmente, um detalhe sobre a implementação. A princípio a complexidade parece ser O(HN*div(N)), onde div(N) são os divisores de N, que é essencialmente O(sqrt(N)). Porém, como H e N são da ordem de 1000000000 (10^9), essa abordagem parece impraticável.

Por outro lado, note que quando chamamos Cn(H, N), apenas os O(sqrt(N)) divisores de N serão chamados e serão divididos por pelo menos um fator de 2. Sinceramente, não sei calcular uma complexidade mais justa, mas olhando por cima, parece que não serão chamadas muitas combinações de H e N.

Além do mais, podemos otimizar o algoritmo usando memoização. No caso usual usaríamos os valores de H e N para indexar uma matriz. Aqui, entretanto, não é possível devido à magnitude dos valores. Supondo um número pequeno de combinações H e N, podemos usar um mapa usando como chave o par (H, N) (map<pair<int, int> > da STL).

Minha implementação em C++ está disponível aqui.


Topcoder: SRM 492

Janeiro 14, 2011

Topcoder é uma empresa que realiza diversos tipos de competições de programação. A mais famosa, de longe, é o SRM (Single Round Match), uma competição rápida de algoritmos. Além dessa, há competições de design e desenvolvimento de software, além das competições longas de algoritmos (Marathon Matches). Veja o site para mais informações.

O SRM é dividido em 3 fases: código, desafio e testes do sistema. A fase de código dura 75 minutos e consiste em resolver 3 problemas estilo maratona de programação. A diferença é que você submete no escuro, ou seja, sem saber se seu programa passou nos casos de testes do sistema. A fase de desafio te dá uma oportunidade de ganhar uns pontos extras fornecendo casos de teste que possivelmente quebre o código do oponente e dura 10 minutos. Depois disso, os programas de cada competidor são submetidos aos testes do sistema. Tem vários detalhes sobre pontuação que podem ser encontrados aqui .

Eu participo dos SRM’s desde 2007, mas sempre de maneira esporádica. Agora que me aposentei da maratona, decidi continuar praticando para não enferrujar (embora eu ainda programe bastante no meu mestrado). Uma coisa que eu deveria fazer mas nunca tive disciplina suficiente, é o post mortem da competição, ou seja, estudar os editoriais e aprender a fazer os problemas que não consegui durante a competição.

Minha ideia é tentar usar o blog para escrever sobre tais problemas. Sem mais delongas, vou apresentar uma breve descrição e a solução dos problemas que não consegui resolver.

Time Traveling Tour

Dado um grafo ponderado e não-orientado G e uma lista de cidades L, deseja-se encontrar um passeio iniciado no vértice 0, que visite as cidades na ordem em que aparecem em L (o passeio pode conter cidades intermediárias que não necessariamente são visitadas). Há um diferencial porém: nesse passeio você pode viajar no tempo e voltar a uma cidade pela qual já passou, com custo zero. Queremos o passeio de menor custo. Link para o problema.

Se não houvesse essa viagem do tempo o problema seria fácil: ache o menor caminho entre todos os pares de vértices e some a distância entre cidades consecutivas de L.

A solução do editorial, descreve um algoritmo de programação dinâmica. O estado é definido por uma tripla (C, i, j), que representa o menor custo de se sair da cidade C e visitar as cidades L[i], …, L[j]. A resposta do problema é dada por (0, 0, |L|-1).

A sacada dessa abordagem é que não importa qual o caminho feito até chegarmos em C. Vamos inverter o pensamento: podemos ir a uma cidade D e então voltar para a cidade C com custo zero. Logo, a partir de uma dada cidade C, iremos usar outras cidades para visitar trechos de i, … j.

Considere o exemplo abaixo, onde as cidades são identificadas por letras e os números indicam a ordem em que devem ser visitadas. A cidade de partida é ‘A’.

Exemplo: letras são rótulos do vértices; números sobre os vértices representam a ordem em que devem ser visitados; os números em azul sobre as arestas representam os custos.

Podemos ver que uma solução ótima é a seguinte: vai de A a B com custo 3 e visita B, vai então até D com custo 2. Volta no tempo para A e visita C com custo 3. Volta no tempo para A e vai até E com custo 8. O total fica 16.

Em termos da tripla, poderíamos representar (A, 0, 3) como {dist(A, B) + (B, 0, 1)} + {dist(A, C) + (C, 2, 2)} + {dist(A, B) + (B, 3, 3)}. Por sua vez, (B, 0, 1) = (B, 0, 0) + {dist(B, D) + (D, 1, 1)}. A base da recursão é quando i = j ou i > j. No primeiro caso, (C, i, j) = dist(C, L[i]). No segundo significa que já visitamos todas as cidades então (C, i, j) = 0.

Uma observação importante é que {dist(A, B) + (B, 0, 1)} + {dist(A, C) + (C, 2, 2)} + {dist(A, B) + (B, 3, 3)} pode ser reescrita como

(1) {dist(A, B) + (B, 0, 1)} + (A, 2, 3),

pois (A, 2, 3) será recursivamente decomposto até que eventualmente a primeira forma apareça.

Isso reduz nosso trabalho a encontrar uma cidade (no exemplo é B) e um índice k, tal que essa cidade vai visitar as cidades i, …, k. A recorrência então fica:

(C, i, j) = INF
Para cada cidade D :
  Para cada índice k = i ... j :
      (C, i, j) = min {(C, i, j), 
                    dist(C, D) + (D, i, k) + (C, k+1, j)

Há dois problemas: essa recorrência pode ser muito ineficiente para os limites do problema, já que o número de operações fica O(50^5). Outro problema é quando k = j. Nesse caso teremos uma recorrência cíclica, pois chamaremos (D, i, j) que por sua vez pode chamar (C, i, j) novamente.

A solução do competidor those trata esses dois problemas. Note que só precisamos considerar o caso k = j porque pode existir uma cidade para a qual não se volta com a máquina do tempo. Então definimos uma segunda tripla {C, i, j} que corresponde ao menor custo de se visitar as cidades i e j, só que necessariamente voltando no tempo para C pelo menos uma vez.

Como sabemos que {C, i, j} voltará ao menos uma vez usando a máquina do tempo, podemos quebrá-lo em duas partes (antes e depois dessa volta):

(2) {C, i, j} = min{(C, i, k) + (C, k + 1, j)} para algum k = i … j – 1

Agora (C, i, k) e (C, k + 1, j) podem ou “delegar” a tarefa de visitar as cidades i a j para outras cidades ou ele mesmo quebrar em mais pedaços (que seria o equivalente a delegar a tarefa para a própria cidade C).

A recorrência de (C, i, j) fica assim:

(3) (C, i, j) = min{ {D, i, j} + dist(C, D)} para alguma cidade D

Observe que essa abordagem elimina a recorrência cíclica e de quebra reduz a complexidade para O(50^4). O trecho que calcula essa recorrência é o seguinte:

i64 eval2(int C, int i, int j){ 
  if (pd2[C][i][j] != -1) return pd2[C][i][j]; 
  pd2[C][i][j] = INFLL; 
  for(int k=i; k<j; k++)
    pd2[C][i][j] = min(pd2[C][i][j], eval(C, i, k)+ 
                        eval(C,k+1, j));
  return pd2[C][i][j]; 
} 
i64 eval(int C, int i, int j){ 
  if (pd[C][i][j]!=-1) return pd[C][i][j]; 
  if (i == j) return dist[C][L[i]]; 
  pd[C][i][j] = INFINITY; 
  for(int D=0; D<n; D++) 
    pd[C][i][j] = min(pd[C][i][j], dist[C][D]+
                      eval2(D, i, j)); 
  return pd[C][i][j]; 
} 

Sendo que a resposta do problema é dada por eval(0, 0, |L|-1).

A minha ideia era postar uma explicação para o problema mais difícil também, o TimeTravellingGogo. Porém, achei tão difícil e levei tanto tempo para pegar a ideia do problema TimeTravellingTour que desanimei. O próprio autor dos problemas disse que eles estavam bem difíceis. Tanto que somente uma pessoa acertou o problema de 1000 pontos.

É incrível que 31 pessoas tenham acertado o problema TimeTravellingTour! Isso quer dizer que eles tiveram a ideia e implementaram corretamente em 75 minutos! Eu lendo o editorial levei umas 2 semanas só para entender a ideia :/


Hooligan

Novembro 12, 2010

Na final brasileira da maratona de programação de 2009, caiu um problema relacionado a futebol, chamado Hooligan, cujo enunciado pode ser acessado aqui.

Vou tentar resumi-lo. Temos um campeonato onde todos os times se enfrentam exatamente k vezes. Em um campeonato por pontos corridos, como o Brasileirão, temos k=2. Porém, diferentemente de um campeonato normal, vitória vale 2 pontos (e não 3), empate 1 e derrota 0. Imagine agora que estamos a certa altura do campeonato e algumas partidas já foram jogadas. A pergunta é: existe uma combinação dos resultados dos jogos restantes que fará com que o time para o qual estamos torcendo, seja não somente o campeão, mas que também tenha mais pontos que o segundo colocado?

Esse problema pode ser modelado como fluxo em redes e resolvido com um algoritmo de fluxo máximo. No dia da prova pensamos em modelá-lo dessa forma, mas não conseguimos chegar a um modelo correto.

Fluxo em redes

A primeira coisa a se fazer, é processar as partidas já realizadas, computando os pontos de cada time de acordo com a regra. Depois, observamos que, sem perda de generalidade, podemos fazer o nosso time predileto ganhar todas as partidas que lhe restam.

Seja o número total de pontos que nosso time tem após todas essas considerações. Observe que é a melhor pontuação que o nosso time pode obter. Porém, para que ele ganhe o campeonato, dependemos da pontuação dos outros times. Queremos uma combinação de jogos em que nenhum dos times restantes tenha mais do que pontos.

Se, mesmo antes de considerar os jogos não realizados, já houver time com ou mais pontos, não há o que fazer. Consideremos então que todos os times têm no máximo pontos. Seja o número de pontos do time i. Queremos que um time i ganhe no máximo pontos com as próximas partidas.

Vamos definir nosso grafo. Crie um nó para cada partida restante e um nó para cada time, além dos vértices fonte e destino, s e t, respectivamente. Para cada partida p, crie uma aresta (s, p) com capacidade 2, que representa o total de pontos que aquela partida vale. Além do mais, sejam u e v os times envolvidos na partida p. Crie uma aresta (p,u) e (p,v), ambas com capacidade 2. Finalmente, para cada time i, crie uma aresta (i, t) com capacidade .

Modelagem de uma partida entre os times u e v.

Afirmamos que existe uma combinação de resultados tal que nosso time de escolha fique em primeiro lugar isolado, se e somente se, o fluxo máximo na grafo definido acima for exatamente igual a 2*npr onde npr é o número de partidas restantes.

Prova: Observe que se o fluxo máximo for 2*npr, todas as arestas que saem de s estarão saturadas, ou seja, estará passando 2 unidades de fluxo. Temos duas arestas saindo de cada partida p. Sejam fu e fv a quantidade de fluxo nessas arestas respectivamente. Dadas as 2 unidades de fluxo chegando em p, as possíveis saídas (fu, fv) são (2, 0), (1, 1) ou (0, 2), sendo que cada uma dessas possibilidades representa um possível resultado de jogo. Já para cada time i, a quantidade de fluxo que chega no seu vértice correspondente a partir de uma dada partida p, é a quantidade de pontos que ganhou com aquela partida. Por conseguinte, a quantidade de fluxo que sai dele é o total de pontos conquistados. Note que, devido à capacidade da aresta, estamos limitando a quantidade de pontos que um dado time pode ganhar. Assim, se o fluxo é 2*npr, significa que conseguimos distribuir os pontos das partidas restantes entre os times, de forma que nenhum deles alcance nosso time predileto.

Além disso, dada uma combinação de resultados das partidas, é fácil construir um fluxo máximo de tamanho 2*npr.

Modelagem de um time.

Uma otimização para que o grafo não fique muito grande é: se existem k’ partidas restantes entre os times u e v, ao invés de criar k’ nós, criamos apenas um, mas multiplicamos as capacidades das arestas de entrada e saída por k’.

Observe que o sistema de pontuação foi modificado para que essa modelagem fosse possível. Se a vitória valesse 3, não conseguiríamos modelar as pontuações (3, 0), (1, 1) e (0, 3).

Algoritmo Guloso

Alguns maratonistas implementaram uma solução gulosa, que foi aceita no site nuevo portal.

A ideia é a seguinte. Computamos os pontos dos jogos já ocorridos e também assumimos que o time escolhido ganha o restante de seus jogos. Além disso, assumimos, a princípio, que todos os outros times empatam seus jogos.

O passo guloso é assim: Verificamos se o nosso time está na liderança isolada. Se sim, então temos uma combinação de resultados válida. Caso contrário, selecionamos o primeiro colocado x (ou algum que esteja dividindo a liderança com nosso time) e o time pior classificado y que tinha inicialmente um jogo não jogado com x. Desfazemos o empate entre x e y e fazemos x perder pra y. Reordenamos os times com essa nova pontuação e repetimos o passo. Se não houver tal y, declaramos que não existe nenhuma configuração de jogos que leve à situação desejada.

Pensei em um contra-exemplo que pode estragar essa estratégia se nenhum cuidado adicional for tomado. Considere 7 times, A, B, C, D, E, F e G, sendo que estamos torcendo pelo time A. Suponha que k=1, e já tiveram vários jogos de forma que só restam as partidas: (B,E), (B,F), (C,E) e (D,E) e que A, B, C, D têm 7 pontos, F e G têm 5 e E tem 4 (depois de considerados os empates dos jogos restantes).

Imagine que o algoritmo selecione B para perder de E (que é o pior classificado), ficando B com 6 pontos e E com 5. Agora suponha que ele selecione C, que necessariamente tem que perder para E (é a única partida que lhe resta). C tem 6 e E tem 6. O único time que está empatado com A é o D, que só pode perder para E, fazendo com que D tenha 6 e E tenha 7. Agora E passa a ficar empatado com A, mas como E não tem mais jogos, o algoritmo vai acusar que não há solução.

Tabelas de classificação ao longo da execução do algoritmo guloso.

Porém, se B perder para F ao invés de E e tanto C quanto D perderem para E, todos esses times ficam com 6 pontos e A ficará na liderança isolada.

Tabelas de classificação ao longo da estratégia ótima.

Uma pergunta é: o resultado que eu usei como contra-exemplo pode ser obtido com alguma combinação de jogos? Eu fiz na mão e aparentemente dá sim. Tive inclusive que adicionar o vértice G para a conta bater :P (note que ele não é usado no contra-exemplo).

Porém, essa é uma pergunta que pode ser respondida com uma modelagem por fluxo em rede e uma consequente redução ao problema do fluxo máximo, usando as ideias do modelo apresentado anteriormente.


Disk Graphs

Outubro 1, 2010

Semana passada teve início a série de seminários em teoria de computação dos membros do Laboratório de Otimização e Combinatória. Essas palestras ocorrerão intercaladas com os seminários do DTC (Departamento de Teoria de Computação), ocorrendo, a priori, às Sextas-feitas, 10h. Acabei estreando essa série com uma palestra intitulada “Disk Graphs”. A ideia central era definir a classe de grafos chamada disk graphs e mostrar dois problemas clássicos de teoria dos grafos sobre essa classe: o problema da clique máxima e da coloração. Neste post, vou apresentar um pequeno resumo da apresentação (disponível aqui).

Dado um conjunto de discos no plano, definimos um grafo com vértices correspondendo aos centros dos discos. Dois vértices são conectados por uma aresta se seus discos correspondentes se interceptam com área não nula. Denominamos tal grafo Disk Graph (DG).

Exemplo de Disk Graph

Um Disk Graph onde todos os discos têm mesmo tamanho é chamado de Unit Disk Graph.

Exemplo de Unit Disk Graph

No caso particular em que os discos não podem se sobrepor, apenas se tangenciar, chamamos o DG de Coin Graph (CG).

Exemplo de um Coin Graph

Em seguida falei sobre a relação entre diferentes classes de grafos. A mais interessante é devido ao Teorema de Koebe (também conhecido como circle packing theorem) que diz basicamente que grafos planares e coin graphs são equivalentes. Eu desconfiava que todo grafo planar é também um disk graph. O prof. Stolfi, que estava presente, provou com um argumento bem simples: dado um coin graph, a menor distância entre bordos de discos que não se tangenciam é positiva, enquanto a de discos que se tangenciam é exatamente 0. Assim, existe um valor suficientemente pequeno do qual podemos aumentar o raio dos discos de forma que os círculos tangentes passem a ter interseção não nula e os não tangentes assim continuem.

Problemas

Um aspecto importante ao enunciar um problema para essa classe de grafos é especificar se a entrada é dada na forma de discos ou na forma de grafo. Observe que se for dada na primeira forma, conseguimos obter a segunda. Porém, mesmo para unit disk graphs, se a entrada estiver na forma de grafo, foi provado que é NP-difícil encontrar um conjunto de discos que formem tal grafo [1]. (Para coin graphs existe um algoritmo que constrói o conjunto de discos a partir de um grafo planar [2]). Para os problemas apresentados, vamos assumir que a entrada é dada na forma de discos.

Primeiramente apresentei o problema da clique máxima para unit disk graphs. Embora seja NP-difícil encontrar a clique máxima em um grafo geral, para unit disk graphs, existe um algoritmo polinomial . Não se sabe, porém, se o problema da clique máxima para disk graphs está em P ou NP.

Depois apresentei o problema da coloração, que continua NP-difícil, mesmo para unit disk graphs e a entrada sendo dada na forma de discos. Foram desenvolvidos algoritmos aproximados e algoritmos online para unit disk graphs e disk graphs. Para unit disk graphs o melhor algoritmo aproximado até agora tem fator de aproximação 3 (limite superior), sendo que não existe algoritmo aproximado com melhor fator de aproximação menor do que 4/3 (limite inferior) a não ser que P=NP. O melhor algoritmo online tem fator de competitividade 5 (limite superior) e não existe algoritmo com fator de competitividade menor do que 2 (limite inferior) a menos que P=NP. Para disk graphs, o algoritmo aproximado tem limites inferior e superior iguais a 4/3 e 5, respectivamente, e o algoritmo online tem ambos limites inferior e superior iguais a log n, ou seja, o algoritmo online para unit disk graphs é o melhor que se pode conseguir.

Sumário com os limites dos fatores de aproximação e competitividade.

Aplicações

Na palestra acabei não falando das aplicações práticas dos disks graphs. Porém, eles são muito utilizados para projetar topologias de rede wireless. Podemos pensar que cada disco representa uma antena wireless posicionada no centro do disco, com alcance equivalente ao raio do mesmo. Assim, o problema da coloração pode ser usado para encontrar uma atribuição de frequências às antenas, considerando que há interferência entre os sinais de antenas cujos círculos se interceptam.

Referências

[1] Breu, H. and Kirkpatrick, D. G. – Unit Disk graph recognition is NP-Hard
[2] Collins, C. R. and K, Stephenson – A Circle packing algorithm


Dijkstra e o caminho máximo

Agosto 13, 2010

O problema do caminho mínimo é um dos problemas mais conhecidos da computação. Nesse post, vou comentar um pouco sobre o problema do caminho mínimo e também do caminho máximo, apresentando modelos de PLI para ambos. Para simplificar, vou considerar apenas as instâncias onde o grafo é direcionado e os pesos nas arestas são positivos.

O problema dos caminhos mínimos pode ser modelado como fluxo em redes. Mais especificamente, pode ser reduzido para o problema do fluxo de custo mínimo. Assim, existe naturalmente um algoritmo polinomial para resolvê-lo. Porém, da mesma forma que existem algoritmos combinatórios para o fluxo máximo e o fluxo de custo mínimo, o algoritmo de Dijkstra resolve o problema dos caminhos mínimos de maneira muito eficiente. O algoritmo foi desenvolvido por Edsger Dijkstra em 1956 tomando café em um bar. Disse o autor em uma entrevista que levou 20 minutos para desenvolver um dos algoritmos mais famosos do mundo da computação.

Claramente um algoritmo que resolva o problema dos caminhos mínimos através de programação linear não será capaz de bater a eficiência do algoritmo de Dijkstra. Mas, para fins de modelagem, vou apresentar o modelo PLI desse problema. A redução para o problema do fluxo máximo de custo mínimo é simples: basta fazer com que o fluxo máximo seja igual a 1. O modelo completo fica:

(1) Para cada nó v do grafo que não a fonte ou o sorvedouro,

(2) Para cada aresta (ij),

(3) Para cada aresta (ij),

(4)

Desta forma, temos que todo vale 0 ou 1. Devido à conservação do fluxo, as arestas com formam um caminho de s a t. Além do mais, o valor da função objetivo consiste em minimizar o custo das arestas desse caminho, justamente a definição do menor caminho.

Caminho de custo máximo

Um problema semelhante ao do caminho de menor custo é o problema do caminho de maior custo. Uma possível aplicação para esse problema é a técnica de planejamento CPM (Critical Path Method). O CPM consiste em construir um grafo direcionado com vértices correspondendo às atividades e arestas representando as dependências entre elas (ou seja, se existe uma aresta a->b, então b só pode ser executada depois que a terminar). A cada atividade está associado um custo, que é seu tempo de execução. Observe que aqui, o custo está associado a um vértice, e não a uma aresta. Isso pode ser resolvido através de uma modificação no grafo: para cada vértice v, substitua-o por vértice v’ e v’, com uma aresta v’-> v”com o custo igual ao do vértice. Para toda aresta (v,u), criamos a aresta (v”,u) e para toda aresta (u,v), criamos a aresta (u,v’) (veja a figura abaixo).

Split de um vértice para transformar custo do vértice em custo da aresta

Outra característica desse grafo é que ele é acíclico. Assim, é possível resolvê-lo em tempo polinimial através de programação dinâmica. Porém, para um grafo geral, o problema do caminho máximo é NP-completo.

Há uma característica que garante a integralidade (ou seja, que a solução do PL coincide com a do PLI) de modelos de programação linear, que é chamada de unimodularidade total. Se a matriz de coeficientes das restrições de um programa linear satisfizer certas condições, ela é dita totalmente unimodular. Isso implica que o problema que foi modelado com esse programa linear pode ser resolvido em tempo polinomial. Dois exemplos de matrizes que possuem essa estrutura são as matrizes de coeficientes dos PL’s do problema do fluxo máximo e do fluxo máximo de custo mínimo. Isso quer dizer que a matriz do PL do caminho de custo mínimo é unimodular. À primeira vista, isso parece implicar que o problema do caminho máximo pode ser resolvido em tempo polinomial, já que é só mudar a função objetivo de minimização pra maximização e, já que não modificamos a matriz de restrições, a unimodularidade total é mantida.

O problema é que não basta apenas modificar a função objetivo para que o PL resolva o problema do caminho de custo máximo. Se fizermos apenas isso, vão aparecer ciclos direcionados de custo positivo, disjuntos do caminho de s a t, já que queremos maximizar a função objetivo. Na figura abaixo, as arestas coloridas formam uma solução viável, já que ciclos (em vermelho) respeitam a conservação de fluxo. Supondo que a capacidade das arestas seja 1, o custo total da solução abaixo é 51; O maior caminho nesse grafo tem custo 33, que é maior do que o caminho encontrado em verde (ou seja, não basta jogar fora os ciclos encontrados). No problema do caminho mínimo eles não vão aparecer e por isso o modelo é válido.

Uma solução viável para o modelo com maximização

Assim, é preciso usar restrições que eliminem ciclos, o que faz com que a matriz de restrições deixe de ser totalmente unimodular. Para eliminá-los, definimos variáveis auxiliares, , associadas aos vértices. A seguinte restrição, elimina ciclos direcionados:

(5) Para cada aresta (i,j), seja M um número suficientemente grande

Se passa fluxo por uma aresta, a restrição fica,

O que implica que . Caso contrário, a desigualdade fica,

que é sempre satisfeita, tornando-a redundante.

Para ver que tal desigualdade elimina ciclos, considere um ciclo direcionado no grafo com os vértices na seguinte ordem (repeti o último vértice para explicitar que é um ciclo), corforme a figura seguinte.

Ciclo direcionado

Se houver fluxo passando por esse ciclo direcionado, a desigualdade (5) vai forçar que , ou seja , o que não pode acontecer. É fácil ver que tal desigualdade não impede a formação do caminho s-t. Basta ir atribuindo valores crescentes para u ao longo do caminho.