- Espacio de búsqueda
-
Espacio de búsqueda
Ejemplo de espacio de búsqueda. Gráfica de una función con múltiples óptimos locales en 2 dimensiones
En optimización, espacio de búsqueda se refiere al dominio de la función a ser optimizada. En el caso de los algoritmos de búsqueda, que manejan espacios discretos, se refiere al conjunto de todas las posibles soluciones candidatas a un problema.
Contenido
Solución candidata y solución de problema
El término solución candidata no siempre se refiere a una solución efectiva al problema. Por ejemplo, en problema de satisfacción de restricciones encontrar una combinación de variables tal que todas las restricciones sean satisfechas es el objetivo del problema. Por esta razón, el espacio de búsqueda esta constituido por soluciones que violan algunas restricciones. Algunos métodos, tales como la relajación lagrangiana, expresan restricciones como parte de la función objetivo, lo que permite una cierta flexibilidad en la resolución.
En otras técnicas, tales como Ramificación y poda sólo se aceptan soluciones que no violen las restricciones. Sin embargo, estos métodos no son aplicables sino en problemas de tamaño reducido.
Explosión combinatoria
En dominios discretos, cuando existen muchas variables o bien muchos valores posibles a asignarles, se produce explosión combinatoria, es decir, el crecimiento exponencial del tamaño del espacio de búsqueda en relación a las variables y sus dominios. Cuando los espacios de búsqueda son muy extensos, los métodos completos son incapaces de encontrar una solución en un tiempo aceptable, por lo que se opta utilizar heuristicas
Óptimos locales
En problemas de optimización una dificultad común es la existencia de óptimos locales, los cuales dan la impresión de haber encontrado el óptimo global. Diversos métodos han sido planteados para superar este problema.
Topología
Los espacios de búsqueda, dependiendo de los métodos que se utilicen para resolver el problema, pueden ser conectados o no. La desconexión entre diversas zonas del espacio de búsqueda presenta un problema para los métodos basados en vecindades, por lo que muchas veces se permite aceptar el tratamiento de soluciones infactibles a fin de conectar estas zonas dispersas.
Véase también
- Optimización combinatoria
- Búsquedas no informadas
- Algoritmo de búsqueda
- Computación evolutiva
- Optimización (matemática)
- Investigación de Operaciones
- Programación con restricciones
Categoría: Inteligencia artificial
Wikimedia foundation. 2010.
