Búsqueda en el Espacio de Estados
La búsqueda en el espacio de estados es la exploración sistemática del conjunto de estados alcanzables desde un estado inicial mediante acciones disponibles, con el fin de encontrar un estado que satisfaga una prueba de objetivo o una ruta que lo alcance.
Definition
La búsqueda en el espacio de estados trata un problema como un grafo cuyos nodos son estados y cuyas aristas son acciones, y procede expandiendo estados desde una frontera de acuerdo con una estrategia fija hasta que se encuentra un estado objetivo o se agota el espacio.
Scope
Este tema abarca la formulación de un problema como un espacio de estados (estados, acciones, modelo de transición, prueba de objetivo, costo de ruta) y las estrategias de búsqueda no informadas que lo exploran sin guía específica del dominio: búsqueda en anchura, búsqueda de costo uniforme, búsqueda en profundidad, búsqueda de profundidad limitada y búsqueda de profundización iterativa. Incluye el análisis de estas estrategias por completitud, optimalidad, complejidad temporal y complejidad espacial, y la distinción entre búsqueda en árbol y búsqueda en grafo con detección de estados repetidos. La guía heurística se trata en el tema separado sobre búsqueda heurística y A*.
Core questions
- ¿Cómo se representa un problema como estados, acciones, un modelo de transición y una prueba de objetivo?
- ¿Cómo difieren la búsqueda en anchura, la búsqueda en profundidad, la búsqueda de costo uniforme y la búsqueda de profundización iterativa en su ordenación de la frontera?
- ¿Cuáles son las garantías de completitud, optimalidad, tiempo y espacio de cada estrategia no informada?
- ¿Cómo evita la búsqueda en grafo la reexploración ineficiente de estados que permite la búsqueda en árbol?
Key concepts
- estado inicial y prueba de objetivo
- modelo de transición y sucesores
- frontera (lista abierta) y conjunto explorado
- búsqueda en anchura
- búsqueda en profundidad
- búsqueda de costo uniforme
- profundización iterativa
- búsqueda en árbol vs. búsqueda en grafo
Key theories
- La ordenación de la frontera determina la estrategia
- Los algoritmos de búsqueda no informada se distinguen únicamente por el orden en que eliminan estados de la frontera: una cola FIFO da búsqueda en anchura, una pila LIFO da búsqueda en profundidad, y una cola de prioridad sobre el costo de la ruta da búsqueda de costo uniforme.
- Profundización iterativa como un óptimo eficiente en espacio
- La búsqueda de profundización iterativa en profundidad ejecuta repetidamente la búsqueda en profundidad limitada con límites crecientes, combinando el espacio lineal de la búsqueda en profundidad con la completitud y optimalidad (en costos unitarios) de la búsqueda en anchura.
Clinical relevance
La búsqueda no informada en el espacio de estados es la base conceptual y de implementación para la búsqueda de rutas, la resolución de rompecabezas, el análisis de alcanzabilidad en la verificación de modelos, y como el sustrato sobre el cual se construyen la búsqueda heurística y adversaria; comprender su complejidad guía cuándo la búsqueda a ciegas es factible y cuándo se requieren heurísticas.
History
La búsqueda sistemática en el espacio de estados desciende de los algoritmos de recorrido de grafos de la década de 1950, incluyendo el trabajo de Moore y Dijkstra sobre la ruta más corta, y se enmarcó como un modelo de resolución de problemas en la IA temprana. El análisis de Korf de 1985 sobre la profundización iterativa estableció su optimalidad entre las búsquedas en árbol admisibles con espacio lineal.
Key figures
- Nils J. Nilsson
- Richard E. Korf
- Edward F. Moore
- Edsger W. Dijkstra
Related topics
Seminal works
- nilsson1971
- russell2020
Frequently asked questions
- ¿Cuándo es óptima la búsqueda en anchura?
- La búsqueda en anchura es óptima cuando cada paso tiene el mismo costo, porque encuentra el objetivo menos profundo primero. Cuando los costos de los pasos difieren, la búsqueda de costo uniforme (que ordena la frontera por el costo de ruta acumulado) es la estrategia no informada que garantiza una solución de menor costo.
- ¿Por qué usar la profundización iterativa en lugar de la búsqueda en anchura simple?
- La búsqueda en anchura almacena toda la frontera y puede requerir una memoria exponencial en la profundidad. La profundización iterativa realiza repetidamente la búsqueda en profundidad con límites de profundidad crecientes, utilizando solo memoria lineal mientras sigue siendo completa y óptima en problemas de costo unitario, a costa de reexpandir nodos poco profundos.