Problema de búsqueda

En la teoría de la complejidad computacional y la teoría de la computabilidad , un problema de búsqueda es un problema computacional que consiste en encontrar una respuesta admisible para un valor de entrada dado, siempre que dicha respuesta exista. De hecho, un problema de búsqueda se especifica mediante una relación binaria R donde xRy si y solo si " y es una respuesta admisible dado x ". ^{[ nota 1 ]} Los problemas de búsqueda aparecen con frecuencia en la teoría de grafos y la optimización combinatoria , por ejemplo, la búsqueda de emparejamientos , camarillas opcionales y conjuntos estables en un grafo no dirigido dado.

Se dice que un algoritmo resuelve un problema de búsqueda si, para cada valor de entrada x , devuelve una respuesta admisible y para x cuando existe tal respuesta; de lo contrario, devuelve cualquier salida apropiada, por ejemplo, "no encontrado" para x si no existe tal respuesta.

PlanetMath define el problema de la siguiente manera: ^{[ 1 ]}

Si${\displaystyle R}$es una relación binaria tal que${\displaystyle \operatorname {field} (R)\subseteq \Gamma ^{+}}$y${\displaystyle T}$es una máquina de Turing , entonces${\displaystyle T}$calcula${\displaystyle f}$si: ^{[ nota 2 ]}

• Si${\displaystyle x}$es tal que hay algo${\displaystyle y}$de tal manera que${\displaystyle R(x,y)}$entonces${\displaystyle T}$acepta${\displaystyle x}$con salida${\displaystyle z}$de tal manera que${\displaystyle R(x,z)}$. (puede haber varios${\displaystyle y}$, y${\displaystyle T}$Solo necesitas encontrar uno de ellos)
• Si${\displaystyle x}$es tal que no hay${\displaystyle y}$de tal manera que${\displaystyle R(x,y)}$entonces${\displaystyle T}$rechaza${\displaystyle x}$.

Tenga en cuenta que la gráfica de una función parcial es una relación binaria, y si${\displaystyle T}$Si se calcula una función parcial, entonces hay como máximo una salida posible.

Un${\displaystyle R}$puede verse como un problema de búsqueda y una máquina de Turing que calcula${\displaystyle R}$También se dice que lo resuelve. Cada problema de búsqueda tiene un problema de decisión correspondiente , a saber:${\displaystyle L(R)=\{x\mid \exists yR(x,y)\}.}$

Esta definición puede generalizarse a relaciones n -arias mediante cualquier codificación adecuada que permita comprimir varias cadenas en una sola (por ejemplo, enumerándolas consecutivamente con un delimitador ).

• Operador de búsqueda ilimitada
• problema de decisión
• Problema de optimización
• Problema de conteo (complejidad)
• Problema de función
• Buscar juegos

This article incorporates material from search problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.