Heurística (computação)
Em ciência da computação, inteligência artificial e otimização matemática, uma heurística (do grego εὑρίσκω "Eu encontro, descubro") é uma técnica projetada para resolver um problema mais rapidamente quando os métodos clássicos são muito lentos ou para encontrar uma solução aproximada quando os métodos clássicos não conseguem encontrar uma solução exata. Isso é obtido trocando-se a otimização, integridade, exatidão ou precisão por velocidade. De certa forma, pode ser considerado um atalho.
Uma função heurística, também chamada simplesmente de heurística, é uma função que classifica alternativas em algoritmos de pesquisa em cada etapa de ramificação com base nas informações disponíveis para decidir qual ramificação seguir. Por exemplo, pode aproximar a solução exata.
Definição
Em Ciência da Computação, normalmente existem duas propriedades principais na criação e elaboração de algoritmos:
- fazer o algoritmo ter um tempo de execução sempre aceitável e
- ser a solução ótima ou provavelmente boa para o problema em todos os casos.
No entanto, um algoritmo heurístico não cumpre uma dessas propriedades, podendo ser ou um algoritmo que encontra boas soluções a maioria das vezes, mas não tem garantias de que sempre encontrará ou um algoritmo que tem processamento rápido, mas não tem provas de que será rápido para todas as situações.
A pesquisa por heurísticas é uma pesquisa realizada por meio da quantificação de proximidade a um determinado objectivo. Diz-se que se tem uma boa (ou alta) heurística se o objecto de avaliação está muito próximo do objectivo; diz-se de má (ou baixa) heurística se o objecto avaliado estiver muito longe do objectivo. Etimologicamente a palavra heurística vem da palavra grega Heuriskein, que significa descobrir (e que deu origem também ao termo Eureca).
Um algoritmo aproximativo (ou algoritmo de aproximação) é heurístico, ou seja, utiliza informação e intuição a respeito da instância do problema e da sua estrutura para resolvê-lo de forma rápida.
Entretanto, nem todo algoritmo heurístico é aproximativo, ou seja, nem toda heurística tem uma razão de qualidade comprovada matematicamente ou prova formal de convergência. Por este motivo, em várias referências bibliográficas distingue-se os termos algoritmo aproximativo e heurística:
- aproximativo é a denominação do algoritmo que fornece soluções dentro de um limite de qualidade absoluto ou assintótico, assim como um limite assintótico polinomial de complexidade (pior caso) comprovado matematicamente;
- heurística e método heurístico são denominações para o algoritmo que fornece soluções sem um limite formal de qualidade, tipicamente avaliado empiricamente em termos de complexidade (média) e qualidade das soluções.
A heurística é um conjunto de regras e métodos que conduzem à descoberta, à invenção e à resolução de problemas. Também é uma ciência auxiliar da História que estuda a pesquisa das fontes.
Classificação das heurísticas
Métodos heurísticos geralmente se enquadram dentro dos seguintes grupos:
- heurísticas de construção, tais como o método guloso, que são aquelas onde uma ou mais soluções são construídas elemento a elemento, seguindo algum critério heurístico de otimização, até que se tenha uma solução viável;
- heurísticas de busca em vizinhança, como a busca local, as quais necessariamente partem de uma solução inicial viável (em alguns casos podendo ser somente uma solução possível qualquer), tentando melhorar esta solução através de operações de troca, remoção ou inserção, até que não seja mais possível a melhoria ou algum outro critério de parada seja satisfeito;
- heurísticas sistemáticas, tais como a Busca com Discrepância Limitada ou Backtracking Controlado, onde a árvore de espaço de soluções é percorrida utilizando critérios de ramificação e corte da árvore;
- heurísticas híbridas, resultantes da combinação de duas ou mais heurísticas com estratégias diferentes;
- metaheurísticas, que são heurísticas genéricas mais sofisticadas, onde uma heurística mais simples é gerenciada por um procedimento que visa explorar inteligentemente a instância do problema e o seu espaço de soluções.
Ainda existem outros tipos de heurística, tais como as técnicas de relaxação por exemplo. Entretanto, tais técnicas são específicas para problemas formulados como problemas de programação inteira ou constraint problems, os quais pertencem a um tipo particular de problema de otimização combinatorial.