Escalada

Definição - O que significa Hill Climbing?

Hill climbing é um método heurístico de otimização matemática usado para resolver problemas computacionalmente desafiadores que têm várias soluções. É um método iterativo pertencente à família de busca local que começa com uma solução aleatória e então melhora iterativamente essa solução um elemento de cada vez até chegar a uma solução mais ou menos otimizada.

Definirtec explica Hill Climbing

Hill climbing é uma técnica de otimização usada para encontrar uma solução "ótima local" para um problema computacional. Ele começa com uma solução que é muito pobre em comparação com a solução ideal e, a partir daí, melhora iterativamente. Ele faz isso gerando soluções "vizinhas" que são relativamente um passo melhores do que a solução atual, escolhe a melhor e então repete o processo até chegar à solução ideal porque não consegue mais encontrar nenhuma melhoria.

Variantes:

  • Simples - O primeiro nó ou solução mais próximo a ser encontrado é escolhido.
  • Subida mais íngreme - Todas as soluções sucessoras disponíveis são consideradas e, em seguida, a mais próxima é selecionada.
  • Estocástico - Uma solução vizinha é selecionada aleatoriamente e, então, é decidido se deve ou não passar para essa solução com base na quantidade de melhoria em relação ao nó atual.

O Hill climbing é feito iterativamente - ele passa por todo um procedimento e a solução final é armazenada. Se uma iteração diferente encontrar uma solução final melhor, a solução ou estado armazenado é substituído. Isso também é chamado de escalada de colina com espingarda, pois simplesmente tenta diferentes caminhos até atingir o melhor, da mesma forma que uma espingarda é imprecisa, mas ainda pode atingir seu alvo devido à grande extensão de projéteis. Isso funciona muito bem em muitos casos porque, ao que parece, é melhor gastar os recursos da CPU explorando caminhos diferentes do que otimizando cuidadosamente a partir de uma condição inicial.