Inteligencia Artificial

Métodos para la solución de problemas.
2. Solución de problemas.
La solución de problemas es fundamental para la mayoría de las aplicaciones de IA;
existen principalmente dos clases de problemas que se pueden resolver mediante
procesos computables: aquéllos en los que se utiliza un algoritmo determinista que
garantiza la solución al problema y las tareas complejas que se resuelven con labúsqueda
de una solución; de ésta última clase de problemas se ocupa la IA.
2.1. Definición del problema como búsqueda en un espacio de estados.
En éste inciso se describe el esquema conocido como espacio de estados para representar
problemas.
Espacio de estados.
Un espacio de estados es un grafo cuyos nodos corresponden a estados del problema. De
éste modo, utilizando ésta representación, lasolución a los problemas se convierte en la
búsqueda de caminos ó rutas óptimas dentro del grafo.
Representación de problemas mediante espacios de estados.
Estudiaremos ejemplos de formulación de problemas utilizando la aproximación de
espacio de estados.
El problema de los bloques.
El problema consiste en encontrar un plan para reordenar la pila de bloques que se
muestra en la figura 2.1C

A

A

B

B

C

Figura 2.1. El problema de los bloques.
las restricciones al problema son las siguientes: solamente podemos mover un bloque
cada vez; un bloque puede levantarse únicamente cuando no tiene nada encima; el bloque
levantado puede colocarse sobre el piso ó sobre otro bloque.

2

Fundamentos de Inteligencia Artificial

Para resolver el problema se requiereencontrar una secuencia de movimientos válidos
que hagan la conversión. Es decir, podemos entender el problema como una exploración
de alternativas posibles; en el estado inicial únicamente tenemos una alternativa: colocar
el bloque C sobre el piso. Luego del primer movimiento encontramos ahora tres
alternativas: poner el bloque A sobre el piso, colocar el bloque A sobre C y, poner el
bloque Csobre A.
Este tipo de análisis está basado en el manejo de dos tipos de conceptos: estados del
problema y, movimientos válidos que nos hagan pasar de un estado del problema a otro
estado del mismo.
El espacio de estados para este ejemplo se muestra en la figura 2.2.
C
A
B

B
A
C

A
BC

C
B
A

B
AC

C
AB

ABC

B
AC

A
B
C

A
BC

B
C
A

C
AB

A
C
BFigura 2.2. Representación espacio-estado para el problema
de los bloques, indicando el camino de solución.
en ésta figura, los nodos corresponden a estados posibles del problema y los arcos
corrresponden a transiciones válidas entre estados posibles; el problema de encontrar un
plan de solución es equivalente a encontrar un camino entre un nodo inicial (estado
inicial) y un nodo meta (estadofinal).

FACULTAD DE MATEMATICAS

3

Fundamentos de Inteligencia Artificial

El rompecabezas de 8.
El problema consiste de una tabla de 3x3 celdas conteniendo ocho números del 1 al 8 y
una celda vacía. Como son ocho números, una celda siempre permanecerá vacía; un
número puede ‘moverse’ a una celda adyacente si ésta está vacía, dejando vacía la celda
donde se encontraba; el problemaconsiste en ordenar los números del 1 al 8 en forma
circular dejando la celda central vacía tal y como se muestra en la figura 2.3.
123
4
8
765

13
824
765

Figura 2.3. El rompecabezas de 8.
la representación espacio estado para éste problema es como sigue :
13
824
765

134
82
765

1
3
824
765

13
824
765

123
8
4
765

134
825
76

134
2
8
765

Figura 2.4.Representación espacio-estado para el problema
del rompecabezas de 8.

FACULTAD DE MATEMATICAS

4

Fundamentos de Inteligencia Artificial

El problema del juego de ajedrez.
Si queremos escribir un programa para jugar ajedrez, podríamos, en primer lugar,
especificar cuál es la posición inicial de las piezas en el tablero, cuáles son las reglas que
definen los movimientos legales y qué...