Hill Climbing Search

Hill Climbing Search
Método:
La escalada de la búsqueda se basa en primer lugar la búsqueda de profundidad. Una heurística es usada para mejorar la eficiencia de búsqueda. En cada paso, se puede estimar si una elección es probable que sea mejor que otro y para las decisiones en consecuencia.

Hill-Escalada Metodología
1. Construir una solución sub-óptima que cumpla con las restricciones del
Problema.
2. Tome la solución y hacer una mejora en ella
3. Repetidamente mejorar la solución hasta que no mejoras más son necesarias / posibles

Demostración:
Animación de ondas de choque (36k) - ver la escalada de la búsqueda
Algoritmo:
Algoritmo Hill Climbing
Éste algoritmo pertenece a los de búsqueda local, y su implementación es bastante sencilla lo cual lo hace muchas veces la opción favorita por muchos a pesar de que existan algoritmos que puedan dar mejores y más exactos resultados.

El algoritmo puede ser utilizado en la resolución de problemas que tienen varias posibles soluciones pero en las cuales algunas son mejores que otras. El algoritmo se comienza con una de estas soluciones escogidas al azar. Y poco a poco va buscando una mejora a dicha solución, por más mínima que ésta sea. Hasta que el algoritmo llega a un punto en el que ya no puede encontrar ninguna mejora a la solución y es entonces cuando termina. Por lo general cuando llega a éste punto la solución es bastante cercana a la más optima, aunque nunca se puede garantizar que llegue a la óptima.
Lo que realiza el algoritmo es el buscar maximizar o minimizar una función f(x) dada, donde “x” se refiere a estados discretos del problema. Estos estados usualmente son representados por vértices en una gráfica. Así el algoritmo va a seguir una gráfica de vértice a vértice, siempre aumentando o disminuyendo localmente el valor de la función hasta encontrar un máximo o mínimo local.
En estos debates vamos a suponer que estamos tratando de maximizar una función. Es decir, estamos tratando de encontrar un punto en el espacio de búsqueda que es mejor que todos los demás. Y por "mejor" queremos decir que la evaluación es más alta. También podríamos decir que la solución es de mejor calidad que todos los demás.
No hay razón para que no se debe tratar de minimizar una función, pero lo hace para facilitar la lectura, si asumimos que siempre están tratando de maximizar la función en lugar de mantenimiento de tener que recordar de lo que podría minimizar o maximizar.
La idea detrás de la escalada es el siguiente.
1. Elija un punto al azar en el espacio de búsqueda.
2. Considere todos los vecinos de la situación actual.
3. Elija el vecino con la mejor calidad y pasar a ese estado.
4. Repita los pasos 2 a 4 hasta que todos los estados vecinos son de menor calidad.
5. Devuelve el estado actual como el estado de disolución.

También puede presentar este algoritmo de la siguiente manera (es tomado del libro AIMA (Russell, 1995) y sigue las convenciones que hemos estado utilizando en este curso cuando se mira en las búsquedas ciegas y heurística).
Función en escalada (Problema) devuelve un estado de solución
Entradas: Problema, problema
Las variables locales: Actual, un nodo
A continuación, un nodo
Actual = MAKE-NODO (INICIAL-state [problema])
Bucle do
Siguiente = un sucesor de mayor valor de la actual
Si VALOR [Siguiente]
Actual = Siguiente
Fin
Debe tener en cuenta que este algoritmo no mantiene un árbol de búsqueda. Sólo se devuelve una solución final.
Además, si dos vecinos tienen la misma evaluación y que son a la vez la mejor calidad, entonces el algoritmo se elige entre ellos al azar.
Evaluación

Las desventajas de esta técnica puede visualizarse considerando la analogía hillclimbing:

Local Máxima: Si empieza escalador comienza a los pies, pasa mucho tiempo de subir a las cumbres de las estribaciones y estar decepcionado de que no son el objetivo.

Mesetas: Si comienza en una llanura plana en algún lugar va a vagar sin rumbo por comparación locales no determinará la mejor dirección.

Crestas: si se encuentra encima de una loma de suave pendiente, la mayoría se mueve lo llevará hacia abajo, pero no se halla en una cumbre.

Se trata de una búsqueda completa.

Costo de la búsqueda
Con esta búsqueda variable como esta es imposible determinar lo que, en su caso, la mejora de la eficiencia se hará. Una naturaleza heurística desafía dicha evaluación.

No óptimas
Este algoritmo no necesariamente encontrará la ruta más eficiente a través del espacio de estados.
Siguiente: La búsqueda del haz
Método informado: Volver.

INTEGRANTES:
ABRAHAM CHAVEZ MALFAVÓN
JESÚS ALEJANDRO GUZMÁN CHÁVEZ
ANA KAREN RIOS ROMERO
KEREN BERENICE SANTOS AGUILAR
DIANA KARINA HERNANDEZ SANTIAGO.