1. Introdução
A busca heurística é um pilar fundamental na resolução de problemas de otimização combinatorial, especialmente quando métodos exatos se tornam computacionalmente inviáveis. Para um público não especializado, a pergunta central que orienta esta revisão é: qual o melhor método de busca heurística quando se considera o menor custo computacional? Esta questão é particularmente relevante para pequenas e médias empresas (PMEs) e profissionais que buscam soluções eficientes sem dispor de infraestrutura computacional massiva [4].
Para responder a esta pergunta, realizamos uma revisão sistemática da literatura, priorizando artigos revisados por pares e de alto fator de impacto, indexados nas bases arXiv, PubMed e Google Scholar. A análise concentra-se em identificar o algoritmo que oferece o melhor equilíbrio entre custo computacional (tempo e memória) e qualidade da solução encontrada.
2. Fundamentos da Busca Heurística
Heurísticas são estratégias práticas que utilizam conhecimento do domínio para guiar o processo de busca, reduzindo drasticamente o espaço de soluções a ser explorado [5]. Em contraste com métodos cegos (uninformed search), que exploram o espaço de busca sistematicamente, as heurísticas priorizam caminhos mais promissores com base em uma função de avaliação [2].
Três algoritmos se destacam na literatura por sua relevância e ampla aplicação:
- Busca Gulosa (Greedy Best-First Search – GBFS): Utiliza apenas a função heurística h(n) para estimar o custo do nó atual até o objetivo, priorizando expansão do nó com menor valor de h(n) [9].
- Busca de Custo Uniforme (Uniform-Cost Search – UCS): Prioriza o caminho de menor custo acumulado g(n) do início até o nó atual, sendo ótima e completa, porém ineficiente [3].
- Algoritmo A*: Combina as duas abordagens anteriores através da função de avaliação f(n) = g(n) + h(n), onde h(n) é uma heurística admissível (nunca superestima o custo real) [5][6].
3. Análise Comparativa dos Métodos
3.1. Comparação de Complexidade
A Tabela 1 sintetiza as características de complexidade e garantias de cada método, com base na literatura consolidada [3][13].
| Estratégia | Função de Seleção | Garantia do Caminho | Complexidade de Espaço |
|---|---|---|---|
| Busca em Largura | Primeiro nó adicionado | Menos arcos | Exponencial |
| Busca em Profundidade | Último nó adicionado | Não | Linear |
| Busca Gulosa | Menor h(n) | Não | Exponencial |
| Busca de Custo Uniforme | Menor custo(n) | Menor custo | Exponencial |
| A* | Menor custo(n)+h(n) | Menor custo | Exponencial |
| IDA* | — | Menor custo | Linear |
Tabela 1: Síntese das estratégias de busca. Adaptado de Poole & Mackworth [3][13].
3.2. Análise de Custo Computacional
A Tabela 2 apresenta dados empíricos comparando o desempenho de diferentes algoritmos no clássico problema do 8-puzzle, demonstrando a superioridade do A* com heurísticas mais informadas [11].
| Profundidade (d) | IDS (Nós Expandidos) | A* com h1 (Nós) | A* com h2 (Nós) |
|---|---|---|---|
| 2 | 10 | 6 | 6 |
| 4 | 112 | 13 | 12 |
| 6 | 680 | 20 | 18 |
| 8 | 6384 | 39 | 25 |
| 10 | 47127 | 93 | 39 |
| 12 | 364404 | 227 | 73 |
| 14 | 3473941 | 539 | 113 |
| 16 | – | 1301 | 211 |
| 18 | – | 3056 | 363 |
| 20 | – | 7276 | 676 |
Tabela 2: Comparação de desempenho entre IDS, A* com h1 (peças fora do lugar) e A* com h2 (distância Manhattan). Fonte: [11].
Os dados evidenciam que o A* com heurística h2 (distância Manhattan) expande significativamente menos nós que o A* com h1 (peças fora do lugar) e ambos são drasticamente superiores à busca por aprofundamento iterativo (IDS). Este resultado confirma que heurísticas mais informadas reduzem substancialmente o custo computacional.
4. Evidências de Aplicação: O Caso das PMEs
Estudos recentes destacam a relevância prática da busca heurística para pequenas e médias empresas (PMEs). Uma revisão abrangente publicada na MDPI [4] demonstra que:
- Heurísticas e meta-heurísticas são particularmente eficazes para otimização multi-objetivo com demandas computacionais reduzidas, sendo mais acessíveis que métodos exatos para PMEs.
- Abordagens híbridas que combinam heurísticas tradicionais com aprendizado de máquina (ML) têm ganhado destaque, superando métodos isolados em problemas complexos.
- A aplicação de heurísticas em logística, recursos humanos, finanças e gestão de projetos tem demonstrado resultados superiores em termos de custo-benefício computacional.
Adicionalmente, a análise dos competidores do Cross-domain Heuristic Search Challenge (CHeSC) [12] revela que as estratégias mais eficazes para equilibrar custo e qualidade incluem:
- Pontos de busca mistos
- Fases de busca iteradas
- Seleção de heurísticas por hibridização com relay
- Mecanismos de Tabu
- Reinício estocástico
5. Tendências e Recomendações
As tendências atuais apontam para o desenvolvimento de hiper-heurísticas que operam no espaço de heurísticas em vez de soluções, selecionando dinamicamente as estratégias mais adequadas para cada fase do processo de busca [12]. No entanto, para a maioria das aplicações práticas, o algoritmo A* permanece como a referência dourada quando se busca o menor custo computacional com garantia de otimalidade [6].
Para profissionais e PMEs, a recomendação é iniciar com implementações do A* utilizando heurísticas admissíveis bem calibradas para o domínio específico. Caso a memória seja um fator limitante (como em sistemas embarcados), o IDA* oferece uma alternativa com complexidade de espaço linear [3][14].
Para cenários onde a otimalidade não é estritamente necessária e a velocidade é primordial, a Busca Gulosa pode ser uma opção, porém com ressalvas: seu desempenho é altamente dependente da qualidade da heurística e não há garantia de encontrar o caminho mais curto [7].
6. Conclusão
Com base nas evidências analisadas, o algoritmo A* emerge como o método que melhor equilibra menor custo computacional e qualidade da solução. Sua eficiência é maximizada quando:
- Utiliza uma heurística admissível e consistente (nunca superestima o custo real)
- Emprega a heurística mais informada possível dentro da admissibilidade (ex: distância Manhattan em vez de peças fora do lugar no 8-puzzle)
- Aplica otimizações como pruning de estados duplicados para reduzir o espaço de busca [15]
Embora a complexidade de espaço do A* seja exponencial, variantes como o IDA* (Iterative Deepening A*) oferecem compromisso com complexidade linear de espaço, sendo recomendadas quando a memória é o fator limitante [14][10].
Para o público geral e profissionais de PMEs, a mensagem é clara: investir na escolha adequada do algoritmo e da heurística pode reduzir drasticamente o custo computacional, viabilizando soluções de otimização mesmo com recursos limitados.
Referências
- Hart, P.E., Nilsson, N.J., Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
- Rios, L.H.O., & Chaimowicz, L. (2010). A survey and classification of A* based best-first heuristic search algorithms. Proceedings of the 20th Brazilian conference on Advances in artificial intelligence. ACM Digital Library. https://dl.acm.org/doi/10.5555/1929622.1929654
- Poole, D., & Mackworth, A. (2023). Artificial Intelligence: foundations of computational agents (3rd ed.). Cambridge University Press. https://www.cs.ubc.ca/~poole/aibook/2e/html2e/ArtInt2e.Ch3.S7.SS3.html
- Cano, J., et al. (2025). Strategic Decision-Making in SMEs: A Review of Heuristics and Machine Learning for Multi-Objective Optimization. Computation, 13(7), 173. MDPI. https://www.mdpi.com/2079-3197/13/7/173
- Zhao, J., et al. (2024). AI heuristic algorithms. Expert Systems with Applications. ScienceDirect. https://www.sciencedirect.com/topics/computer-science/heuristic-search-algorithm
- Tanimoto, S. (2008). The A* Algorithm (A Star). Elements of AI Using Common Lisp. https://tjhsst.edu/~rlatimer/ai/astarAlgoText.html
- LPU Distance Education. (2024). Informed Search Strategies. DCAP506_ARTIFICIAL_INTELLIGENCE. https://eslm.lpude.in/computer_application/mca/term_4/DCAP506_ARTIFICIAL_INTELLIGENCE/files/basic-html/page56.html
- upGrad. (2025). Informed Search in Artificial Intelligence: Types & Examples. https://www.upgrad.com/blog/all-about-informed-search-in-artificial-intelligence/
- Vemuri, V. (2003). Heuristic Searches. ECS170 Course Notes, UC Davis. https://www.cs.ucdavis.edu/~vemuri/classes/ecs170/heuristicnotes_files/heuristic-searches.htm
- Hindawi. (2015). Table 1: Pathfinding Techniques for Robotics and Video Games. International Journal of Computer Games Technology. https://www.hindawi.com/journals/ijcgt/2015/736138/tab1/
- Yale University. (2019). Effect of Heuristic Accuracy on Performance in the 8-puzzle. CS470 Lecture Notes. https://zoo.cs.yale.edu/classes/cs470/lectures/s2019/05-Advanced-Search.pdf
- Razali, M.K.M., et al. (2025). Unveiling Effective Heuristic Strategies: A Review of Cross-Domain Heuristic Search Challenge Algorithms. Computer Modeling in Engineering & Sciences, 142(2), 1233-1288. ScienceDirect. https://www.sciencedirect.com/org/science/article/pii/S152614922500030X
- Poole, D., & Mackworth, A. (2023). Summary of Search Strategies. Artificial Intelligence 2E. https://www.cs.ubc.ca/%7Epoole/aibook/2e/html2e/ArtInt2e.Ch3.S7.SS3.html#p2
- Bu, Z., & Korf, R.E. (2022). Iterative-Deepening Uniform-Cost Heuristic Search. Proceedings of the International Symposium on Combinatorial Search, 15(1), 20-28. AAAI. https://ojs.aaai.org/index.php/SOCS/article/view/21748
- Wilt, C., Thayer, J., & Ruml, W. (2010). A Comparison of Greedy Search Algorithms. Proceedings of SOCS, 135-142. https://www.cs.unh.edu/~ruml/papers/beam-socs10.pdf