Búsqueda Ascenso a la Colina(Hill Climbing)

• Algoritmo:1. Sea L una Lista de nodos iniciales, ordenarlos según su cercanía a la meta.

2. Tomar el primer nodo N. Si L está vacía, falla.

3. Si N es la meta. Regrese la trayectoria desde el nodo inicial al nodo N.

4. Si N no es una meta. Buscar los hijos de N, ordenarlos según su proximidad a la meta, etiquetándolos con la trayectoria desde el nodo inicial, y agregue los hijos al frente de L. Elimine las primeras trayectorias de la lista. Retorne al paso 2.

Búsqueda Ascenso a la Colina(Hill Climbing)

• Usa una técnica de mejoramiento iterativo.

• Comienza a partir de un punto (punto actual) en el espacio debúsqueda.

• Si el nuevo punto es mejor, se transforma en el punto actual, sino, otro punto vecino es seleccionado y evaluado.

• El método termina cuando no hay mejorías, o cuando sealcanza un número predefinido de iteraciones.

Ejemplo

• Un sistema puede encontrarse en un conjunto de estados {S0, …., S8}. Su estado inicial es S0 y los estados meta, S7y S8. Considérense los siguientes operadores y costes asociados a cada operador:

OP1: S3→S8(coste 5) OP2: S2→S3(coste 25) OP3: S5→S3(coste 20)OP4: S1→S2(coste 100) OP5: S4→S2(coste 80) OP6: S6→S7(coste 100)OP7: S0→S1(coste 10) OP8: S0→S4(coste 10) OP9: S0→S5(coste 20)OP10: S0→S6(coste 20)

• Considérense también los siguientes valores de la función heurística h, que estima el menor coste desde cada nodo a un nodo meta:

h(S0) = 40 h(S3) = 10 h(S6) = 110h(S1) = 20 h(S4) = 40 h(S7) = 0h(S2) = 20 h(S5) = 100 h(S8) = 0

• Se tiene a S0 como nodo

inicial y a S1, S4, S5 y S6

como los nodos

directamente conectados

a el.

• Se expanden los nodos

directamente conectados

a SO. En este caso se

tienen a S1, S4, S5 y S6.

• Se evalúa cual es la

mejor ruta a seguir

basado en el valor de la

función heurística.

• Se descarta el recorrido

anterior y se toma S1

como el nuevo nodo

actual.

• Se expanden los nodos

directamente conectados

a S1.

• S2 esta directamente

conectado a S1.

• Se descarta S1 y S2 se

convierte en el nuevo

nodo actual.

• Se expanden los nodos

conectados a S2. en este

caso S3.

• Se descarta S2 para

convertir a S3 en el nodo

actual.

• Se colocan S8 ya que es

el nodo que esta

directamente conectado

con S3.

• S8 tiene un valor de 0

para la función heurística

así que se considera una

meta.

• Al llegar a S8 se descarta

todo el recorrido y solo

queda el mismo como

resultado final de la

aplicación del algoritmo.

S8 es la solución.

• El algoritmo de ascenso a

la colina no contempla la

ruta sino que tiene como

función principal

encontrar una respuesta

o un estado final.