FACULTAD DE CIENCIAS Y TECNOLOGÍA

INFORMÁTICA-SISTEMAS

BÚSQUEDA

ASCENSO DE COLINA

INTEGRANTES:

Canaviri Astete Wilder

Cuba Cespedes Silvestre Carlos

Lopez Vargas Adan

Zarate Fernandez Juan Luis

MATERIA: Inteligencia Artificial (i)

DOCENTE: Lic. Garcia Perez Carmen Rosa

FECHA: 26/03/19

COCHABAMBA – BOLIVIA

INTRODUCCIÓN

Creado en 1993 por Forrest y Michelt y también con la ayuda de Richard Palmer en un estudio sobre algoritmos genéticos para la solución de problemas de optimización.

La búsqueda por ascenso de colinas son aquellas que tienen estados completos y disponen de un algoritmo que les permite recorrer los nodos para llegar a su objetivo, tienen algunos métodos de evaluación que les permite ser óptimo y completo, además no ocupa tanta memoria eso la hace optimizador de recurso.

OBJETIVO

Conocer acerca de esta búsqueda por ascenso de colinas para ver cuál es su funcionabilidad, qué tipo de métodos y algoritmo utiliza, además ver característica de esta búsqueda y dónde se emplea.

• Usa una técnica de mejoramiento iterativo
• Comienza a partir de un punto (punto actual) en el espacio de búsqueda
• Si el nuevo punto es mejor se transforma en el punto actual, si no, otro punto vecino es seleccionado y evaluado
• El método termina cuando no hay mejoras o cuando se alcanza un número predefinido de iteraciones

Escalada Simple

• Dirigirse siempre a un estado mejor que el actual
• Función heurística de proximidad (disponen de una información sobre la proximidad de cada estado a un estado objetivo)
• Es un método local, sus movimientos están determinados por ser mejores que los previos

Escalada por Máximo Pendiente

• Busca un estado no solamente mejor que el actual sino el mejor de todos los aspectos posibles

¿Cómo Funciona?

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.

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); y (2) pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.

Para entender la búsqueda local, encontraremos muy útil considerar la forma o el paisaje del espacio de estados.

El paisaje tiene «posición» (definido por el estado) y «elevación» (definido por el valor de la función de coste heurística o función objetivo). Si la elevación corresponde al costo, entonces el objetivo es encontrar el valle más bajo (un mínimo global); si la elevación corresponde a una función objetivo, entonces el objetivo es encontrar el pico más alto (un máximo global). (Puedes convertir uno en el otro solamente al insertar un signo menos.) Los algoritmos de búsqueda local exploran este paisaje. Un algoritmo de búsqueda local completo siempre encuentra un objetivo si existe; un algoritmo óptimo siempre encuentran un mínimo/máximo global.

A veces a la ascensión de colinas se le llama búsqueda local voraz porque toma un estado vecino bueno sin pensar hacia dónde ir después.

Máximo local: un máximo local es un pico que es más alto que cada uno de sus estados vecinos, pero más abajo que el máximo global. Los algoritmos de ascensión de colinas que alcanzan la vecindad de un máximo local irán hacia el pico, pero entonces se atascarán y no podrán ir a ninguna otra parte

• Crestas:

Las crestas causan una secuencia de máximos locales que hace muy difícil la navegación para los algoritmos avaros.

• Meseta: una meseta es un área del paisaje del espacio de estados donde la función de evaluación es plana. Puede ser un máximo local plano, del que no existe ninguna salida ascendente, o una terraza, por la que se pueda avanzar. Una búsqueda de ascensión de colinas podría ser incapaz de encontrar su camino en la meseta

Algoritmo Ascenso de Colina

Entrada: un problema (árbol), meta

INICIO

Bandera b=falso

ListaEspera

Actual

Si Actual esta vacío

Entonces mostrar no hay solución

Sino

Mientras b = falso

Si Actual tiene hijos

Hijos

Mejor

Si Mejor es meta

b

devolver Mejor

sino

Actual Mejor

ListaEspera.agregarPeor(Hijos)

FinSi

sino

Actual

ListaEspera.EliminarPrimero()

FinSi

FinMientras

Finsi

FIN

Ejercicio de aplicación

El ejercicio consiste de un alumno que se quiere transportar hasta la Universidad Mayor de San Simón, el cual tiene varias alternativas para llegar al destino.

El alumno por su experiencia anterior, sabe qué tiempo le toma, si llegase a pasar una alternativa, esto se puede ver en un árbol de decisión.

Ahora él quiere llegar considerando cada alternativa que podría tomar.

Solución

Primera Iteración

Usar el auto: Duración 5 minutos

Usar la bici: Duración 10 minutos

El alumno toma la decisión de usar el auto porque tarda menos tiempo, en sacar el auto a la calle y empezar a avanzar.

Segunda Iteración

Durante su avance se le presenta dos situaciones:

Desvío: Duración 30 minutos

Bloqueo: Duración 1 hora

Él decide tomar un desvío, le es conveniente por el momento

Tercera Iteración

Durante el desvío se vuelve a encontrar con 2 situaciones:

Bloqueo: 1 hora

Accidente Tránsito: 4 horas

El alumno se da cuenta que todas las decisiones que tomó no eran las más adecuadas por lo que decide volver a su segunda alternativa de la primera iteración.

Cuarta Iteración

Auto: Duración 5 min // decisión descarta

Bicicleta: Duración 10 min

El estudiante decide tomar una nueva decisión, porque tomando el auto no le llevó a su destino.

Quinta iteración

Ciclo Vía: Duración 30 minutos

Avenida: Duración 1 hora

Él sabe que tomando la ciclo vía evitará semáforos y tráfico de autos, por lo cual decide la ciclo vía.

Sexta iteración

Destino: Duración 30 minutos

Luego de haber tomar la decisión anterior, ya solo tiene una decisión que tomar que es el destino, al cual quería llegar.

Análisis de alternativas

Alternativa 1:

Casa -> auto ->desvío-> bloqueo= 0 min + 5 min + 30min + 1hora= 1hora 35min

Con esta alternativa no llega al destino.

Alternativa 2:

Casa -> bicicleta -> ciclo vía -> destino = 0 minu+10 min + 30 min + 30 min = 1 hora 10 min

Al estudiante le toma 1 hora 10 min llegar a su destino.

CRITERIOS DE BÚSQUEDA

1.- Completo

El algoritmo se puede decir que no es completo, porque no explora todo el espacio de estados. Sólo encuentra una solución. Debido a que evita la exploración de una parte del espacio de estados.

2.- Óptimo

No. Si bien se puede encontrar una solución no hay ningún tipo de garantía de que esta sea la más óptima, no se hace ningún análisis referente a cuán optima es la solución.

3.- Complejidad Temporal

Teniendo en cuenta los siguientes factores:

b : Se tiene un árbol con 2 ramas por nivel (en promedio)

d: Se tiene una profundidad de 3, teniendo en cuenta que el nodo inicial empieza desde 0

De esta forma se tiene una complejidad temporal igual a : O (b^d) —- O (2 ^ 3) = 8 seg

4.- Complejidad Espacial

Teniendo en cuenta la información anterior se tiene:

(b*d) = O (2*3 ) = 6

Ahora si se asume que cada nodo ocupa 10 bytes entonces se tienen 60 bytes de espacio total ocupado.

CONCLUSIÓN

Como conclusión podemos decir que la búsqueda por ascenso de colinas básicamente está basada en la primera búsqueda a profundidad, tienen una heurística utilizada para mejorar la eficiencia de la búsqueda haciéndola más óptima, pero dependerá qué tipo de evaluación escoja, se sabe que en cada paso que dé o recorre, se puede estimar si una elección es probable que sea mejor que otro y así sucesivamente para que pueda encontrar una mejor solución eficaz.

Contenido

OBJETIVO.. 2

Escalada simple. 2

Escalada por máximo pendiente. 2

COMO FUNCIONA.. 2

Máximo local3

• Crestas. 3

• Meseta. 3

Algoritmo ascenso de colina. 4

Ejercicio de aplicación. 6

CRITERIOS DE BÚSQUEDA.. 8

1.- Completo. 8

2.- Óptimo. 8

3.- Complejidad Temporal8

4.- Complejidad Espacial8

CONCLUSIÓN.. 9