Arboles Binarios & Inteligencia Artificial

Página 1

POR: Byron Rosero (4525) - Jairo Cabezas (5855)

Arboles

Binarios e Inteligencia Artificial

Seguro que todos hemos vistos muchas aplicaciones y

juegos de adivinación las típicas que te dicen que pienses en un objeto o en

una persona y en pocas preguntas te adivinan en qué estás pensando y se nos

queda una cara de tontos que no es normal. En este artículo vamos a ver por

encima como crear un adivinador simple.

Estos juegos se basan en una gran base de datos de la

que mediante preguntas que se hacen al jugador se van eliminando opciones hasta

que queda una. Suelen tener grandes algoritmos heurísticos para poder acertar

incluso con datos erróneos por parte del usuario.

Nosotros vamos a crear un sistema adivinador de

animales al que hay que “enseñarle” en un principio nuestro adivinador solo

conocerá un animal y preguntará si ese es el animal que estás pensando, si no

es así te preguntará en que animal pensabas y en que lo diferencia del que nos

ha propuesto, así irá creando un árbol de animales que al cabo de unos cuantos

miles de partidas podrá adivinar cualquier animal.

Usaremos el lenguaje de programación Python por su

sencillez y usaremos una estructura de árboles para almacenar nuestro

adivinador. Empecemos.

Árboles

Un árbol es una estructura de datos compuesta de

nodos. Cada nodo está compuesto por una carga y enlaces a sus nodos hijos.

Como vemos en este árbol las cargas son números

enteros como 65, 58, 79, etc. Los nodos tienen hijos a los que apuntan, por

ejemplo, el nodo 65 tiene 2 nodos hijos 58 y 79. 58 a su vez tiene 3 nodos

hijos 25, 96 y 12.

Los árboles se componen de un nodo que no tienen padre

en nuestro caso es 65 que se llama tronco (por el símil con el árbol). Los

nodos hijos que van saliendo de él se llaman ramas hasta llegar a nodos que no

tienen nodos hijos que se llaman nodos hojas.

Arboles binarios

Es este artículo vamos a centrarnos en los árboles

binarios. Son árboles que tienen solo dos nodos hijos. Se va bifurcando de dos

en dos, por los que se les llama binario.

Como podemos ver en el árbol superior hay dos nodos

hijos en cada rama, por tanto es un árbol binario.

Árboles binarios en C++

Vamos a crear este tipo de dato en lenguaje python:

class cArbol {

private:

Nodo valor, izq, der;

};

Podemos ver que recibe tres valores, la carga y dos

referencias a sus nodos hijos, en un principio todo definido con None. Para

crear un arbol podríamos hacer lo siguiente.

arbol = Arbol(5)

Esto nos

crearía el siguiente esquema.

Podríamos

añadirle dos nodos hijos:

arbol = Arbol(5)

arbol.izq = Arbol(4)

arbol.der = Arbol(3)

Lo anterior se puede resumir en una sola línea de

código.

arbol = Arbol(5, Arbol(4), Arbol(3))

El resultado es el mismo. Como vemos cada llamada a la

clase Arbol() solo nos genera un nodo del árbol.

Lo más importante para un tipo de dato es tener alguna

manera de poder recorrerlo, vamos a implementar una función que recorra todos

los nodos del árbol y nos devuelva la suma de las cargas de cada nodo.

class cArbol {

private:

Nodo

valor, izq, der;

public:

int

suma(cArbol Arbol){

if

(Arbol == NULL) return 0

return

(suma(Arbol.izq) + suma(Arbol.der) + Arbol.valor

arbol

= Arbol(5, Arbol(4), Arbol(3))

};

Nuestra función suma recibe el nodo padre como

parámetro. Tiene la condición base de que si el árbol vale NULL (está vacío)

pues su valor es 0 si no se cumple se llama recursivamente para calcular el

valor de sus hijos más la carga cuando alcanza un nodo que vale NULL retornará

0 y saldrá de la recursividad.

Los árboles binarios sirven para ir eligiendo entre

opciones que se van ramificando. Es útil para comportamientos y toma decisiones

de una posible I.A.

Adivinador de animales

Ahora que sabemos cómo crear estructura de árboles con

C++ vamos a crear una Inteligencia Artificial que tratará de adivinar en que

animal estamos pensando. El programa irá aprendiendo a medida que jugamos e irá

conociendo más animales. Lo que vamos a hacer es crear una estructura árbol que

se vaya ramificando poco a poco.

Veamos un ejemplo ejecución del programa para que

veáis como funciona.

Estas pensando en un animal? s

Es un pajaro? n

Qué animal era? Raton

Qué diferencia a un pajaro de un Raton? Vuela

Si el animal fuera un pajaro cual seria la respuesta? N

Estas pensando en un animal? s

vuela? s

Es un pajaro? n

Qué animal era? Aguila

Qué diferencia a un pajaro de un Aguila? caza

Si el animal fuera un pajaro cual seria la respuesta? n

Estas pensando en un animal? s

vuela? n

Es un Raton? n

Qué animal era? Perro

Qué diferencia a un Raton de un Perro? Ladra

Si el animal fuera un Raton cual seria la respuesta? n

Estas pensando en un animal? s

vuela? n

Ladra? n

Es un Raton? n

Qué animal era? Rinoceronte

Qué diferencia a un Raton de un Rinoceronte? tiene cuernos

Si el animal fuera un Raton cual seria la respuesta? n

Estas pensando en un animal? s

vuela? s

caza? n

Es un pajaro? n

Qué animal era? Buitre

Qué diferencia a un pajaro de un Buitre? come carroña

Si el animal fuera un pajaro cual seria la respuesta?

n

Estas pensando en un animal? s

vuela? n

Ladra? n

tiene cuernos? s

Es un Rinoceronte? n

Qué animal era? Elefante

Qué diferencia a un Rinoceronte de un Elefante? tienen

trompa larga

Si el animal fuera un Rinoceronte cual seria la

respuesta? n

Estas pensando en un animal? s

vuela? n

Ladra? n

tiene cuernos? n

tienen trompa larga? n

Es un Raton? n

Qué animal era? Jabali

Qué diferencia a un Raton de un Jabali? tiene

colmillos largos

Si el animal fuera un Raton cual seria la respuesta? n

Estas pensando en un animal? s

vuela? n

Ladra? n

tiene cuernos? n

tienen trompa larga? n

tiene colmillos largos? n

Es un Raton? n

Qué animal era? Jirafa

Qué diferencia a un Raton de un Jirafa? tiene el

cuello largo

Si el animal fuera un Raton cual seria la respuesta? n

Estas pensando en un animal? s

vuela? s

caza? n

come carroña? n

Es un pajaro? n

Qué animal era? Mosca

Qué diferencia a un pajaro de un Mosca? es un insecto

Si el animal fuera un pajaro cual seria la respuesta?

n

Estas pensando en un animal? s

vuela? n

Ladra? n

tiene cuernos? s

tienen trompa larga? n

parece un colmillos largos? n

Es un Rinoceronte? s

Soy el más grande!

Como se puede ver inicialmente el programa no “sabe”

nada, solo sabe el nodo inicial que aleatoriamente hemos puesto que sea pájaro

y pregunta si el animas es un pájaro. Si se le dice que no preguntará en que

animal se estaba pensando y te pedirá una diferencia con el que te ha sugerido

él para almacenarlo en su árbol. Así a medida que se va jugando e introduciendo

animales el programa va conociendo más ya que su árbol se va ramificando y

creciendo en animales.

Veamos otra

ejecución del programa más corta para poder analizarla.

Está pensando en un animal? s

Es un pájaro? n

Cómo se llama el animal? Perro

Qué pregunta distinguiría a un pájaro de un perro?

Puede volar

Si el animal fuera un perro, cuál sería la respuesta?

n

Estás pensando en un animal? s

Puede volar? n

Es un perro? n

Cómo se llama el animal? gato

Qué pregunta distinguiría a un gato de un perro? Ladra

Si el animal fuera un gato, cuál sería la respuesta? n

Estás pensando en un animal? s

Puede volar? n

Ladra? s

Es un perro? s

Soy el más grande!

Generaría el

siguiente árbol binario.

Como podermos ver según la información que le damos va

generando un árbol. Al principio de cada juego se empieza en lo más alto del

árbol (tronco) y se hace la pregunta que contiene el nodo, cuando llega a un

nodo hoja trata de adivinar. Hay que darse cuenta que todos los animales son

nodos hojas y todas las preguntas son nodos ramas obvio porque solo las

preguntas tienen o una respuesta u otra pregunta y los animales son estados finales.

Si falla pide el a usuario el nombre del nuevo animal y una diferencia con el

intento fallido, entonces añade el nuevo animal y la nueva pregunta al árbol.

Aquí está el

código completo del programa en Python.

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# Clases

#

-----------------------------------------------------------

class Arbol:

def

__init__(self, carga=None, izq=None, der=None):

self.carga = carga

self.izquierda = izq

self.derecha = der

def __str__(self):

return

str(self.carga)

#

-----------------------------------------------------------

# Funciones

#

-----------------------------------------------------------

def si(preg):

from

string import lower

resp =

lower(raw_input(preg))

return

(resp[0] == 's')

#

-----------------------------------------------------------

def main():

bucle =

True

raiz =

Arbol("pajaro")

while

bucle:

if not

si("Estas pensando en un animal? "): break

arbol

= raiz

while

arbol.izquierda != None:

if

si(arbol.carga + "? "):

arbol = arbol.izquierda

else:

arbol = arbol.derecha

#adivinar

animal

= arbol.carga

if

si("Es un " + animal + "? "):

print "Soy el más grande!"

continue

#obtener informacion

nuevo

= raw_input("Qué animal era? ")

info =

raw_input("Qué diferencia a un " + animal + " de un " +

nuevo + "? ")

indicador = "Si el animal fuera un " + animal + " cual

seria la respuesta? "

arbol.carga = info

if

si(indicador):

arbol.izquierda = Arbol(animal)

arbol.derecha = Arbol(nuevo)

else:

arbol.derecha

= Arbol(animal)

arbol.izquierda = Arbol(nuevo)

return 0

if __name__ == '__main__':

main()

La función si() devuelve verdadero si se ha

escrito S o s y falso si se ha escrito otra cosa. Es esta función la que

interactúa con el usuario.

La condición del bucle externo es 1, por lo que

seguirá hasta que se encuentre la sentencia break cuando el usuario

decida que ya ni piensa en ningún animal. El bucle while interno recorre

el árbol guiado por las respuestas que va dando el usuario. Cuando se añade un

nuevo nodo al árbol, la pregunta sustituye a la carga y los dos hijos son el

nuevo animal y la carga original del nodo que ahora es la pregunta.

Una carencia de esta implementación es que, al salir,

¡olvida todo lo que le habías enseñado con tanto cuidado! Esto se podría

solucionar almacenando la estructura del árbol en algún archivo o base de

datos.

Este código tan simple si se le implementa una base de

datos online que vaya haciendo crecer el árbol en cada juego de los usuarios.

Al cabo de un tiempo, después de muchos juegos sería capaz de adivinar

cualquier animal. Sería necesario añadir algo de heurística para evitar

animales repetidos y demás, pero se sale de la intención del artículo.