Universidad Autónoma Juan Misael Saracho INTELIGENCIA ARTIFICIAL

Facultad de Ingeniería en recursos naturales y tecnología Lic. Jhenny Castillo Tapia

ACTIVIDAD N°1

PROBLEMAS
Nombre y Apellido: Adrian Laime Choque
1. ¿Qué es un problema?
Es un determinado asunto o una cuestión que requiere de una solución. A nivel social, se
trata de alguna situación en concreto que, en el momento en que se logra solucionar,
aporta beneficios a la sociedad.

2. ¿Cómo define problema la I.A.?

La resolución de problemas en IA requiere, normalmente, determinar una secuencia de
acciones o decisiones. Esta secuencia será ejecutada posteriormente por un agente con el
fin de alcanzar un objetivo a partir de una situación inicial dada.

3. ¿Cómo plantear un problema?

 Inicia con la descripción del mismo en lenguaje natural, donde se establece la
meta, se delimita el problema.
 Se sigue un proceso de definición formal y estructurada que se representará en
algún lenguaje, lo cual nos lleva a otro nivel de abstracción o síntesis.
 Es importante verificar si este es similar a los problemas tipo ya definidos en la
literatura.
 También se debe determinar el espacio de soluciones, de las cuales se van a
considerar sólo la solución factible.
4. ¿Qué tipos de problemas existen y cuáles son?
Existen los siguientes:
 Problemas de un solo estado
 Problemas de estados múltiples
 Problemas de contingencias
 Problemas de exploración
5. ¿Qué características tiene un problema?
Un problema está compuesto por:
 Un estado inicial que es donde se encuentra el agente.
 Un conjunto de acciones que el agente puede emprender.
 La prueba de meta para saber si alcanzo un estado meta.
 La función costo de ruta que le asigna un valor a una ruta determinada.
Universidad Autónoma Juan Misael Saracho INTELIGENCIA ARTIFICIAL
Facultad de Ingeniería en recursos naturales y tecnología Lic. Jhenny Castillo Tapia

6. ¿Cuáles son los pasos para la solución de problemas?

Formulación de metas: se establece el objetivo.
Formulación del problema: se decide qué acciones y estados habrán de considerarse.
Búsqueda: evaluación de las posibles secuencias de acciones que le llevan a la meta y
elección de la más apta.
Ejecución: se llevan adelante la solución que presenta la búsqueda.

7. ¿A qué se denomina estado?

Denominaremos Estado a la representación de los elementos que describen el problema
en un momento

8. ¿Qué función cumple el operador?

Función de transformación sobre la representación de un estado que lo convierte en otro
estado

9. ¿Qué tipo de solución existe en espacio de estados?

Solución: Secuencia de pasos que llevan del estado inicial al final (secuencia de
operadores) o también el estado final
Tipos de solución: una cualquiera, la mejor, todas
Coste de una solución: Gasto en recursos de la aplicación de los operadores a los
estados. Puede ser importante o no según el problema y que tipo de solución busquemos

10. ¿Cuántos tipos de estrategias de búsqueda existen y cuáles son?

Se agrupan en dos grandes grupos:
 Búsquedas sin contar con información (búsqueda ciega): no existe información
acerca de la cantidad de pasos necesarios o sobre el costo de ruta para pasar del
estado de un momento dado a la meta.
 Búsqueda respaldada con información (búsqueda heurística): se posee
información muy valiosa para orientar la búsqueda para que sea más óptima.
Universidad Autónoma Juan Misael Saracho INTELIGENCIA ARTIFICIAL
Facultad de Ingeniería en recursos naturales y tecnología Lic. Jhenny Castillo Tapia

Parte Práctica
Plantear el problema la Torres de Hanoi (Investigar) como un problema de búsqueda:
Defina el problema, los pasos para la solución del problema – Especificar la
representación de los estados, y el estado inicial y meta – Especificar los operadores
para generar estados Mostrar el árbol para el caso de 3 discos – Plantea alguna
heurística para hacer más eficiente la búsqueda
El rompecabezas de la Torre de Hanoi fue inventado por el matemático francés Edouard
Lucas en 1883. Se inspiró en una leyenda acerca de un templo hindú donde el
rompecabezas fue presentado a los jóvenes sacerdotes. Al principio de los tiempos, a los
sacerdotes se les dieron tres postes y una pila de 64 discos de oro, cada disco un poco más
pequeño que el de debajo. Su misión era transferir los 64 discos de uno de los tres postes a
otro, con dos limitaciones importantes. Sólo podían mover un disco a la vez, y nunca
podían colocar un disco más grande encima de uno más pequeño. Los sacerdotes trabajaban
muy eficientemente, día y noche, moviendo un disco cada segundo. Cuando terminaran su
trabajo, dice la leyenda, el templo se desmenuzaría en polvo y el mundo se desvanecería.
Aunque la leyenda es interesante, usted no tiene que preocuparse de que el final del mundo
ocurra pronto en cualquier momento. El número de movimientos necesarios para mover
correctamente una torre de 64 discos es 264−1=18,446,744,073,709,551,615. A una
velocidad de un movimiento por segundo, ¡eso sería 584,942,417,355 años! Claramente
hay algo más en este rompecabezas de lo que parece.
La Figura muestra un ejemplo de una configuración de discos en el proceso de movimiento
del primer poste al tercero. Observe que, según especifican las reglas, los discos de cada
poste se apilan de manera que los discos más pequeños estén siempre encima de los discos
más grandes. Si usted no ha intentado resolver este rompecabezas antes, debe probarlo
ahora. No necesita discos y postes elegantes, una pila de libros o trozos de papel servirán

¿Cómo vamos a resolver este problema recursivamente? ¿Cómo resolvería usted este
problema en todo caso? ¿Cuál es nuestro caso base? Pensemos en este problema desde
Universidad Autónoma Juan Misael Saracho INTELIGENCIA ARTIFICIAL
Facultad de Ingeniería en recursos naturales y tecnología Lic. Jhenny Castillo Tapia

abajo hacia arriba. Supongamos que usted tiene una torre de cinco discos, originalmente en
un poste. Si usted ya sabía cómo mover una torre de cuatro discos al poste dos, entonces
podría mover fácilmente el disco inferior al poste tres, y luego mover la torre de cuatro
discos desde el poste dos al poste tres. Pero ¿qué tal si usted no sabe cómo mover una torre
de altura cuatro? Supongamos que usted sabía cómo mover una torre de altura tres al poste
tres; entonces sería fácil mover el cuarto disco al poste dos y mover los tres discos del poste
tres encima de aquél. Pero ¿qué tal si usted no sabe cómo mover una torre de tres discos?
¿Qué tal si usted mueve una torre de dos discos al poste dos y luego mueve el tercer disco
al poste tres, y luego mueve la torre de altura dos encima de dicho disco? Pero ¿qué tal si
todavía no sabe cómo hacer esto? Seguramente estaría de acuerdo en que mover un solo
disco al poste tres es bastante fácil, trivial incluso podría decirse. Esto suena como un caso
base.
El siguiente es un esquema de alto nivel de cómo mover una torre desde el poste de origen,
hasta el poste destino, utilizando un poste intermedio:
1. Mover una torre de altura-1 a un poste intermedio, utilizando el poste destino.
2. Mover el disco restante al poste destino.
3. Mover la torre de altura-1 desde el poste intermedio hasta el poste destino usando el
poste de origen.
Siempre y cuando obedezcamos la regla de que los discos más grandes deben permanecer
en la parte inferior de la pila, podemos usar los tres pasos anteriores recursivamente,
tratando cualquier disco más grande como si ni siquiera estuviera allí. Lo único que falta en
el esquema anterior es la identificación de un caso base. El problema de la torre de Hanoi
más simple es una torre de un disco. En ese caso, sólo necesitamos mover un solo disco a
su destino final. Una torre de un disco será nuestro caso base. Además, los pasos descritos
anteriormente nos mueven hacia el caso base reduciendo la altura de la torre en los pasos 1
y 3.
El Programa 1 muestra el código en Python para resolver el rompecabezas de la Torre de
Hanoi.

Programa 1 
Universidad Autónoma Juan Misael Saracho INTELIGENCIA ARTIFICIAL
Facultad de Ingeniería en recursos naturales y tecnología Lic. Jhenny Castillo Tapia

Note que el código en el Programa 1 es casi idéntico a la descripción en español. La clave
de la simplicidad del algoritmo es que realizamos dos llamadas recursivas diferentes, una
en la línea 3 y otra en la línea 5. En la línea 3 movemos todo menos el disco inferior de la
torre de origen hacia un poste intermedio. La siguiente línea simplemente mueve el disco
inferior a su lugar final. Luego, en la línea 5, movemos la torre desde el poste intermedio
hasta la parte superior del disco más grande. El caso base se detecta cuando la altura de la
torre es 0; en ese caso no habrá nada que hacer, por lo que la
función moverTorre simplemente regresa el control. Lo importante a tener en cuenta al
tratar el caso base de esta manera es que simplemente el regreso desde moverTorre es lo
que finalmente permite que la función moverDisco sea invocada.
La función moverDisco, que se muestra en el Programa 2, es muy simple. Todo lo que hace
es imprimir que se está moviendo un disco de un poste a otro. Si usted codifica y ejecuta el
programa moverTorre podrá ver que le da una solución muy eficiente al rompecabezas.

Programa 2

El programa en el ActiveCode 1 proporciona la solución completa para tres discos.

Solución recursiva del problema de las torres de Hanoi (hanoi)

Ahora que usted ha visto el código para moverTorre y moverDisco, es posible que se

pregunte por qué no tenemos una estructura de datos que realice explícitamente un
seguimiento de qué discos están en qué postes. He aquí una sugerencia: si usted fuera a
Universidad Autónoma Juan Misael Saracho INTELIGENCIA ARTIFICIAL
Facultad de Ingeniería en recursos naturales y tecnología Lic. Jhenny Castillo Tapia

supervisar explícitamente los discos, utilizaría probablemente tres objetos Pila, uno para
cada poste. La respuesta es que Python proporciona implícitamente las pilas que
necesitamos a través de la pila de llamadas.