Resumen Metodos De Busqueda - Utn

Métodos de búsqueda





Se define el problema en términos de búsqueda en el espacio de estados que contiene el dominio de todos los posibles estados (representaciones que contienen el conjunto de toda la información que describe la situación del sistema en un momento dado). Los mecanismos que se emplean para modificar o transformar un estado del sistema se llama operadores o reglas y seusan para enlazar un estado actual con otro estado objetivo.

Dados un estado inicial (Ei) y uno final (Ef), se buscan distintas soluciones o caminos para llegar de uno a otro mediante una estructura de control.



Sistema de Producción

Es un sistema que proporciona una estructura que facilita la descripción y la ejecución de un proceso de búsqueda.

Se encuentran caracterizados por:1. Conjunto de reglas (If- Then)




2. Base de datos/Conocimiento, que tenga información sobre la tarea que estoy realizando




3. Estrategia de Control, que especifique el orden de aplicación de reglas y resuelva los conflictos entre las mismas.




4. Aplicador de reglas



Clasificación del Sistema de producción:



➢ Monótono: aquel en el cual laaplicación de una regla no prevé la posterior aplicación de otras reglas que podrían haberse aplicado cuando se seleccionó la primera.
➢ No monótono: aquel en el cual se aplican todas y cada una de las reglas que pueden ser tomadas en un momento determinado.
➢ Parcialmente Conmutativo: aquel en el cual se aplica una secuencia de reglas que transforma el estado X al estado Y por alguna permutaciónpermitida.
➢ No Parcialmente Conmutativo: aquel donde si se permutan las reglas no se llega del estado X al estado Y.
➢ Conmutativo: sistema monótono y parcialmente conmutativo. No puede volver a estado pasados.




Estrategia de control

Existen dos requisitos que debería cumplir:

• Debe causar algún cambio (provocar cambios a corto plazo)

• Debe ser sistemática (provocarcambios a largo plazo)




← Métodos de Búsqueda

Métodos sin información

Son aquellos algoritmos que buscan sin un conocimiento que pueda guiar la búsqueda, es una búsqueda a ciegas y se debe buscar en todos los nodos

Primero en Amplitud

• Genera por niveles

• Genero todos los Nodos

• Me da todas las soluciones, y elige la mejor

• No queda "Atrapado"Primero en Profundidad

• Genera por ramas

• Me da la primer solución, que puede no ser la mejor

• Puede quedar atrapado

• Se necesita menos memoria que para el anterior porque genera de a una rama por vez

• Se puede encontrar una solución sin haber explorado todo el árbol

Generación y prueba

• Genera por ramas, pero genera todo el árbol y comparaentre las soluciones para devolver la mejor.

• Es adecuado para problemas sencillos, ya que si son complejos puede consumir mucho tiempo (porque recorre todo el espacio de búsqueda)

Búsqueda bidireccional

• Debo conocer el estado inicial (nodo raíz) y el estado final (nodo solución) a fin de realizar dos búsquedas.

• Partiendo del estado inicial al final se realizara unabúsqueda y partiendo del estado final al inicial se realizara otra.

• Ambos métodos de búsqueda pueden ser diferentes, pero es necesario que uno de los métodos sea búsqueda por amplitud.

• Ejecuto los dos métodos hasta que se encuentren en un nodo



Métodos con información

Son aquellos algoritmos que operan con un conocimiento que guía la búsqueda en un sentido determinado. Esteconocimiento del dominio se representa a través de una función heurística (función que evalúa el grado de deseabilidad de un estado particular).

Heurística (Descubrir) : Es una técnica que aumenta la eficiencia de un proceso de búsqueda. Mediante su uso se puede esperar buenas (aunque no optimas) soluciones para problemas complejos en un tiempo mucho menor que los tiempos tradicionales....