Algoritmo de pesquisa - Search algorithm

Representação visual de uma tabela hash , uma estrutura de dados que permite a recuperação rápida de informações.

Na ciência da computação , um algoritmo de pesquisa é um algoritmo (normalmente envolvendo uma infinidade de outros algoritmos mais específicos) que resolve um problema de pesquisa . Os algoritmos de busca funcionam para recuperar informações armazenadas dentro de alguma estrutura de dados , ou calculadas no espaço de busca de um domínio de problema, seja com valores discretos ou contínuos .

Embora os problemas de pesquisa descritos acima e a pesquisa na web sejam ambos problemas de recuperação de informações, eles geralmente são estudados como subcampos separados e são resolvidos e avaliados de maneiras diferentes. Os problemas de pesquisa na web geralmente se concentram em filtrar e localizar documentos que sejam mais relevantes para consultas humanas. Os algoritmos de pesquisa clássicos são normalmente avaliados com base na rapidez com que podem encontrar uma solução e se essa solução tem garantia de ser ótima. Embora os algoritmos de recuperação de informações devam ser rápidos, a qualidade da classificação e se os bons resultados foram deixados de fora e os ruins incluídos são mais importantes.

O algoritmo de pesquisa apropriado geralmente depende da estrutura de dados que está sendo pesquisada e também pode incluir conhecimento prévio sobre os dados. Algumas estruturas de banco de dados são especialmente construídas para tornar os algoritmos de pesquisa mais rápidos ou mais eficientes, como uma árvore de pesquisa , mapa de hash ou um índice de banco de dados .

Os algoritmos de pesquisa podem ser classificados com base em seu mecanismo de pesquisa em 3 tipos de algoritmos: linear, binário e hash. Os algoritmos de pesquisa linear verificam cada registro para aquele associado a uma chave de destino de forma linear. Pesquisas binárias ou de meio intervalo visam repetidamente o centro da estrutura de pesquisa e dividem o espaço de pesquisa pela metade. Os algoritmos de pesquisa de comparação melhoram a pesquisa linear eliminando sucessivamente registros com base em comparações das chaves até que o registro de destino seja encontrado e podem ser aplicados em estruturas de dados com uma ordem definida. Os algoritmos de busca digital funcionam com base nas propriedades dos dígitos em estruturas de dados que usam chaves numéricas. Por fim, o hashing mapeia diretamente as chaves para os registros com base em uma função hash .

Os algoritmos são frequentemente avaliados por sua complexidade computacional ou tempo de execução teórico máximo. As funções de pesquisa binárias, por exemplo, têm uma complexidade máxima de O (log n ) , ou tempo logarítmico. Isso significa que o número máximo de operações necessárias para encontrar o destino da pesquisa é uma função logarítmica do tamanho do espaço de pesquisa.

Aplicações de algoritmos de pesquisa

As aplicações específicas de algoritmos de pesquisa incluem:

Aulas

Para espaços de busca virtuais

Veja também: Solver

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

Uma subclasse importante são os métodos de busca local , que visualizam 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 escaneie o espaço movendo-se de um item para outro ao longo das bordas, por exemplo, de acordo com a descida mais íngreme ou o critério do melhor primeiro , ou em uma pesquisa estocástica . Essa categoria inclui uma grande variedade de métodos metaheurísticos gerais , como recozimento simulado , pesquisa tabu , equipes A e programação genética , que combinam heurísticas arbitrárias de maneiras específicas. O oposto da pesquisa local seriam os métodos de pesquisa globais. Este método é aplicável quando o espaço de busca não é limitado e todos os aspectos da rede dada estão disponíveis para a entidade que executa o algoritmo de busca.

Esta classe também inclui vários algoritmos de pesquisa de árvore , que visualizam os elementos como vértices de uma árvore e percorrem essa árvore em alguma ordem especial. Exemplos destes últimos incluem os métodos exaustivas tal como busca em profundidade e de procura em largura , bem como vários à base de heurística árvore de pesquisa que podam métodos tais como retrocesso e ramo e ligado . Ao contrário das metaheurísticas gerais, que na melhor das hipóteses funcionam apenas em um sentido probabilístico, muitos desses métodos de busca em árvore têm a garantia de encontrar a solução exata ou ótima, se houver tempo suficiente. Isso é chamado de " completude ".

Outra subclasse importante consiste em algoritmos para explorar a árvore do jogo de jogos de múltiplos jogadores, como xadrez ou gamão , cujos nós consistem em todas as situações de jogo possíveis que podem resultar da situação atual. O objetivo nesses problemas é encontrar a jogada que oferece a melhor chance de vitória, levando em consideração todas as jogadas possíveis do (s) oponente (s). Problemas semelhantes ocorrem quando humanos ou máquinas precisam tomar decisões sucessivas cujos resultados não estão inteiramente sob o controle de alguém, como na orientação de robôs ou no planejamento de marketing , financeiro ou estratégico militar . Esse tipo de problema - busca combinatória - tem sido amplamente 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 * e suas variantes.

Para subestruturas de uma determinada estrutura

O nome "pesquisa combinatória" é geralmente usado para algoritmos que procuram uma subestrutura específica de uma determinada estrutura discreta , como um gráfico, uma string , um grupo finito e assim por diante. O termo otimização combinatória é normalmente usado quando o objetivo é encontrar uma subestrutura com um valor máximo (ou mínimo) de algum parâmetro. (Uma vez que a subestrutura é geralmente representada no computador por um conjunto de variáveis ​​inteiras com restrições, esses problemas podem ser vistos como casos especiais de satisfação de restrição ou otimização discreta; mas eles são geralmente formulados e resolvidos em um ambiente mais abstrato, onde o representação interna não é explicitamente mencionada.)

Uma subclasse importante e amplamente estudada são os algoritmos de gráfico , em particular algoritmos de passagem de gráfico , para encontrar subestruturas específicas em um dado gráfico - como subgráficos , caminhos , circuitos e assim por diante. Os exemplos incluem o algoritmo de Dijkstra, o algoritmo de Kruskal , o algoritmo do vizinho mais próximo e o algoritmo de Prim .

Outra subclasse importante desta categoria são os algoritmos de busca de strings , que procuram padrões dentro de strings. Dois exemplos famosos são os algoritmos Boyer – Moore e Knuth – Morris – Pratt e vários algoritmos baseados na estrutura de dados da árvore de sufixo .

Pesquise o máximo de uma função

Em 1953, o estatístico americano Jack Kiefer desenvolveu a pesquisa de Fibonacci, que pode ser usada para encontrar o máximo de uma função unimodal e tem muitas outras aplicações na ciência da computação.

Para computadores quânticos

Existem também métodos de pesquisa projetados para computadores quânticos , como o algoritmo de Grover , que são teoricamente mais rápidos do que a pesquisa linear ou de força bruta, mesmo sem a ajuda de estruturas de dados ou heurísticas. Embora as idéias e aplicações por trás dos computadores quânticos ainda sejam inteiramente teóricas, estudos foram conduzidos com algoritmos como o de Grover, que reproduzem com precisão as versões físicas hipotéticas dos sistemas de computação quântica.

Motor de Otimização de Busca

Os algoritmos de pesquisa usados ​​em um mecanismo de pesquisa como o Google ordenam os resultados de pesquisa relevantes com base em uma miríade de fatores importantes. A otimização de mecanismos de pesquisa (SEO) é o processo no qual qualquer resultado de pesquisa funcionará em conjunto com o algoritmo de pesquisa para obter organicamente mais tração, atenção e cliques para seu site. Isso pode ir tão longe quanto tentar ajustar o algoritmo dos motores de busca para favorecer um resultado de pesquisa específico mais fortemente, mas a estratégia girando em torno de SEO tornou-se incrivelmente importante e relevante no mundo dos negócios.

Veja também

Categorias:

Referências

Citações

Bibliografia

Livros

Artigos

links externos