Problema de busca

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 yR(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

Um problema de busca é definido por:

• 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

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.

Método de busca

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

   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

Ver também

• Problema de decisão
• Problema de otimização
• Problema de contagem (complexidade)
• Problema função