Algoritmos De Busca

Algoritmos de Busca

Na 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.

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.4 Atualmente os algoritmos de busca são a base de motores de buscas da Internet.

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