Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Algoritmo de Busqueda local
71
Algoritmo de busqueda local
Blanco Rocha Victor
Castillo Romero Edgar
Zapien Cardiel Miguel
Tabla de Contenido
Contenido
Algoritmo de búsqueda local
Qué es?
Características
Algoritmo
Aspectos
Conclusiones
Bibliografía
Frase
"Hasta la fecha, no se ha diseñado un ordenador que sea consciente de lo que esta haciendo, pero la mayor parte del tiempo, nosotros tampoco lo somos"
Marvin Minsky
Algoritmo heurisitico
Que es?
El algoritmo de busqueda local es un algoritmo heuristico lo que significa que es un procedimiento de busqueda de soluciones casi optimales a un precio computacional razonable.
Que hace?
Explora repetidamente la vecindad de una solucion en busca de una mejor solucion. Cuando no se encuentra una solucion que mejora la actual, se dice que la solucion es localmente optima
Que hace?
Características
- Es el algorimto heuristico mas sencillo
- Estabasado en el concepto de localidad
- Se mantiene en todo momentos una posible solucion al problema
- A cada paso se elige una solucion cercana a la solucion actual que la mejore
- El algoritmo termina cuando ninguna solucion cercana mejora la actual
Ascensión de colinas
Algoritmo
Algoritmo formal
- Sólo se consideran los descendientes cuya función de estimación es mejor que la del padre (poda del espacio de búsqueda).
- Se puede usar una pila y guardar los hijos mejores que el padre para poder volver atrás, pero en general el coste es prohibitivo.
- Las características de la función heurística determinan la calidad del resultado y la rapidez de la búsqueda.
Problemas
–Máximo local. Todos los vecinos tienen función heurística peor.
–Meseta. Todos los vecinos tienen la misma función heurística que el nodo actual.
–Crestas: Las crestas causan una secuencia de máximos locales que hace muy difícil la navegación para los algoritmos avaros.
Aspectos
Solución inicial
Solución inicial
Se empieza primero con una solución inicial.
Puntos a considerar:
- Sencillez
- Coste computacional
Conjunto de soluciones
Conjunto de soluciones
Conjunto de soluciones vecinas V(e) de cada solución e
Elección de la solución
Eleccion de solucion
Eleccion de la solucion vecina a cada paso
- Elegir el mejor vecino
- Elegir el primer vecino que mejore la solución actual
- Elegir una estrategia de inspección aleatoria
Conclusiones
Blanco Rocha Victor
Blanco Rocha Victor
Conclusion
Despues de analizar el algoritmo pude determinar que aunque es uno de los metodos mas faciles y comunes es eficiente y confiable ya que permite la localizacion de una solucion lo mas optima posible.
Castillo Romero Edgar
Castillo Romero Edgar
Este algoritmo tiene la ventaja en encontrar soluciones mas rápidas debido al uso de vecindades haciendo que sea superior a la búsqueda aleatoria
Zapien Cardiel Miguel
Zapien Cardiel Miguel
Conclusion
Los algoritmos de búsqueda local y problemas de optimización son una medida de solución a un problema, esto en base a la búsqueda del mejor resultado posible dentro de un espacio de resultados, a travez de un conjunto de restricciones determinados por el tipo de búsqueda local que se realice.
Bibliografia
Bibliografía
Ceccaroni, L. (2007). Inteligencia Artificial Busqueda Local.
Computer Science Department. (s.f.). Obtenido de http://www.cs.upc.edu/~bejar/ia/transpas/teoria/2-BH3-Busqueda_local.pdf
Lozano, J. A. (2015). Algorimtos de Busqueda Local. Euskera.
Mauricio G.C. Resende, J. L. (2003). PROCEDIMIENTOS DE BUSQUEDA MIOPES ALEATORIZADOS Y ADAPTATIVOS. Valencia,Espana: Redalyc.
Union, U. P. (s.f.). SlidePlayer. Obtenido de http://slideplayer.es/slide/3928460/
- Que es un algoritmo heurístico?
- Menciona al menos 3 características
- Cuales son los aspectos a considerar en la búsqueda local?