cienciasdelacomputacion.com

Algoritmo primero a lo Ancho

Tipos de Busqueda, Busqueda Heuristica

Tipos de búsqueda según estrategias de control:
ALGORITMO
Disponemos de información segura sobre qué operación aplicar
BUSQUEDA EXHAUSTIVA (A CIEGAS)
Exploración del árbol de búsqueda sistemáticamente pero sin información
BUSQUEDA HEURÍSTICA (INFORMADA)
información sobre el problema (información del dominio) que permite reducir la búsqueda

Del griego “heuriskein” que significa descubrir o encontrar
La heurística es una ayuda para guiar el proceso de búsqueda.

En general, con la utilización de heurísticas no se van a conseguir
siempre resultados óptimos (la mejor solución), pero si se van a conseguir resultados de buena calidad en un tiempo razonable.

Se utilizan en problemas complejos donde aparece el problema de la explosión combinatoria. En este tipo de problemas, los algoritmos de búsqueda exhaustiva tienen costos inaceptablemente altos (sólo son válidos para problemas sencillos).

Usar información “heuristica” para “adivinar” cuál nodo expandir
la heurística aparece bajo la forma de una función de evaluación basada en la información específica para el dominio o contexto relacionado con el problema
el problema de búsqueda se puede considerar como la maximización o minimización de una función.

La función de evaluación nos proporciona una manera de evaluar un nodo “localmente” basado en una estimación del costo de llegar desde el nodo actual al nodo meta.
Problemas con la Heurística
la heurística suele ser poco certera - problema abierto
puede no encontrar la mejor respuesta - superado por algoritmo A*
La heurística es una técnica la cual produce resultados, pero no siempre.

Mucho de lo que hacemos en la vida cotidiana involucra soluciones heurísticas a los problemas. Usualmente trabaja, o usualmente trabaja lo suficientemente bien, y cuando no trabaja, entonces se trata el problema de otra forma.

La palabra heurística, no solo describe los casos donde una solución podría no ser encontrada, sino que describe los casos donde deseamos encontrar la mejor solución.

La heurística podría ayudar a encontrar soluciones que pueden ser buenas, pero talvez no la mejor solución. Obviamente la medida de cuan bueno es y la evaluación de las técnicas heurísticas, es relativa al dominio, y a la tarea específica que la solución del problema será aplicada al dominio.

Como especificar un problema en IA

Para producir una especificación formal de un problema se deben definir:

• espacio de estados válidos;
• estado inicial del problema;
• estado objetivo o final;
• estado de falla
• reglas que se pueden aplicar para pasar de un estado a otro.

Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todos los estado válidos, sino que es posible definirlo de manera más general.
El estado inicial consiste en uno o varios estados en los que puede comenzar el problema.
El estado objetivo consiste en uno o varios estados finales que se consideran solución aceptable.
Las reglas describen las acciones u operadores que posibilitan un pasaje de estados.
Una regla tiene una parte izquierda y una parte derecha.
La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla.
La parte derecha describe la operación que se lleva a cabo si se aplica la regla, es decir, como obtener el estado sucesor.
Por ejemplo, en el problema de jugar al ajedrez:
el espacio de estados son la totalidad de tableros que se puede generar en un juego de ajedrez;
el estado inicial es el tablero de 8 x 8 donde cada celda contiene un símbolo de acuerdo a las piezas situadas;
el objetivo o estado final se define como cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esté amenazado.
las reglas son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual de tablero y otra parte que describe el cambio que debe producirse en el tablero.
dado que escribir exhaustivamente todas las reglas es imposible prácticamente, (en el ejemplo, escribir todas las posiciones