Problema de busca

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes fiáveis e independentes, mas elas não cobrem todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes, inserindo-as em notas de rodapé ou no corpo do texto, nos locais indicados.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Em teoria da complexidade computacional e teoria da computabilidade, o problema de busca é um tipo de problema computacional representado por uma relação binária. Se R ​​é uma relação binária tal que o dominio (R) ⊆ Γ+ e T é um máquina de Turing, então T calcula R ​​se:

  • Se x é tal que existe algum y tal que R(x, y) então T aceita x com saída z tal que R(x, z) (pode haver vários y, e T só precisa encontrar um deles )
  • Se x é tal que não existe y tal que R(x, y) então T rejeita x

Intuitivamente, o problema consiste em encontrar uma estrutura y em um objeto x. Um algoritmo é dito para resolver o problema se ele se comporta da seguinte forma: se pelo menos uma estrutura correspondente existe, então uma ocorrência desta estrutura é emitida, caso contrário, o algoritmo pára com uma saída apropriada ("Item não encontrado" ou qualquer outra mensagem do gênero).

Por exemplo, esses problemas ocorrem muito frequentemente em teoria dos grafos, onde busca grafos para estruturas como em particular acoplamento, clique, conjunto independente, etc. são assuntos de interesse.

Observe que o grafo de uma função parcial é uma relação binária, e se T calcula uma função parcial, então há, no máximo, uma saída possível.

Uma relação R pode ser vista como um problema de busca, e uma máquina de Turing que calcula R também pode resolvê-lo. Todo problema de busca tem um correspondente problema de decisão

L(R)=\{x\mid \exists y R(x,y)\}. \,

Esta definição pode ser generalizada para relações N-ária usando qualquer codificação adequada que permite que várias sequências sejam comprimidas em uma cadeia de caracteres (por exemplo, listando-os consecutivamente com um delimitador).

Definição[editar | editar código-fonte]

Um problema de busca é definido por:[1]

  • Um conjunto de estados
  • Um estado inicial
  • Um estado meta ou teste objetivo
uma função booleana que nos diz se um determinado estado é um estado meta
  • Uma função sucessor
Linha de um mapeamento de um estado a um conjunto de novos estados

Objetivo[editar | editar código-fonte]

Encontrar uma solução quando não é dado um algoritmo para resolver um problema, mas apenas uma especificação do que uma solução parece.[2]

Método de busca[editar | editar código-fonte]

  • Algoritmo de busca genérico: dado um grafo, os nós de início, e nós finais , de forma incremental explorar caminhos a partir dos nós de início.
  • Mantenha uma fronteira de caminhos a partir do nó de início que foram exploradas.
  • Como produto de busca, a fronteira se expande para os nós inexploradas até que um nó meta é encontrado.
  • A maneira em que a fronteira é expandido define a estratégia de busca.[3]
   Entrada: um grafo,
       um conjunto de nós iniciais,
       Boolean procedure goal(n) que testa se n é um nó final. 
   fronteira := {s : s é um nó inicial};
   while fronteira não é vazio: 
       selecione e remova o caminho <n0, ..., nk> de fronteira;
       se goal(nk)
           retorne <n0, ..., nk>;
       para cada vizinho n de nk
           adicione <n0, ..., nk, n> a fronteira;
   end while

Referências

  1. Leyton-Brown, Kevin. Graph Search. ubc. Página visitada em 7 February 2013.
  2. Leyton-Brown, Kevin. Graph Search. ubc. Página visitada em 7 February 2013.
  3. Leyton-Brown, Kevin. Graph Search. ubc. Página visitada em 7 February 2013.

Ver também[editar | editar código-fonte]