Em algoritmos , a busca local é um método geral usado para resolver problemas de otimização , ou seja, problemas onde se busca a melhor solução em um conjunto de soluções candidatas. A busca local consiste em passar de uma solução para outra solução próxima no espaço das soluções candidatas ( o espaço de busca ) até que uma solução considerada ótima seja encontrada, ou o tempo previsto seja excedido.
Tomemos como exemplo o problema do caixeiro viajante , que consiste, dada uma lista de cidades e as distâncias entre elas, em encontrar um circuito que passe por todas as cidades, e que seja o mais curto possível. Em outras palavras, o conjunto de soluções admissíveis é o conjunto de circuitos que passam por todas as cidades, e o objetivo é minimizar o comprimento. Podemos considerar que estamos em um grafo não direcionado cujos vértices são cidades e as arestas são estradas entre cidades.
Um algoritmo de busca local simples, denominado 2-opt , é o seguinte: comece em qualquer circuito e repita a próxima busca. Pegue duas arestas (A, B) e (C, D) e substitua-as pelas arestas por (A, D) e (B, C). Se este novo circuito for mais curto, mantenha-o e continue, caso contrário, pegue o circuito anterior e experimente outro par de arestas.
Podemos parar o algoritmo quando todos os pares de arestas tiverem sido testados. A solução obtida não é garantida como ótima, mas ainda pode ser útil e de qualidade.
Um algoritmo de busca local começa a partir de uma solução candidata e a move iterativamente para uma solução vizinha . Este método é aplicável apenas se uma noção de vizinhança for definida no espaço de busca. Por exemplo, a vizinhança de uma árvore estendida é outra árvore estendida que difere apenas por um nó. Para o problema SAT, os vizinhos de uma boa atribuição são geralmente aquelas atribuições que diferem apenas no valor de uma variável. O mesmo problema pode ter várias definições de vizinhança diferentes; a otimização local com vizinhanças que limitam mudanças em k componentes da solução é freqüentemente chamada de k- ótima.
Normalmente, cada solução candidata tem mais de uma solução vizinha; a escolha daquele para o qual se mover é feita utilizando apenas as informações sobre as soluções próximas à solução atual, daí o termo de busca local . Quando a escolha da solução vizinha é feita apenas pela escolha daquela que maximiza o critério, a metaheurística assume o nome de hill climbing .
O critério para interromper a pesquisa local pode ser um limite de tempo. Outra possibilidade é parar quando a melhor solução encontrada pelo algoritmo não tiver sido melhorada para um determinado número de iterações. Os algoritmos de busca local são algoritmos subótimos, pois a busca pode parar quando a melhor solução encontrada pelo algoritmo não é a melhor do espaço de busca. Essa situação pode ocorrer mesmo que a parada seja causada pela impossibilidade de melhorar a solução atual, pois a solução ótima pode ser encontrada longe da vizinhança das soluções percorridas pelo algoritmo.
Os algoritmos de busca local são amplamente usados em problemas de otimização difíceis, como problemas de computador (especialmente inteligência artificial ), matemática , pesquisa operacional , engenharia e bioinformática .
Os problemas a seguir se prestam bem ao uso da pesquisa local :
Muitos problemas podem ser formulados de várias maneiras em termos de espaço e propósito de pesquisa. Por exemplo, para o problema do caixeiro viajante, uma solução pode ser um ciclo e o critério a ser maximizado é a combinação do número de nós e da duração do ciclo. Mas uma solução também pode ser um caminho, e transformá-lo em um ciclo pode fazer parte da meta.