Búsqueda combinatoria
 | Este artículo incluye una lista de referencias , lecturas relacionadas o enlaces externos , pero sus fuentes siguen sin estar claras porque carece de citas en línea . ( Enero de 2013 ) |
En ciencias de la computación e inteligencia artificial , los estudios de búsqueda combinatoria buscan algoritmos para resolver casos de problemas que se cree que son difíciles en general, mediante la exploración eficiente del espacio de solución generalmente grande de estos casos. Los algoritmos de búsqueda combinatoria logran esta eficiencia reduciendo el tamaño efectivo del espacio de búsqueda o empleando heurísticas. Se garantiza que algunos algoritmos encontrarán la solución óptima, mientras que otros solo pueden devolver la mejor solución encontrada en la parte del espacio de estados que se exploró.
Los problemas clásicos de búsqueda combinatoria incluyen resolver el rompecabezas de las ocho reinas o evaluar movimientos en juegos con un gran árbol de juego , como reversi o ajedrez .
Un estudio de la teoría de la complejidad computacional ayuda a motivar la búsqueda combinatoria. Los algoritmos de búsqueda combinatoria suelen estar relacionados con problemas NP difíciles . En general, no se cree que tales problemas puedan resolverse eficazmente. Sin embargo, las diversas aproximaciones de la teoría de la complejidad sugieren que algunas instancias (por ejemplo, instancias "pequeñas") de estos problemas podrían resolverse de manera eficiente. Este es de hecho el caso, y estos casos a menudo tienen importantes ramificaciones prácticas.
Ejemplos de
Los algoritmos comunes para resolver problemas de búsqueda combinatoria incluyen:
Mirar hacia el futuro
Lookahead es un componente importante de la búsqueda combinatoria, que especifica, aproximadamente, la profundidad con la que se explora el gráfico que representa el problema. La necesidad de un límite específico en la anticipación proviene de los grandes gráficos de problemas en muchas aplicaciones, como el ajedrez informático y el Go de computadora . Una búsqueda ingenua en amplitud de estos gráficos consumiría rápidamente toda la memoria de cualquier computadora moderna. Al establecer un límite de anticipación específico, el tiempo del algoritmo se puede controlar cuidadosamente; su tiempo aumenta exponencialmente a medida que aumenta el límite de anticipación.
Las técnicas de búsqueda más sofisticadas, como la poda alfa-beta , pueden eliminar subárboles completos del árbol de búsqueda de la consideración. Cuando se utilizan estas técnicas, la anticipación no es una cantidad definida con precisión, sino la profundidad máxima buscada o algún tipo de promedio.
Ver también
- Búsqueda por fuerza bruta
- Explosión combinatoria
- Optimización combinatoria
- Algoritmo de búsqueda
- Búsqueda de espacio de estado
Referencias
- Russell y Norvig. Inteligencia artificial: un enfoque moderno .
