INTRODUCCIÓN
La clase impartida en este día ayudo a despejar muchas dudas ya que notamos que los algoritmos de búsquedas se han diseñado para explorar los espacios de búsquedas esta se consigue manteniendo uno o más caminos en memoria y registrando que alternativas se van explorando en cada punto
OBJETIVO
La siguiente clase tiene como objetivo entender los algoritmos de búsqueda locales.
ALGORITMO DE BÚSQUEDA LOCAL Y PROBLEMAS DE OPTIMIZACIÓN
Los algoritmos de búsqueda que hemos visto hasta ahora se diseñan para explorar sistemáticamente espacios de búsqueda. Esta forma sistemática se alcanza manteniendo uno o más caminos en memoria y registrando qué alternativas se han explorado en cada punto a lo largo del camino y cuáles no. Cuando se encuentra un objetivo, el camino a ese objetivo también constituye una solución al problema. En muchos problemas, sin embargo, el camino al objetivo es irrelevante. Por ejemplo, en el problema de las 8 -reinas, lo que importa es la configuración final de las reinas, no el orden en las cuales se añaden. Esta clase de problemas incluyen muchas aplicaciones importantes como diseño de circuitos integrados, disposición del suelo de una fábrica, programación del trabajo en tiendas, programación automática, optimización de redes de telecomunicaciones, dirigir un vehículo, y la gestión de carteras.
Si no importa el camino al objetivo, podemos considerar una clase diferente de algoritmos que no se preocupen en absoluto de los caminos. Los algoritmos de búsqueda local funcionan con un solo estado actual (más que múltiples caminos) y generalmente se mueve sólo a los vecinos del estado. Típicamente, los caminos seguidos por la búsqueda no se retienen. Aunque los algoritmos de búsqueda local no son sistemáticos, tienen dos ventajas claves:
(1) Usan muy poca memoria (por lo general una cantidad constante)
(2) Pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.
ALGORITMO DE BÚSQUEDA DE ASCENSIÓN DE COLINAS
- Bucles que continuamente se mueve en dirección del valor creciente (hacia arriba)
- Termina cuando alcanza "un pico" donde ningún vecino tiene un valor más alto.
Características:
- Es un algoritmo voraz, que no mantiene un árbol de búsqueda, sino sólo la representación del estado actual y el valor de su función objetivo. Mantiene una estructura de datos del nodo actual que necesita sólo el registro del estado y su valor de función objetivo.
- No se mira más allá de los vecinos inmediatos del estado actual.
- Escoge el vecino que tiene un mejor valor de la función objetivo.
- Finaliza cuando alcanza un "extremo" (máximo o mínimo, depende del pateamiento)
CONCLUSIÓN
Después de haber analizado esta temática concluimos que estos algoritmos de búsqueda son simplemente algoritmos de búsquedas se han diseñado para explorar los espacios de búsquedas que se continúan manteniendo uno o más caminos en memoria y registrando que alternativas se van explorando en cada punto
BIBLIOGRAFÍA
Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.
Macías, J 2013. ALGORITMO DE BÚSQUEDA DE ASCENSIÓN DE COLINAS. (En línea). EC. Consultado, 20 de Noviembre. 2014. Formato PDF. Disponible en: https://prezi.com/z135qjn4tnya/algoritmos-de-busqueda-local-y-problemas-de-optimizacion/
Muñoz, A. 2010. Búsqueda Local. (En línea). EC. Consultado, 20 de Noviembre. 2014. Formato PDF. Disponible en: http://sci2s.ugr.es/docencia/metah/pdf/Tema02-BusquedaLocal-13-14.pdf
