Atualizado em 19/10/2026: texto refeito: definição direta de hill climbing (subida de encosta), passo a passo do algoritmo, variantes, os três problemas clássicos (máximo local, platô, cordilheira), comparação com descida do gradiente, simulated annealing e algoritmo genético, com fontes; saíram parágrafos genéricos e repetidos. Como conferimos os dados
Hill climbing (em português, subida de encosta) é um algoritmo de busca local usado em otimização. Ele parte de uma solução qualquer e faz pequenas mudanças nela; cada mudança que melhora o resultado é mantida, e o algoritmo para quando nenhuma mudança vizinha melhora mais nada. A imagem é a de alguém subindo um morro no escuro: dá um passo em cada direção e fica onde o terreno é mais alto.
Como o algoritmo funciona, passo a passo
- Comece com uma solução inicial, em geral escolhida ao acaso.
- Gere os vizinhos: soluções que diferem da atual por uma pequena alteração (um elemento trocado, um valor ajustado).
- Avalie cada vizinho com a função objetivo (a nota que se quer maximizar ou minimizar).
- Mova-se para um vizinho melhor. Se nenhum vizinho for melhor que a solução atual, pare: você chegou a um ótimo local.
Por ser um anytime algorithm, o hill climbing pode ser interrompido a qualquer momento e ainda devolve uma solução válida: a melhor encontrada até ali. Em problemas convexos, o ótimo local é também o ótimo global; nos demais, não há garantia.
Variantes do hill climbing
| Variante | Como escolhe o próximo passo |
|---|---|
| Simple hill climbing | Aceita o primeiro vizinho que for melhor que a solução atual. |
| Steepest-ascent (subida mais íngreme) | Avalia todos os vizinhos e vai para o melhor deles. |
| Stochastic (estocástico) | Sorteia um vizinho e decide, com alguma probabilidade, se aceita o movimento. |
| First-choice | Gera vizinhos aleatórios até achar um melhor, útil quando há vizinhos demais para listar. |
| Random-restart (reinícios aleatórios) | Roda o hill climbing várias vezes a partir de pontos iniciais diferentes e guarda o melhor resultado. |
Os três problemas clássicos
- Máximo local: o algoritmo chega a um pico menor que o pico mais alto do terreno e para, porque todos os vizinhos são piores. É o problema mais conhecido, ligado ao conceito de mínimo local (a mesma ideia, para quem minimiza em vez de maximizar).
- Platô: uma região plana, em que todos os vizinhos têm o mesmo valor. Sem diferença entre eles, o algoritmo não sabe para onde ir.
- Cordilheira (ridge): uma faixa alta e estreita em diagonal. Como cada passo muda uma variável por vez, a busca precisa ziguezaguear, com passos muito pequenos, para avançar.
Reinícios aleatórios, aceitar movimentos laterais num platô e variantes estocásticas são as formas mais simples de contornar esses problemas.
Hill climbing e outros métodos de otimização
- Descida do gradiente: ajusta todas as variáveis de uma vez na direção indicada pela derivada da função. É a escolha comum quando a função é diferenciável, como no treino de redes neurais; o hill climbing serve para funções em que não dá para calcular derivada.
- Simulated annealing: parecido com o hill climbing estocástico, mas aceita de propósito alguns movimentos piores, com probabilidade que diminui ao longo do tempo. Esses “pulos” ajudam a sair de máximos locais.
- Algoritmo genético: em vez de uma solução por vez, trabalha com uma população de soluções que se combinam e sofrem mutações.
- Busca tabu: guarda uma memória dos movimentos recentes para não voltar a soluções já visitadas.
Onde o hill climbing é usado
Como heurística, o hill climbing aparece em problemas de busca e otimização em que uma solução “boa o bastante” encontrada rápido vale mais que a solução perfeita: ajuste de parâmetros, roteamento, escalonamento de tarefas, alocação de recursos e jogos. Ele costuma ganhar de métodos mais pesados quando o tempo de busca é curto e poucos passos já levam a uma solução razoável.
Termos relacionados
Fontes (conferidas em 18/10/2026): Wikipédia (inglês): Hill climbing · Wikipédia (inglês): Local search (optimization)