Algoritmo de busca

Em ciência da computação, um algoritmo de busca, em termos gerais é um algoritmo que toma um problema como entrada e retorna a solução para o problema, geralmente após resolver um número possível de soluções.
Uma solução, no aspecto de função intermediária, é um método o qual um algoritmo externo, ou mais abrangente, utilizará para solucionar um determinado problema. Esta solução é representada por elementos de um espaço de busca, definido por uma fórmula matemática ou um procedimento, tal como as raízes de uma equação com números inteiros variáveis, ou uma combinação dos dois, como os circuitos hamiltonianos de um grafo.
Já pelo aspecto de uma estrutura de dados, sendo o modelo de explanação inicial do assunto, a busca é um algoritmo projetado para encontrar um item com propriedades especificadas em uma coleção de itens. Os itens podem ser armazenadas individualmente, como registros em um banco de dados.
A maioria dos algoritmos estudados por cientistas da computação que resolvem problemas são algoritmos de busca.

História

Os algoritmos de busca têm como base o método de procura de qualquer elemento dentro de um conjunto de elementos com determinadas propriedades. Que podiam ser livros nas bibliotecas, ou dados cifrados, usados principalmente durante as duas grandes guerras. Seus formatos em linguagem computacional vieram a se desenvolver juntamente com a construção dos primeiros computadores. Sendo que a maioria de suas publicações conhecidas começa a surgir a partir da década de 1970. Atualmente os algoritmos de busca são a base de motores de buscas da Internet

Classes de algoritmos de busca

Para espaços de busca virtuais

Algoritmos para a busca de espaços virtuais são usados em problema de satisfação de restrição, onde o objetivo é encontrar um conjunto de atribuições de valores para certas variáveis que irão satisfazer específicas equações e inequações matemáticas. Eles também são utilizados quando o objetivo é encontrar uma atribuição de variável que irá maximizar ou minimizar uma determinada função dessas variáveis. Algoritmos para estes problemas incluem a base de busca por força bruta (também chamado de "ingênua" ou busca "desinformada"), e uma variedade de heurísticas que tentam explorar o conhecimento parcial sobre a estrutura do espaço, como relaxamento linear, geração de restrição, e propagação de restrições.

Algumas subclasses importantes são os métodos de busca local , que vêem os elementos do espaço de busca como os vértices de um grafo, com arestas definidas por um conjunto de heurísticas aplicáveis ao caso, e fazem a varredura do espaço, movendo-se de item para item ao longo das bordas, por exemplo de acordo com o declive máximo ou com o critério da melhor escolha, ou em uma busca estocástica. Esta categoria inclui uma grande variedade de métodos metaheurísticos gerais, como arrefecimento simulado, pesquisa tabu, times assícronos, e programação genética, que combinam heurísticas arbitrárias de maneiras específicas.

Esta classe também inclui vários algoritmos de árvore de busca, que vêem os elementos como vértices de uma Árvore (teoria dos grafos)árvore, e atravessam-na em alguma ordem especial. Exemplos disso incluem os métodos exaustivos, como em busca em profundidade e em busca em largura, bem como vários métodos de busca por poda de árvore baseados em heurística como retrocesso e ramo e encadernado . Ao contrário das metaheurísticas gerais, que trabalham melhor apenas no sentido probabilístico, muitos destes métodos de árvore de busca têm a garantia de encontrar a solução exata ou ideal, se for dado tempo suficiente.

Outra importante sub-classe consiste de algoritmos para explorar a árvore de jogo de jogos para múltiplos participantes (multiplayer), como xadrez ou gamão, cujos nós consistem em todas as situações de jogo possíveis que poderiam resultar da situação atual. O objetivo desses problemas é encontrar o movimento que oferece a melhor chance de uma vitória, tendo em conta todos os movimentos possíveis do(s) adversário(s). Problemas similares ocorrem quando as pessoas, ou máquinas, têm de tomar decisões sucessivas cujos resultados não estão totalmente sob seu controle, como em um robô, ou na orientação de marketing, financeira ou de planejamento estratégico militar. Este tipo de problema - pesquisa combinatória - tem sido extensivamente estudado no contexto da inteligência artificial. Exemplos de algoritmos para esta classe são o algoritmo minimax, poda alfa-beta e o algoritmo A*.

Para sub-estruturas de uma dada estrutura

O nome de pesquisa combinatória é geralmente usado para os algoritmos que procuram uma sub-estrutura específica de uma dada estrutura discreta, tais como um grafo, uma cadeia de caracteres, um grupo (matemática) finito, e assim por diante. O termo otimização combinatória é normalmente utilizado quando o objetivo é encontrar uma sub-estrutura com um valor máximo (ou mínimo) de algum parâmetro. (Uma vez que a sub-estrutura normalmente é representada no computador por um conjunto de variáveis de inteiros com restrições, estes problemas podem ser vistos como casos especiais de satisfação restrita ou otimização discreta, mas eles geralmente são formulados e resolvidos em um ambiente mais abstrato onde o representação interna não é explicitamente mencionada.)

Uma subclasse importante e extensivamente estudados são os algoritmos de grafos, em particular algoritmos de travessia de grafo, para encontrar determinada sub-estruturas em um dado grafo - como subgrafos, caminhos, circuitos, e assim por diante. Exemplos incluem o algoritmo de Dijkstra, algoritmo de Kruskal, o algoritmo do vizinho mais próximo, e algoritmo de Prim.

Outra subclasse importante desta categoria são os algoritmos de busca de cadeia de caracteres, que busca de padrões dentro de expressões. Dois exemplos famosos são os algoritmos Boyer-Moore e Knuth-Morris-Pratt, e vários algoritmos baseados nas estrutura de dados árvore de sufixo.

Busca pelo máximo de uma função

Em 1953, Kiefer concebeu a busca de Fibonacci, que pode ser utilizada para encontrar o máximo de uma função unimodal e tem muitas outras aplicações em ciências da computação.

Para computadores quânticos

Há também métodos de busca projetados para computadores quânticos, como o algoritmo de Grover, que são teoricamente mais rápidos do que a busca linear ou força bruta mesmo sem a ajuda de estruturas de dados ou heurísticas.

Ver também

• Busca com retrocesso
• Solucionador
• Busca de jogos
• Sistemas de recomendação também usam métodos estatísticos para classificar os resultados em conjuntos de dados muito grandes
• Algoritmos de ordenação necessários para a execução de determinados algoritmos de buscas
• Algoritmo de seleção
• Sem almoço grátis em busca e otimização
• Motor de busca
• Problema de pesquisa linear
• Pesquisa binária
• Pesquisa sequencial
• Pesquisa por interpolação

Referências

• Donald Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching. ISBN 0-201-89685-0.

Ligações externas

• Uninformed Search Project at the Wikiversity.
• Unsorted Data Searching Using Modulated Database.