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

Anúncios

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 :/