Espacio de búsqueda

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la 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.

Solución candidata y solución de problema[editar]

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 está 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[editar]

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 por utilizar heuristicas

Óptimos locales[editar]

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[editar]

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[editar]