O que é heurística e quando devemos usá-las?

Em Ciência da Computação e Otimização Matemática, geralmente procuramos um procedimento que forneça uma solução exata para um problema. Em um contexto geral, isso significa sempre retornar a resposta correta, e no caso de otimização, a resposta correta é a melhor! Mas, como vimos em P vs. NP: um "problema de um milhão de dólares, nem todo problema pode ser resolvido em um período de tempo viável. É exatamente isso que motiva um campo crescente de pesquisas que estuda métodos para encontrar a melhor solução possível no tempo disponível. Esses métodos são conhecidos como Heurísticas.

 

Para ilustrar a utilidade dos métodos heurísticos, vamos pegar o exemplo de O Gambito da Rainha e a complexidade e imaginar um jogo de xadrez. Mais precisamente, consideremos um jogo de xadrez prático no qual os jogadores têm um limite de tempo. Podemos construir um algoritmo para jogar xadrez que considere todos os movimentos possíveis e escolha o melhor. Mas apesar de ser comprovadamente ótimo, esse algoritmo sempre perderia em um jogo da vida real. Mesmo com nossos supercomputadores modernos, levaria uma quantidade absurda de tempo para decidir seu movimento inicial. Então, como um computador foi capaz de vencer o campeão mundial, Garry Kasparov, em 1997? Com uma heurística, é claro!

 

A principal diferença entre métodos exatos e heurísticos está na abordagem. Métodos exatos focam em encontrar a solução ótima no menor tempo possível, o que em muitos casos equilibra a busca por uma  solução melhor e a tentativa de provar que a melhor solução atual é a ótima. Por outro lado, os métodos heurísticos se concentram em entender o que constitui uma "boa" solução e em desenvolver um método de busca que aproveite esse conhecimento. Um ponto de partida usual para o desenvolvimento de heurísticas é replicar a lógica de um profissional. No exemplo do xadrez, uma heurística comumente usada é criar, com a ajuda de jogadores de xadrez experientes, uma função que pode pontuar uma configuração do tabuleiro com base nas posições das peças. Esta função evita a necessidade de simular todos os jogos possíveis até o final.

 

Então, devo sempre escolher heurística? Claro que não! Para muitos problemas práticos, é possível encontrar a solução ótima, e se for esse o caso, você deve buscá-la! Mas nos casos em que a solução ótima não é possível, você deve estar ciente das desvantagens das heurísticas e como superá-las:

 

Quando é "bom o suficiente"?

 

Quando você tem uma solução ótima, sabe que não poderia ter feito melhor. Mas se você estiver usando uma heurística, nunca saberá se poderia ter uma melhora de 50% se tentasse um pouco mais. Felizmente, na maioria dos casos, um estudo baseado em instâncias simuladas do seu problema pode indicar quando um determinado método de busca começa a estagnar. Com isso, um profissional de otimização qualificado pode definir bons critérios de parada que, com base em suas necessidades, fornecerão a relação ideal entre tempo e qualidade da solução.

 

Os humanos nem sempre são bons em resolver problemas

 

Como dito anteriormente, uma estratégia comum para heurísticas é usar a intuição humana como ponto de partida. Isso é ótimo em muitas situações, mas às vezes as limitações e vieses humanos podem resultar em uma má tomada de decisão. Projetar uma boa heurística não é simplesmente codificar a intuição profissional em uma solução. Um método de busca eficiente que aproveite a velocidade do computador também é muito importante para explorar soluções diferentes e inusitadas.

 

Eles são difíceis de comparar

 

Comparar duas heurísticas não é uma tarefa trivial. Quase sempre você obtém um resultado misto, no qual o método A produz melhores resultados em alguns casos e, em outros, o método B é superior. Uma análise estatística cuidadosamente construída e um bom modelo computacional do problema são muito importantes para identificar um método robusto que forneça boas soluções em uma ampla variedade de contextos. Outra boa prática é usar métodos com parâmetros livres que podem ser ajustados a diferentes cenários. 

 

Autor: Vinícius Mello - Consultor na Cassotis Consulting

                                      Coautor: Fabio Silva - Gerente Sênior na Cassotis Consulting