En la teoría de la complejidad computacional y la teoría de la computabilidad , un problema de búsqueda es un tipo de problema computacional representado por una relación binaria . Si R es una relación binaria tal que el campo ( R ) ⊆ Γ + y T es una máquina de Turing , entonces T calcula R si:
- Si x es tal que hay algo y tal que R ( x , y ) entonces T acepta x con salida z tal que R ( x , z ) (puede haber múltiples y , y T solo necesita encontrar uno de ellos)
- Si x es tal que no hay y tal que R ( x , y ) entonces T rechaza x
Intuitivamente, el problema consiste en encontrar la estructura "y" en el objeto "x". Se dice que un algoritmo resuelve el problema si existe al menos una estructura correspondiente, y luego se genera una aparición de esta estructura; de lo contrario, el algoritmo se detiene con una salida adecuada ("Elemento no encontrado" o cualquier mensaje similar).
Tales problemas ocurren con mucha frecuencia en la teoría de grafos , por ejemplo, donde la búsqueda de grafos para estructuras tales como coincidencias particulares , camarillas , conjuntos independientes , etc. son temas de interés.
Tenga en cuenta que la gráfica de una función parcial es una relación binaria, y si T calcula una función parcial, entonces hay como máximo una salida posible.
Una relación R puede verse como un problema de búsqueda, y también se dice que una máquina de Turing que calcula R lo resuelve. Cada problema de búsqueda tiene un problema de decisión correspondiente , a saber
Esta definición puede generalizarse a relaciones n- arias usando cualquier codificación adecuada que permita comprimir múltiples cadenas en una cadena (por ejemplo, enumerándolas consecutivamente con un delimitador).
Definición
Un problema de búsqueda se define por: [1]
- Un conjunto de estados
- Un estado de inicio
- Un estado de meta o una prueba de meta
- una función booleana que nos dice si un estado dado es un estado objetivo
- Una función sucesora
- un mapeo de un estado a un conjunto de nuevos estados
Objetivo
Encuentre una solución cuando no se le dé un algoritmo para resolver un problema, sino solo una especificación de cómo se ve la solución. [1]
Método de búsqueda
- Algoritmo de búsqueda genérico: dado un gráfico, nodos de inicio y nodos de objetivo, explore incrementalmente las rutas desde los nodos de inicio.
- Mantenga una frontera de rutas desde el nodo de inicio que se han explorado.
- A medida que avanza la búsqueda, la frontera se expande hacia los nodos inexplorados hasta que se encuentra un nodo objetivo.
- La forma en que se expande la frontera define la estrategia de búsqueda. [1]
Entrada: un gráfico, un conjunto de nodos de inicio, Objetivo de procedimiento booleano (n) que prueba si n es un nodo de objetivo. frontera: = {s: s es un nodo de inicio}; mientras la frontera no esté vacía: seleccione y elimine la rutade la frontera; ,> si gol (nk) return; ,> para cada vecino n de nk agreguea la frontera; ,> terminar mientras
Ver también
Referencias
- ↑ a b c Leyton-Brown, Kevin. "Búsqueda de gráficos" (PDF) . ubc . Consultado el 7 de febrero de 2013 .
Este artículo incorpora material del problema de búsqueda en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .