ESPACIOS DE
•
BÚSQUEDA
INTEGRANTES:
GOMEZ GARCIA IVAN
LÓPEZ GALINDO URIEL
RAMÍREZ RÍOS ISAAC
• Cuando se resuelve un problema, se busca la mejor
solución entre un conjunto de posibles [Link]
conjunto de todas las posibles soluciones a un problema
concreto se llama Espacio de Búsqueda.
• Cada posible solución se le puede asociar un valor que indicará Sí es buena
la solución para el [Link] algoritmo genético (AG) devolverá la mejor
solución de entre todas las posibles que tenga en un momento [Link]
muchos métodos que se usan para buscar una solucion válida, pero no
necesariamente obtienen la mejor solución.
• Algunos de estos métodos son:
• Algoritmos de escalada
• Backtracking o vuelta atrás
• Búsqueda a ciegas
• Algoritmos genéticos.
Las soluciones que encuentran estos tipos de búsqueda suelen ser buenas soluciones, pero no siempre
encuentran la óptima.
ALGORITMOS DE ESCALADA
• Se llaman de escalada (o de ascensión a la colina)porque tratan de elegir en cada
paso un estado cuyo valor heurístico sea mayor que el del estado activo en ese
momento. Los algoritmos de escalada representan una técnica muy utilizada en
ciertas clases de problemas de optimización. La idea es comenzar con una solución
sub-óptima del problema y, repetidamente, mejorar la misma hasta que cierta
condición sea maximizada.
BACKTRACKING O VUELTA ATRÁS.
• Es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. Los
problemas que deben satisfacer un determinado tipo de restricciones son problemas
completos, donde el orden de los elementos de la solución no importa. La técnica va creando
todas las posibles combinaciones de elementos para obtener una solución. Su principal
virtud es que en la mayoría de las implementaciones se puede evitar combinaciones,
estableciendo funciones de acotación (o poda) reduciendo el tiempo de ejecución.
BÚSQUEDA A CIEGAS.
• Los métodos ciegos son procedimiento sistemáticos de búsqueda del estado meta en el árbol de
estado. Son llamados de métodos ciegos, porque usan estrategias de búsqueda que solo consideran
la relación de precedencia entre estados. La información sobre el beneficio, utilidad, lucro de pasar
de un estado para otro estado no es considerado. Los métodos de búsqueda ciega más conocidos
son:
Búsqueda en amplitud
Búsqueda en profundidad
Búsqueda no determinística (aleatorio)
ALGORITMOS GENÉTICOS.
• Estos algoritmos hacen evolucionar una población de individuos
sometiéndola a acciones aleatorias. Los Algoritmos Genéticos usan una
analogía directa con el comportamiento natural. Trabajan con una población
de individuos, cada uno de los cuales representa una solución factible a un
problema dado. A cada individuo se le asigna un valor ó puntuación,
relacionado con la bondad de dicha solución.
CONCLUSIÓN
• Podemos concluir que los espacios de búsqueda son fundamentales en la
resolución de problemas utilizando técnicas de búsqueda. Estos espacios de
búsqueda se refieren a la representación de todos los posibles estados o
soluciones que se pueden explorar para encontrar una solución óptima o
satisfactoria.
