Algoritmos aproximativos, heurísticas e meta-herísticas

Para problemas NP-completos, e para suas respectivas versões de otimização NP-difíceis, não se conhece algoritmo determinístico que os solucione de forma exata em tempo polinomial. Apesar disso, muitos desses problemas continuam tendo importantes aplicações reais, como em logística (PCV), escalonamento de tarefas (problema da mochila - PM), ou planejamento de infraestrutura urbana (cobertura por vértices - VCOVER). Nessas situações, como a complexidade de algoritmos exatos permite apenas a solução de instâncias muito pequenas do problema em tempo factível, pode-se recorrer a estratégias não-exatas para os problemas, desde que esse relaxamento traga vantagens do ponto de vista de tempo/complexidade. Duas abordagens são seminais desse contexto:

• Algoritmos aproximativos: nesse caso não se garante que as melhores soluções serão encontradas, mas tem-se um procedimento que garante quão pior qualquer solução não-exata possa ser em relação à sua contrapartida solução exata.

• Heurísticas: procedimentos que não garantem que a solução exata será retornada, mas que alguma solução não exata será retornada em tempo hábil.

Algoritmos aproximativos¶

Para problemas de otimização, onde temos uma noção da qualidade de uma solução, podemos sempre comparar o custo de uma solução ótima $S^*$ com o custo de uma solução não-ótima $S$, esta última retornada por um procedimento que não garante a otimalidade:

1. Maximização: $c(S) \leq c(S^*)$ (melhor é aquilo que é maior)
2. Minimização: $c(S^*) \leq c(S)$ (melhor é aquilo que é menor)

Definimos o fator de aproximação de uma solução aproximada como sendo a razão que expressa quantas vezes a mesma é pior do que uma solução ótima para a mesma instância de entrada, calculada da seguinte forma:

1. Maximização: $\frac{c(S^*)}{c(S)}$
2. Minimização: $\frac{c(S)}{c(S^*)}$

Observe que a mesma ideia poderia ser aplicada a qualquer solução aproximada $S$ e sua contrapartida ótima $S^*$. Assin, chamamos um algoritmos de ρ-aproximativo se, e somente se, as soluções por ele obtidas são, no máximo, ρ vezes piores do que a solução ótima para qualquer que seja a instância do problema. Assim, 1-aproximativo remete a um algoritmo ótimo, enquanto 2-aproximativo remete a um algoritmo que sempre produz soluções até 2 vezes piores do que o ótimo. Da mesma forma, ρ poderia ser inclusive uma função (não constante) do tamanho da entrada $f(n)$. O último representa um esquema de aproximação para um algoritmo, cuja qualidade e fator de aproximação depende diretamente do tamanho da entrada. Em seguida, vamos focar no cenário em que o fato de aproximação ρ é uma constante.

Para mostrar que um algoritmo é aproximativo, devemos então encontrar um fator de aproximação para o algoritmo ρ tal que:

1. Maximização: $c(S^*) \leq \rho~ c(S)$
2. Minimização: $c(S) \leq \rho~ c(S^*)$

Exemplo 1: cobertura por vértices¶

Neste problema, dado um grafo, o objetivo é selecionar um subconjunto mínimo dos vértices tal que todas as arestas sejam incidentes em algum vértice selecionado. Um algoritmo aproximativo para o problema, e totalmente arbitrário, seria:

vcover-aproximativo(G(V,E))
E' = E
C = {}
while E' != {}
  let (u,v) be an arbitrary edge in E'
  C = set-union(C, {u,v})
  remove from E' all edges incident with u or with v
return C

Um fator de aproximação para o algoritmo pode ser derivado a partir dos seguintes fatos:

1. Seja $A$ as arestas escolhidas no único laço do algoritmo. Sendo assim, os vértices escolhidos em $C$ satisfazem:

$|C|=2|A|$

2. Seja $S^*$ uma solução ótima. Cada aresta em $A$ precisa ser coberta por, pelo menos, um vértice em $S^*$. Isto é, uma aresta de $A$ precisa ser coberta por um vértice de $S^*$ ou por dois vértices de $S^*$ (nunca por nenhum vértice em $S^*$, por quê?):

$c(S^*) \geq |A|$

3. Juntando (1) e (2):

$c(S^*) \geq |A| \implies 2c(S^*) \geq 2|A| \implies 2c(S^*) \geq 2|A| = |C|$

Isto é:

$|C| \leq 2c(S^*)$, e por isso, temos um fator de aproximação 2 para o algoritmo. Conclusão, vcover-aproximativo se trata de um algoritmo 2-aproximativo.

Exemplo 2: problema do caixeiro viajante com desigualdade triangular (PCV)¶

Dado um grafo ponderado com arestas representando distâncias entre cidades, queremos encontrar um percurso fechado (ciclo hamiltoniano) de custo mínimo.

Uma observação interessante sobre o PCV é que deve-se passar por cada um dos vértices do grafo uma única vez, assim como no problema da árvore geradora mínima (AGM). De fato, com um ciclo hamiltoniano, podemos obter rapidamente uma árvore geradora (não necessariamente mínima):

**TODO: incluir figura

A ideia do algoritmo aproximado apresentado a seguir, busca tomar a direção inversa: encontrar um ciclo hamiltoniano a partir de uma árvore geradora. Faz sentido, já que encontrar uma árvore geradora mínima em um grafo é um problema conhecidamente fácil de se resolver e podemos contar com algoritmos polinomiais como o de Prim ou o de Kruskal. Pela dinâmica a seguir apresentada, e para que o fator de aproximação do algoritmo seja válido, vamos assumir que as instâncias do PCV atendem a propriedade da desigualdade triangular para os pesos das arestas, isto é:

$c(u,v) \leq c(u,w) + c(w,v)$ para $u,v,w \in V$

Seria o equivalente a garantir que o caminho direto entre dois vértices nunca pode ser maior do que o caminho indireto entre dois vértices. Se os pesos representarem distâncias euclidianas, por exemplo, essa propriedade é naturalmente satisfeita.

Sendo assim, dada uma AGM do grafo, como transformá-la em um ciclo hamiltoniano? Uma alternativa é possível a partir de um caminhamento em profundidade (DFS) na AGM.

*** TODO: incluir exemplo e explicação do exemplo*

pcv-aprox-agm(G(V, E))
T* = "alguma AGM de G" // usando o Prim ou Kruskal, por exemplo
C = "faça um caminhamento em profundidade (DFS) em T, anotando os vértices na ida e na volta do percurso"
S = "elimine as repetições de vértices em C, exceto o primeiro e o último"
retorne S

O algoritmo acima é polinomial no tamanho do grafo (verifique isso detalhando como cada linha do algoritmo alto nível acima seria implementada). A sequência de observações a seguir demonstra um fator de aproximação para o algoritmo:

1. Sabemos que o custo de uma solução ótima $S^*$ para o PCV é maior ou igual ao custo de uma árvore geradora qualquer $T$, que por sua vez é maior do que o custo de uma AGM $T^*$ :

$c(S^*) \geq c(T) \geq c(T^*) \implies c(S^*) \geq c(T^*)$ -- (I)

2. O custo do caminhamento DFS em $T^*$ no algoritmo é $2c(T^*)$, já que passamos duas vezes por cada aresta: na ida e na volta. Assim:

$c(C)=2c(T^*)$ -- (II)

3. Mas também sabemos que o custo da solução retornada pelo algoritmo, $c(S)$, não é maior do que o caminhamento DFS de custo $2c(T^*)$, já que o primeiro foi obtido através da remoção de vértices (e arestas) do segundo.

$c(C) \geq c(S)$ -- (III)

4. Então, usando os fatos anteriores:

$c(S^*) \geq_{\texttt{(I)}} c(T^*) \implies 2c(S^*) \geq 2c(T^*) =_{\texttt{(II)}} c(C) \geq_{\texttt{(III)}} c(S)$

Dessa forma, temos nosso fator de aproximação para este problema de minimização: $\rho = 2$. Em outras palavras, os ciclos hamiltonianos retornados pelo algoritmo aproximativo são, no máximo, duas vezes piores do que a solução ótima, para qualquer que seja a instância de entrada! O algoritmo é 2-aproximativo desde que a entrada respeite a desigualdade triangular.