UNIVERSIDAD MAYOR DE SAN SIMÓN

FACULTAD DE CIENCIAS Y TECNOLOGÍA

INFORMÁTICA-SISTEMAS

BÚSQUEDA

ASCENSO DE COLINA

INTEGRANTES:

                        Canaviri Astete Wilder

                        Cuba Céspedes Silvestre Carlos

López Vargas Adán

                        Zarate Fernández Juan Luis

MATERIA:

Inteligencia Artificial (i)

DOCENTE:

Lic. García Pérez 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 optimo 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, que tipo de métodos y algoritmo utiliza, además ver carácterística de esta búsqueda y donde 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 mejorías o cuando se alcanza un numero 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

COMO 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 que 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:

                Desvió: Duración 30 minutos

                Bloqueo: Duración 1 hora

El decide tomar un desvió le es conveniente por el momento

Tercera Iteración

Durante el desvió se vuelve a encontrar con 2 situaciones:

                Bloqueo: 1 hora

                Accidente Transito: 4 horas

El alumno se da cuenta que todas las decisiones que tomo 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 llevo 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 evitara 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 ->desvió-> 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á que 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