Hill climbing

Solo disponible en BuenasTareas
  • Páginas : 2 (435 palabras )
  • Descarga(s) : 0
  • Publicado : 23 de marzo de 2011
Leer documento completo
Vista previa del texto
Hill climbing
Grecia Almeyda Torres

• También conocido como asenso de colinas. • Del procedimiento de prueba existe una realimentación que ayuda al generador a decidirse por cual dirección debemoverse en el espacio de búsqueda. • En estos procesos se abandona la búsqueda si no existe un estado alternativo razonable al que se pueda mover. • Son locales, ya que deciden qué hacer, mirandoúnicamente a las consecuencias inmediatas de sus opciones.

Algoritmo
1. Seleccione aleatoriamente un nodo, n0, como nodo actual n. 2. Genere los sucesores de n (utilizando los operadores definidospara el problema) y seleccione el sucesor, nb, para el que la función v(nb) = vb tenga el valor mínimo (en caso de que existan más de un sucesor con el valor mínimo, elija uno aleatoriamente). 3. Si vb
• Puede que nunca lleguen a encontrar una solución, si sonatrapados en estados que no son el objetivo, desde donde no se puede hallar mejores estados, por ejemplo:
 Un máximo local: es mejor que sus vecinos.  Una meseta: todos los vecinos son iguales.  Un risco:que es un tipo especial de máximo local, imposible de atravesar con movimientos simples.

• Hay algunas formas que pueden ayudar a resolver estos problemas, aunque no existe garantía:
 Paraevitar máximos locales, regresar a un estado anterior y explorar en una dirección diferente.  Para casos de mesetas, reiniciar la búsqueda buscando la mejor solución actual.  Para los riscos, aplicardos o más operaciones, antes de elegir el camino.

• En todos los casos anteriores, el algoritmo llega un punto más allá del cual no se logra ningún avance. • Cuando esto sucede es obvio que debeempezarse de nuevo en otro punto. Y esto es justamente lo que hace con ascenso de cima con reinicio aleatorio, efectúa una serie de búsquedas de ascenso de cima desde estados iniciales generados...
tracking img