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

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

Os comentários estão fechados.

%d bloggers like this: