Metodo heuristico

1.4. Resolución de problemas de IA   

 
Para construir un sistema que resuelva un sistema específico, es necesario:
1- Definir el problema formalmente con precisión.
2- Analizar el problema.
3- Representar el conocimiento necesario para resolver el problema.
4- Elegir la mejor técnica que resuelva el problema y aplicarla.
 
1.4.1. Definición formal del problema
El primer pasopara diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente.
Hay problemas que porser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc. ). Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir:
 
* espacio de estados válidos;
* estado inicial del problema;
* estado objetivo ofinal;
* 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 laoperació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 definecomo cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esté amenzado;
- 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 esimposible prácticamente, (en el ejemplo, escribir todas las posiciones de tablero), las reglas deben escribirse de la manera más general posible.
La representación como espacio de estados forma parte de la mayoría de los métodos de IA. Su estructura se corresponde con la resolución de problemas porque:
* permite definir formalmente el problema, mediante la necesidad de convertir unasituación dada en una situación deseada mediante un conjunto de operaciones permitidas;
* permite definir el proceso de resolución de un problema como una combinación de técnicas conocidas y búsqueda (la técnica general de exploración del espacio intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).

1.4.2. Estrategia de control: Métodos de búsqueda

 
* BúsquedaBreadth-First Search (primero en ancho)
Este algoritmo de búsqueda visita cada nodo del árbol por niveles, es decir, visita todos los nodos de un nivel antes de visitar los del siguiente. A continuación se detalla un pseudo-código de este algoritmo:
Lista_nodos = [estado_inicial];
Mientras Not Vacia(lista_nodos)
estado_actual = lista_nodos.primero;
Si EstadoFinal(estado_actual) entonces...