La búsqueda sistemática es una técnica utilizada en la inteligencia artificial para resolver problemas combinatorios de manera exhaustiva. Combina métodos de búsqueda constructiva con técnicas de retroceso, lo que permite explorar sistemáticamente todas las posibles soluciones de un problema.
Relación entre la búsqueda constructiva y la búsqueda sistemática
Para comprender mejor la búsqueda sistemática, es útil examinar su relación con los métodos de búsqueda constructiva. Un ejemplo prototípico de búsqueda constructiva es la heurística del vecino más cercano para el problema del viajante de comercio (TSP, por sus siglas en inglés). Esta heurística construye una solución paso a paso, extendiendo el recorrido parcial con los vecinos más cercanos al último vértice visitado.
Si modificamos este algoritmo para que en cada paso del proceso de construcción se puedan agregar vecinos arbitrarios al recorrido parcial, obtendremos un método de búsqueda constructiva que en principio puede encontrar la solución óptima para cualquier instancia del problema TSP. Por lo tanto, un algoritmo que pueda enumerar sistemáticamente todas estas construcciones estaría garantizado de resolver de manera óptima cualquier instancia del TSP (si se le da suficiente tiempo), es decir, sería completo.
Podemos obtener fácilmente un algoritmo completo para el TSP combinando la heurística del vecino más cercano con el retroceso. En cada punto de elección del algoritmo de construcción (incluido el vértice inicial), se mantiene una lista de todas las opciones alternativas. Una vez que se ha generado un recorrido completo, el proceso de búsqueda retrocede al punto de elección más reciente en el que existen alternativas no exploradas, y la búsqueda constructiva se reanuda utilizando un vértice alternativo en ese punto. Este proceso de retroceso primero intenta opciones alternativas para decisiones recientes (que están profundas en el árbol de búsqueda correspondiente) y, una vez que se exploran todas las alternativas para un punto de elección dado, vuelve a visitar decisiones anteriores. En este último caso, todos los puntos de elección subsecuentes se generan nuevamente, es decir, en nuestro ejemplo, a partir de ese punto, primero usamos la heurística del vecino más cercano para generar otro recorrido completo y luego continuamos revisando recursivamente las decisiones tomadas en este proceso.
Complejidad de la búsqueda sistemática
Visitar todas las soluciones mediante un método de búsqueda con retroceso conduce a un algoritmo con al menos una complejidad de tiempo exponencial, que rápidamente se vuelve inmanejable incluso para instancias de problemas relativamente pequeñas. Afortunadamente, en muchas situaciones es posible podar grandes partes del árbol de búsqueda correspondiente que se puede demostrar que no contienen ninguna solución. Por ejemplo, en el caso del TSP, la búsqueda en una rama dada puede terminarse si la longitud del recorrido parcial actual más una cota inferior de la longitud de la completación del recorrido supera el recorrido más corto encontrado hasta el momento. Este tipo de algoritmo se denomina búsqueda de ramificación y acotación (branch & bound) o búsqueda A* en las comunidades de investigación operativa e inteligencia artificial, respectivamente.
Para el problema SAT, se puede diseñar fácilmente un algoritmo de retroceso que busca en un árbol de búsqueda binario en el que cada nodo corresponde a asignar un valor de verdad a una variable, que luego se fija para el subárbol debajo de ese nodo. Este árbol se puede podar considerablemente utilizando la propagación de unidades, una técnica que propaga las consecuencias lógicas de asignaciones de variables atómicas particulares hacia abajo en el árbol de búsqueda y elimina efectivamente subárboles que no pueden contener un modelo de la fórmula dada. La propagación de unidades es una de las técnicas clave utilizadas en todos los algoritmos de búsqueda sistemática de vanguardia para SAT.
La relación entre la búsqueda constructiva y el retroceso en la búsqueda sistemática
En general, el retroceso sistemático es un mecanismo recursivo que se puede utilizar para construir un algoritmo de búsqueda completo sobre un método de búsqueda constructiva. Este enfoque se puede aplicar a prácticamente cualquier algoritmo de búsqueda constructiva. Además, muchos algoritmos de búsqueda sistemática prominentes y exitosos se pueden descomponer en un método de búsqueda constructiva y alguna forma de retroceso. Cabe destacar que los métodos de construcción utilizados en este contexto no necesariamente tienen que ser tan codiciosos como la heurística del vecino más cercano. Además, aunque muchos algoritmos de búsqueda sistemática conocidos son deterministas, es posible combinar heurísticas de construcción aleatorias con retroceso para obtener algoritmos de búsqueda sistemática estocástica.
También hay cierta flexibilidad en los mecanismos de retroceso, que no tienen que revisar las decisiones de manera recursiva de la manera simple indicada anteriormente. De hecho, siempre que haya una representación razonablemente compacta de todas las soluciones candidatas no exploradas, esencialmente cualquier estrategia que garantice evaluar eventualmente todas estas conduce a un algoritmo de búsqueda completo. En particular, esto permite que el orden en el que se revisan las decisiones sea aleatorio o cambie dinámicamente según el progreso de la búsqueda, enfoques que proporcionan la base para algunos de los algoritmos de búsqueda sistemática mejor conocidos para problemas combinatorios como SAT.
Consultas habituales sobre la búsqueda sistemática en inteligencia artificial
- ¿Cuál es el objetivo de la búsqueda sistemática en inteligencia artificial?
El objetivo de la búsqueda sistemática en inteligencia artificial es encontrar la solución óptima para un problema combinatorio al explorar sistemáticamente todas las posibles soluciones.
- ¿Qué es la búsqueda constructiva?
La búsqueda constructiva es un enfoque de resolución de problemas que construye una solución paso a paso, agregando elementos o tomando decisiones de manera incremental.
- ¿Qué es el retroceso en la búsqueda sistemática?
El retroceso en la búsqueda sistemática es un mecanismo que permite regresar a puntos de elección anteriores y explorar diferentes alternativas en el proceso de construcción de la solución.
- ¿Cuál es la complejidad de la búsqueda sistemática?
La búsqueda sistemática puede tener una complejidad de tiempo exponencial, lo que significa que el tiempo requerido para encontrar la solución óptima puede aumentar rápidamente a medida que el tamaño del problema crece.
La búsqueda sistemática en inteligencia artificial es una técnica poderosa para resolver problemas combinatorios. Combina métodos de búsqueda constructiva con retroceso para explorar de manera exhaustiva todas las posibles soluciones. Aunque puede tener una complejidad de tiempo alta, existen técnicas de poda y optimización que ayudan a mejorar su eficiencia. La búsqueda sistemática es ampliamente utilizada en diferentes áreas de la inteligencia artificial y sigue siendo objeto de investigación activa.
Si quieres conocer otras notas parecidas a Búsqueda sistemática en ia: técnica exhaustiva para resolver problemas combinatorios. puedes visitar la categoría Inteligencia.