Hill climbing
Páginas: 2 (435 palabras)
Publicado: 23 de marzo de 2011
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...
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...
Leer documento completo
Regístrate para leer el documento completo.