Búsqueda y Resolución de Problemas
La búsqueda y resolución de problemas es la rama de la inteligencia artificial que se ocupa de formular tareas como la exploración de un espacio de estados o configuraciones y de encontrar secuencias de acciones, asignaciones o movimientos que alcanzan un objetivo.
Definition
La resolución de problemas basada en búsqueda representa una tarea como un estado inicial, un conjunto de acciones que transforman estados, una prueba de objetivo y un costo de ruta, y la resuelve explorando sistemáticamente los estados alcanzables hasta que se encuentra un estado objetivo (o una ruta de menor costo hacia uno).
Scope
Esta área abarca la formulación de problemas como espacios de estados y los algoritmos que los exploran: búsqueda no informada (ciega) como la búsqueda en anchura y en profundidad, búsqueda informada (heurística) como A* y la búsqueda voraz del mejor primero, búsqueda adversaria para juegos de dos jugadores, y satisfacción de restricciones. Trata cómo se modelan los problemas como estados, acciones y pruebas de objetivo, y cómo se analizan la completitud, la optimalidad, el tiempo y el espacio. Excluye el aprendizaje de las heurísticas de búsqueda o las funciones de evaluación a partir de datos, lo que pertenece al subcampo separado del aprendizaje automático.
Sub-topics
Core questions
- ¿Cómo se formula una tarea del mundo real como un espacio de estados con estados, acciones y una prueba de objetivo?
- ¿Cuándo es un algoritmo de búsqueda completo (garantizado para encontrar una solución si existe) y óptimo (garantizado para encontrar una solución de menor costo)?
- ¿Cómo guía una función heurística la búsqueda hacia el objetivo preservando la optimalidad?
- ¿Cómo se puede controlar la explosión combinatoria del espacio de estados mediante la poda o el ordenamiento informado?
- ¿Cómo cambia la búsqueda cuando un adversario elige algunos de los movimientos?
Key concepts
- espacio de estados
- árbol de búsqueda y grafo de búsqueda
- búsqueda no informada (ciega)
- función heurística
- admisibilidad y consistencia
- búsqueda A*
- factor de ramificación y profundidad de búsqueda
- completitud y optimalidad
- satisfacción de restricciones
Key theories
- Heurísticas admisibles y optimalidad de A*
- Si una heurística nunca sobreestima el costo real hasta el objetivo (es admisible), la búsqueda A* expande nodos en orden de mejor primero de f = g + h y se garantiza que devuelve una solución óptima; la consistencia garantiza además que ningún nodo se reexpanda.
- Compensación entre búsqueda no informada e informada
- Las estrategias ciegas (primero en anchura, costo uniforme, primero en profundidad, profundización iterativa) difieren solo en el orden de los nodos y ofrecen garantías sin conocimiento del dominio, mientras que las estimaciones heurísticas del costo restante pueden reducir drásticamente el espacio explorado con el riesgo de perder la optimalidad si la heurística es inadmisible.
- Formulación de problemas como búsqueda en el espacio de estados
- Una amplia gama de tareas se vuelven tratables una vez que se plantean como búsqueda sobre estados conectados por acciones, lo que hace que la elección de la representación de estados y los operadores sea una decisión de diseño central que determina el factor de ramificación y la profundidad de la solución.
Clinical relevance
La búsqueda subyace a una enorme variedad de sistemas prácticos: planificación de rutas y navegación (A* en redes de carreteras), motores de rompecabezas y juegos, configuración y programación automatizadas, planificación de movimientos de robots, y como columna vertebral de la planificación automatizada y los solucionadores de restricciones utilizados en logística e investigación de operaciones.
History
La búsqueda fue central para la IA desde sus inicios, con el General Problem Solver de Newell y Simon (finales de la década de 1950) enmarcando la inteligencia como búsqueda a través de espacios de problemas. El algoritmo A* (Hart, Nilsson, Raphael, 1968) dio a la búsqueda heurística una base rigurosa de optimalidad, y la monografía de Pearl de 1984 sistematizó la teoría de la búsqueda heurística. El marco sigue siendo una lente organizativa estándar en los libros de texto de IA.
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- ¿Cuál es la diferencia entre búsqueda no informada y búsqueda informada?
- La búsqueda no informada (ciega), como la búsqueda en anchura o en profundidad, no utiliza información sobre cuán cerca está un estado del objetivo y explora puramente por la estructura del espacio de estados. La búsqueda informada (heurística) utiliza una estimación del costo restante hasta el objetivo para priorizar qué estados expandir, lo que puede ser mucho más eficiente.
- ¿Por qué A* es tan ampliamente utilizado?
- A* combina el costo real desde el inicio (g) con una estimación heurística hasta el objetivo (h), y cuando la heurística es admisible, se garantiza que encuentra una solución óptima mientras explora típicamente muchos menos estados que la búsqueda no informada. Este equilibrio entre optimalidad y eficiencia lo convierte en una opción predeterminada para la búsqueda de caminos.