Introdução a Guava – Revista Java Magazine 104

Junho 24, 2012

Este mês foi publicada na revista Java Magazine uma matéria que escrevi sobre o projeto Guava. O mais legal é que o convite foi feito por causa dos posts sobre Java que escrevi aqui no blog.

Basicamente o Guava é composto por um conjunto de bibliotecas que visam simplificar a vida do desenvolvedor. Ela foi inicialmente desenvolvida pelo Google e depois teve seu código-fonte disponibilizado.

No artigo descrevemos um probleminha simples e apresentamos uma solução que utiliza diversas bibliotecas do Guava. Usamos uma extensão da Collections do SDK, utilitários para estruturas de dados do SDK como List e Map, novas estruturas de dados como muli-mapas, manipulação de String e IO, funções que visam tornar expressões matemáticas mais legíveis, etc. Na solução também aplicamos um paradigma funcional para demonstrar o uso das classes Function e Predicate que podem simplificar e melhorar a legibilidade do código.

O conteúdo completo é restrito a assinantes, mas uma prévia está disponível aqui.

Acabei deixando alguns componentes do Guava de fora como Cache, Concorrência e EventBus, mas algum dia pretendo estudá-los.

Conclusão

Embora a escrita de um artigo para uma revista tome mais tempo que a de um post do blog, o conteúdo fica com uma qualidade melhor porque passa por revisão. Além disso, aprendi um assunto que eu vinha querendo estudar faz um tempo. Enfim, gostei da experiência e pretendo escrever novos artigos.

Anúncios

Leitura e escrita de dados em Haskell

Junho 17, 2012

Hoje vamos comentar sobre leitura e escrita de dados em Haskell. A minha principal referência é o Capítulo 7 do livro “Real World Haskell“.

Começamos com um exemplo bem simples que lê e escreve na saída padrão:

-- hello.hs
main = do
     putStrLn "Entre com seu nome:"
     inpStr <- getLine
     putStrLn ("Ola " ++ inpStr)

Para rodá-la podemos fazer :load hello.hs seguido de main no ghci ou runghc hello.hs no próprio terminal ou gerar um executável com ghc hello.hs.

Aqui já temos diversos conceitos novos. Primeiramente temos as funções de leitura e escrita, respectivamente getLine e putStrLn.

Vamos analisar a assinatura de tipos dessas funções:

putStrLn :: String -> IO ()
getLine :: IO String

Os tipos IO () e IO String representam uma ação de IO. Um jeito de interpretá-los é como sendo um invólucro (wrapper) para um tipo. Assim, IO String é um invólucro para o tipo String e IO () é um invólucro para um vazio.

Entrada e saída de dados são tarefas intrinsecamente não-puras, pois em uma chamada para leitura de dados (p.e. usando getLine) nem sempre retornará o mesmo resultado e uma escrita dos dados (p.e. usando putStrLn) possui efeitos colaterais externos.

Haskell sendo uma linguagem puramente funcional, faz uso de ações para poder lidar com tarefas não-puras. Futuramente, quando for falar sobre Mónades, pretendo explicar melhor sobre isso.

Seguindo com a interpretação do exemplo, temos o operador “<-“. Ele é uma maneira de executar uma ação, “extraindo” o seu conteúdo. Nesse caso, estamos “extraindo” a String lida com o getLine e atribuindo à variável inpStr.

Temos também o operador return, que encapsula um tipo em uma action, sendo o oposto do operador “<-” e não deve ser confundido com a palavra-chave de mesmo nome em linguagens imperativas.

O seguinte exemplo demonstra o encapsulamento de uma String em uma action, seguida da extração da mesma.

main = do
     inpStr <- return "Encapsulando e extraindo mensagem"
     putStrLn inpStr

O bloco definido pela palavra-chave do pode ser reescrito como uma sequência de operações ligadas por operadores do tipo “>>” e “>>=“. Analisando as assinaturas de tipos desses operadores temos:

(>>) :: (Monad m) => m a -> m b -> m b
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

Aqui Monad é uma typeclass. IO é uma instância de Monad. O operador “>>” serve para conectar duas ações, descartando o resultado da primeira e retornando a segunda.

main = 
     putStr "Ola" >> putStrLn " Mundo"

O operador “>>=” executa uma ação e alimenta uma função com o valor retornado. Essa função gera uma nova ação. Um exemplo:

main = 
     getLine >>= (\x -> putStrLn $ "Ola " ++ x)

Assim, o exemplo do início do post poderia ser reescrito sem o uso da palavra-chave do:

main =
     putStrLn "Entre com seu nome:" >> 
       getLine >>= 
         (\inpStr -> putStrLn $ "Ola " ++ inpStr)

Manipulação de arquivos de texto

A leitura e escrita de arquivos de texto em Haskell é bastante parecida com a de linguagens imperativas. Temos a função openFile

openFile :: FilePath -> IOMode -> IO Handle

que recebe o caminho do arquivo (uma string) e um modo de acesso (leitura, escrita, etc.)), e retorna um manipulador (handler) do arquivo (encapsulado em uma ação de IO).

Temos também as funções hGetLine que lê uma linha do manipulador, hPutStrLn que escreve uma linha no manipulador e hIsEOF que decide se o manipulador atingiu o final do arquivo.

import System.IO
import Data.Char(toUpper)

main :: IO()
main = do
     inh <- openFile "entrada.txt" ReadMode
     outh <- openFile "saida.txt" WriteMode     
     mainloop inh outh
     hClose inh
     hClose outh

mainloop inh outh = 
         do ineof <- hIsEOF inh
            if ineof
               then return()
               else do inpStr <- hGetLine inh
                       hPutStrLn outh (map toUpper inpStr)
                       mainloop inh outh

Temos os manipuladores para a entrada padrão, a saída padrão e a saída de erro. Desta forma poríamos usar as seguintes definições:

getLine = hGetLine stdin
putStrLn = hPutStrLn stdout
print = hPrint stdout

hGetContents

Ao invés de definir a função mainloop como no exemplo acima, podemos usar a função hGetContents

hGetContents :: Handle -> IO String

import System.IO
import Data.Char(toUpper)

main :: IO ()
main = do 
       inh <- openFile "entrada.txt" ReadMode
       outh <- openFile "saida.txt" WriteMode
       inpStr <- hGetContents inh
       hPutStr outh (map toUpper inpStr)
       hClose inh
       hClose outh

Como Haskell é uma linguagem com avaliação preguiçosa (lazy evaluation), no exemplo acima a função hGetContents não carregará todo o arquivo em memória, mas fará a leitura e escrita em partes.

readFile, writeFile e interact

As funções readFile e writeFile simplificam a leitura e escrita em arquivos de texto para casos como o do nosso exemplo, abstraindo o uso direto dos manipuladores:

readFile :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()

A nova versão fica bastante concisa:

import System.IO
import Data.Char(toUpper)

main :: IO ()
main = do 
       inpStr <- readFile "entrada.txt"
       writeFile "saida.txt" (map toUpper inpStr)

No caso particular de estarmos trabalhando com a entrada e saída padrão, podemos usar a função interact. Ela lê uma String da entrada padrão, processa com a função passada como parâmetro e retorna a String processada.

interact :: (String -> String) -> IO ()

Nesse caso nosso código se reduziria a uma linha!

import Data.Char(toUpper)

main :: IO ()
main =
       interact (map toUpper)

Buffering

Se rodarmos o código acima no ghci, ao mesmo tempo em que digitamos os caracteres eles passam a ser impressos no terminal. Há três tipos de buffers NoBuffering, LineBuffering e BlockBuffering. O modo padrão no ghci é o NoBuffering. Podemos mudar o modo padrão através da função hSetBuffering,

main :: IO ()
main = do
       hSetBuffering stdin LineBuffering
       interact (map toUpper)

Um efeito colateral indesejável é que depois que executarmos o main, os próximos comandos digitados no ghci só aparecerão depois de apertarmos o Enter :P

Parâmetros via linha de comando

Para obter os parâmetros passados como parâmetro via linha de comando, podemos usar a função getArgs presente em System.Environment

getArgs :: IO [String]

Ele retorna uma action contendo uma lista de strings correspondente aos parâmetros.

import System.IO
import System.Environment

main = do
     list <- getArgs
     putStrLn(show(list))

Praticando com problemas de programação

Agora que já aprendi o básico de leitura da entrada e saída padrão, vou começar a praticar no SPOJ-Br com os problemas da OBI. Até agora eu vinha usando o project Euler pois lá só precisa submeter a solução, não importando o modo como se faz a leitura/escrita dos dados.

Outra maneira de praticar é com a lista de 99 problemas de Haskell, mas esse eu ainda não tentei.

Minha sugestão de problemas para serem resolvidos no SPOJ-Br são Quadrados, Soma, Fatorial, Primo. Alguns com lógica bem simples também, mas um pouco mais chato de processar a entrada são Pneu, Fliperama, Garçom, Tacógrafo e Sedex.

Spoiler!

No problema Quadrados dá fazer uma solução bem compacta usando conceitos discutidos anteriormente como IO, funções lambda, currying e composição de função:

main = interact ((++ "\n") . show . (\x -> x*x) . read)

Referências

[1] Real World Haskell – Capítulo 7
[2] Haskell.org – Introduction to IO


SRM 533, 535 e Codeforces #108

Junho 10, 2012

Desde o último post-mortem, participei de várias competições de programação. No SRM 533 falhei nos dois problemas que submeti (Casket of Star e Magic Board) e por causa disso voltei a virar azul :(

No Codeforces #108, passei um bom tempo pensando no problema Garden, mas não consegui resolver.

No SRM 535 achei um bug na minha solução e tive que re-submeter o problema fácil por 75 pontos. Além disso errei um challenge (-25 pontos). Finalmente, pensei bastante no problema Fox and Business, mas a complexidade da minha solução estava muito alta dado os limites do problema.

Neste post vou apresentar um resumo das soluções para os quatro problemas mencionados.


Casket of Star

A descrição do problema se encontra aqui. Estou supondo que o vetor de entrada é chamado w e possui tamanho n.

Minha abordagem durante a prova foi gulosa: remover sempre o elemento i tal que w[i-1]*w[i+1] seja máximo. Na hora me pareceu correto e todos os casos de teste passaram, mas eis um contra-exemplo: (2, 5, 10, 5, 2). O algoritmo irá remover o 10, gerando um produto de 5*5=25, deixando (2, 5, 5, 2). Aí não tem muito o que fazer: vamos tirar os dois 5, gerando os produtos 10 e depois 4, para um total de 39. Entretanto, se retirarmos os 5’s antes do 10, teremos 20 + 20 + 4, para um total de 44.

Programação dinâmica

Durante a prova cheguei a pensar em uma abordagem por programação dinâmica, mas encontrei dificuldades em definir os subproblemas independentes. Minha única ideia foi a de remover um dado elemento i (adicionando um valor w[i-1]*w[i+1]) e então pensar em alguma coisa com os subproblemas [0,i-1] e [i+1, n-1], mas eles não são independentes, pois poderíamos remover o elemento i+1 e o valor obtido dependeria do valor no outro subvetor.

Depois da prova pensei em outras alternativas. Uma delas foi: e se ao invés de tentar separar em subproblemas a partir do primeiro elemento removido, tentar separar a partir do último? Essa ideia aleatória matou o problema porque se eu sei que o elemento i será o último a ser removido, então os intervalos [0,i] e [i, n-1] são independentes! Isso porque o valor obtido da remoção de um elemento de 0 a i-1 não dependerá do valor de i+1 a n-1 e vice-versa.

Se chamarmos de f(i, j) o melhor valor obtido para a subsequência [i, j], podemos derivar a seguinte recorrência:

f(i, j) = \max_{i +1 \le k \le j-1} \left\{ f(i, k) + f(k, j) + w(i)w(j) \right\}

No caso estamos tentando com todos os possíveis valores de k entre i+1 e j-1 e supondo que k será o último elemento a ser removido. O resultado das remoções feitas em f(i, k) será o vetor {i,k} e o de f(k, j) será o vetor {k, j}, ou seja, {i, k, j}. Agora a única possibilidade é remover k e somamos w(i)w(j) no valor. O caso base é quando temos menos de 2 elementos, o qual devemos retornar 0.

Resumo

Achei a dificuldade do problema elevada, além do fato de ele ser bem tricky. A taxa de acerto foi de 31%.

A técnica de “pensar ao contrário” (nesse caso, olha para o último elemento a ser removido ao invés do primeiro), que eu já havia usado em problemas passados, foi essencial.


Magic Board

Neste problema, devemos encontrar um caminho que passe exatamente por todas as células marcadas de um grid, com a seguinte restrição: só podemos ir de uma célula para outra usando linhas verticais ou horizontais, sendo que no caminho devemos alternar entre linhas verticais e horizontais, começando por uma linha horizontal.

Minha abordagem foi a seguinte. Seja s o vértice inicial e t o vértice final do caminho. Nesse caso, somamos 1 na contagem da coluna de s. Se o número de vértices for par, então a última aresta é horizontal e nesse caso também somamos 1 na contagem da coluna de t. Por outro lado, se o número de vértices for ímpar, a última aresta é vertical e então somamos 1 na linha de t. Agora, verificamos se todas as colunas e linhas possuem uma contagem par.

Temos que chutar todos os possíveis pares s e t para ver se algum satisfaz a condição acima, ou seja, o algoritmo é O(N^4), para N = 50.

Essa abordagem parecia correta, mas eu tomei um challenge. O motivo: essa contagem não faz a verificação da conexidade. Pode existir um caminho válido mas com “ciclos” disjuntos, como no seguinte exemplo:


##...
.#...
...##
...##

Figura 1: Ciclo disjunto

A componente no alto à esquerda é válida, assim como o ciclo abaixo à direita, mas eles são disjuntos. É possível eliminar esse caso fazendo uma simples busca em profundidade e verificar se todo vértice é alcançável a partir do outro usando apenas arestas ortogonais.

No editorial, a solução é modelar o tabuleiro como grafo bipartido. Cada coluna representa um vértice da primeira partição, enquanto cada linha representa um vértice da segunda partição. O problema consiste em decidir se existe um caminho euleriano, com a restrição de que a primeira aresta usada no tabuleiro seja horizontal.

Resumo

Esse foi outro problema tricky, pelo fato de não haver casos de testes com o problema da conexidade.

A modelagem de um tabuleiro usando um grafo bipartido é uma técnica que eu já havia utilizado anteriormente. Tentar trocar arestas com vértices (dualidade) no grafo pode ser útil para conseguir resolver o problema. Nesse caso, um problema que parecia um caminho hamiltoniano (NP-difícil) acabou ficando parecido com um caminho euleriano (para o qual existe um algoritmo polinomial)

Dois problemas relacionados que me veem à mente são o Rectilinear Polygon [4] e o The Necklace [5].


Fox and Business

Podemos modelar este problema matematicamente da seguinte maneira:

\min (\sum_{i \in S} p_i a_i t) + tK

Onde, S é representa os empregados que serão escolhidos na solução, p_i é o custo por unidade de trabalho do empregado i e a_i é a quantidade de unidades de trabalho dele em uma hora. A variável t é o tempo de cada trabalhador e K é o número de trabalhador que deverá ser usado.

Essa função objetivo está sujeita a

\sum_{i \in S} a_i t = T

onde T é o total de trabalho que deve ser feito. Durante a prova só consegui pensar em uma abordagem de programação dinâmica, mas minha ideia tinha uma complexidade que não passaria no tempo.

A abordagem usada no editorial é muito engenhosa e não utiliza PD. A ideia se você dividir a função objetivo por uma constante positiva, a solução ótima não muda. Como T é uma constante, podemos dividir a função objetivo por ela, obtendo

(\sum_{i \in S} p_i a_i t) + tK = \dfrac{(\sum_{i \in S} p_i a_i t) + tK}{T}

Substituindo o valor de T, podemos nos livrar da variável t,

= \dfrac{(\sum_{i \in S} p_i a_i) + K}{\sum_{i \in S} a_i}

Bom, isso não pareceu ajudar muito, mas a segunda sacada é transformar esse problema de otimização em um problema de decisão, ou seja, dado um valor C, existe uma solução S tal que

C \ge \dfrac{(\sum_{i \in S} p_i a_i) + K}{\sum_{i \in S} a_i}?

Com um pouco de álgebra podemos reescrever essa desigualdade como

C \sum_{i \in S} a_i \ge (\sum_{i \in S} p_i a_i) + K \rightarrow

\sum_{i \in S} a_i(C - p_i) \ge K

O valor máximo do lado esquerdo da desigualdade pode ser calculado de maneira gulosa, escolhendo os K maiores de a_i(C - p_i)! Se esse valor máximo for menor do que K, então não existe uma solução. Assim, temos um algoritmo para resolver o problema de decisão.

Para obter o valor ótimo de C, podemos usar a técnica da busca binária. O valor esperado pelo problema será C T

Resumo

Ideias utilizadas: Manipulação algébrica e busca binária para transformar um problema de otimização em um de decisão.


Garden

Neste problema temos um tabuleiro n x m onde cada célula tem um inteiro positivo que representa um custo. Duas células são ditas adjacentes se tocam em um dos lados (não consideramos diagonal). Duas células podem ser conectadas através de um caminho de células adjacentes. O custo desse caminho é a soma dos custos das células nesse caminho. São dados então k pontos desse tabuleiro que devem ser conectados com o menor custo. Mais detalhes no enunciado do problema.

Esse problema lembra um caso particular do problema da árvore de Steiner, onde é permitido adicionar novos vértices para tentar obter uma árvore de custo menor do que a árvore geradora mínima.

Achei a solução do editorial bastante resumida e com um inglês meio difícil de compreender. De qualquer maneira, deu pra entender que se trata de programação dinâmica. No editorial é dada a recorrência, mas tive que quebrar a cabeça para entender de onde ela veio.

Programação dinâmica

A ideia básica da recorrência é: dada uma cobertura de um conjunto de pontos, quebramo-na em cobertura menores, cobrindo subconjuntos do conjunto inicial de pontos. Faremos a quebra em pontos compartilhados pelas coberturas menores o qual chamaremos de pivots.

Seja C(P, p) a cobertura de menor custo cobrindo o conjunto de pontos P e que possua o ponto p. No nosso caso, P é um subconjunto dos pontos a serem cobertos e pode ser representado com uma máscara de bits. Já o ponto p é uma célula qualquer do tabuleiro. A solução que queremos é \max_p \{C(P, p)\} com P igual ao conjunto dos pontos a serem cobertos.

Há dois tipos de recorrência que vamos considerar. Primeiro, considere um grafo que conecta os pontos desejados como o exemplo da Figura 2(a). Queremos particioná-lo em 2 subgrafos que cobrem subconjuntos desses pontos e que compartilham apenas o ponto verde (pivot). Uma possibilidade de quebra é a da Figura 2(b).

Figura 2

Agora podemos resolver recursivamente cada componente e calcular o custo da componente completa somando os custos. Porém, veja que o pivot está sendo contado duas vezes e portanto devemos subtrai-lo. Definimos C_1(P, q) como:

C_1(P, p) = \max_{P'}\{C(P',p) + C(P \setminus P', p) - custo(p)\}

Onde P' representa todos os subconjuntos próprios não vazios de P.

Porém, pode ser o caso de não conseguirmos particionar o grafo de forma que o pivot seja o único ponto compartilhado, como é o caso da segunda componente de Figura 2(b). Neste caso queremos modificar o nosso pivot, mas para isso devemos considerar a distância entre o pivot antigo e o novo, representados por p e q em nosso exemplo:

Figura 3

Nesse caso definimos C_2(P, p) como:

C_2(P, p) = \max_{q}\{C(P \setminus \{p\}, q) + dist(p, q) - custo(q)\}

Onde q é um ponto qualquer do tabuleiro. Um cuidado que devemos ter aqui é que se p pertence a P, devemos removê-lo antes de chamar a recursão. Novamente, veja que o custo da célula q está sendo considerado duas vezes e portanto precisamos descontar um delas.

Finalmente, temos que C(P, p) = \max\{C_1(P, p), C_2(P, p)\}

Não bastasse isso, o problema ainda pede para mostrar o grafo que conecta os pontos (se houver mais de um com custo ótimo, pode ser qualquer um). Para isso devemos guardar as decisões tomadas durante as recorrências para recuperar a solução.

Complexidade

A distância entre pares de pontos pode ser pré-computada usando o algoritmo de Floyd-Warshall. Denotando nm por N, temos O(N^3).

Para calcular a complexidade da recursão vemos que são O(2^k N) estados. Na primeira recorrência devemos analisar outros O(2^k) estados, enquanto na segunda são O(N), levando a uma complexidade total O(2^kN(2^k + N)). Os limites do problema são k \le 7 e N \le 200, o que dá na ordem de O(8\cdot10^6) operações.

Resumo

Ideias utilizadas: Observar os limites dos problemas, particularmente o valor de k, que sugerem que no estado da programação dinâmica podem ser usadas máscara de bits.

Além disso, notar que se quebrarmos em subproblemas particionando o conjunto inicial de pontos, as soluções parciais não podem ser utilizadas imediatamente para compor a solução do problema original por que há células que seriam compartilhadas entre ambas as soluções e portanto devemos remover a contagem repetida.

A grande sacada é ver que podemos supor que as sub-soluções compartilham exatamente uma célula se permitirmos a troca de pivot.

Códigos-fontes

Disponibilizei os códigos-fontes de todos os problemas discutidos no post, no github (SRM 533, SRM 535 e Codeforces #108).

Referências

[1] Editorial SRM 533
[2] Editorial Codeforces #108
[3] Editorial SRM 535
[4] UVa 11106 – Rectilinear Polygon
[5] UVa 10054 – The Necklace


Mapas de Símbolos Fisicamente Realizáveis: a função Max-Min

Junho 5, 2012

Já escrevi sobre o tema de pesquisa do meu mestrado — otimização da visualização de mapas de símbolos proporcionais — em outros posts [1], [2] e [3].

Desta vez gostaria de falar sobre uma das variantes desse problema proposta por Cabello et al [4] onde o objetivo é basicamente dispor os símbolos no mapa de modo a maximizar a visibilidade do disco menos visível. Mais formalmente, dado um conjunto de discos S e uma disposição deles no plano, denotamos por b_i o comprimento da borda visível do disco i \in S.

O objetivo é encontrar uma disposição dos discos que maximize \min \{b_i\}. Não por acaso tal função é chamada de Max-Min.

Cabello et al. apresentaram um algoritmo guloso que maximiza essa função objetivo quando os discos só podem ser empilhados (não podem ser entrelaçados). A ideia é bem simples: dado um conjunto de n discos S, escolha o disco i^* que se posto por baixo de todos os outros teria o maior comprimento de borda visível (ou seja, b_i^* é máximo). Coloque i^* na base e determine a ordem dos outros discos recursivamente.

A versão “força-bruta” desse algoritmo é O(n^3), mas eles apresentam uma versão O(n^2 \log n) usando árvores de segmentos.

Se permitirmos que os discos possam ser entrelaçados, conforme a figura abaixo à esquerda, o problema se torna NP-difícil!

Disposição com entrelaçamento vs. disposição em pilha

Já havíamos atacado a versão que objetiva maximizar a soma das bordas visíveis considerando todos os discos (chamada de Max-Total) e permitindo entrelaçamento usando Programação Linear Inteira. Esse trabalho foi apresentado no Sibgrapi de 2011.

Após esse congresso, fomos convidados a estender nosso trabalho com pelo menos 30% de novo conteúdo e submeter para a publicação em um jornal científico, o The Visual Computer.

Decidimos então atacar a versão com função objetivo Max-Min usando PLI também. A formulação é bastante parecida com aquela que apresentamos no Sibgrapi, mas resolvedores de PLI têm bastante dificuldade em lidar com formulações do tipo max-min, onde se quer maximizar o menor valor de uma função.

Em nossos experimentos, instâncias para as quais o resolvedor achava a solução ótima da função Max-Total em segundos, não eram resolvidas mesmo rodando durante algumas horas para a versão Max-Min.

Uma possível causa para esse comportamento é que para formulações max-min temos muitas soluções com mesmo valor (platôs) e isso faz com que os otimizadores se percam.

Para um exemplo, considere as soluções na figura abaixo. Embora sejam bastante diferentes, elas possuem o mesmo valor da função Max-Min porque o disco destacado em vermelho é tão pequeno, que é ele que define o valor da função objetivo não importando a disposição entre o restante dos discos.

Soluções com mesmo valor da função Max-Min (definida pela borda do disco vermelho)

Como muitas das nossas instâncias podem ser decompostas em componentes menores, usamos a seguinte ideia para tentar melhorar o desempenho do nosso algoritmo. Considere as componentes decompostas c_1, c_2, \cdots, c_k. Seja s(c_i) o valor da solução ótima de c_i para Max-Min limitado a desenhos em pilha e p(c_i) permitindo também desenhos entrelaçados.

Suponha que as componentes estão numeradas de forma que s(c_1) \le s(c_2) \le \cdots \le s(c_k). Assim, a solução ótima da instância completa para desenhos em pilha é igual a s(c_1).

Temos também que s(c_i) \le p(c_i), pois estamos maximizando uma função e p considera tanto desenhos em pilha quanto entrelaçados.

Infelizmente não podemos afirmar que p(c_i) \le p(c_{i+1}). Porém, seja i^* = \mbox{argmin}_i\{p(c_i)\}. Se p(c_{i'}) \le s(c_{i'+1}) para algum i' \le k-1, então temos que p(c_{i'}) \le s(c_{j}) para i' < j e portanto p(c_{i'}) \le s(c_{j}) para i' < j, ou seja, i^* \le i'.

A ideia do algoritmo é resolver cada componente com o algoritmo polinomial de Cabello e ordená-las pelo valor da solução, obtendo s(c_1) \le s(c_2) \le \cdots \le s(c_k). Em seguida resolvemos as componentes nessa ordem usando a formulação do Max-Min permitindo desenhos entrelaçados, obtendo a cada passo p(c_i). Se em algum passo encontramos p(c_{i}) \le s(c_{i+1}), podemos parar pois já encontramos o valor ótimo.

Esse nosso trabalho foi aceito, tendo sido publicado online recentemente [5].

Referências

[1] Blog do Kunigami: Mapas de Símbolos Proporcionais
[2] Blog do Kunigami: Mapas de símbolos proporcionais e a meia integralidade da cobertura de vértices
[3]Blog do Kunigami: Visualização ótima de desenhos fisicamente realizáveis
[4] S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann, “Algorithmic aspects of proportional symbol maps”, Algorithmica, 2010.
[5] G. Kunigami, P. de Rezende, C. de Souza and T. Yunes, “Generating Optimal Drawings of Physically Realizable Symbol Maps with Integer Programming”, 2012