Razón Artificial

La ciencia y el arte de crear videojuegos

Arboles e inteligencia Artificial

Escrito por adrigm el 26 de agosto de 2010 en Inteligencia Artificial, Programación | 0 Comentarios.

Existen muchas estructuras de datos y conocerlas y saberlas aplicar es fundamental para programar. En este artículo os voy a hablar de una estructura de datos muy usada en el desarrollo de videojuegos en general y en la inteligencia artificial en particular. Los árboles.

Los árboles son una estructura de dato compuesta de nodos que a su vez tienen nodos hijos. Cada nodo está compuesto de una carga y en enlace 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 hijos 25, 96 y 12.

Los árboles se componen de un nodo principal que no tienen padre en nuestro caso es 65 que se llama tronco (por el símil con el árbol) Luego los nodos hijos que van saliendo de él se llaman ramas hasta llegar a nodos que no tienen nodos hijos que son llamados hojas.

Arboles binarios

Vamos a centrarnos en este artículo en los árboles binarios. Los árboles binarios son árboles  que tienen solo dos nodos hijos. Se va bifurcando de dos en dos, por esto lo de binarios.

Como vemos en este árbol hay como máximo dos nodos hijos en cada rama. Esto es un árbol binario.

Creando el tipo de dato

Vamos a proceder a crear este tipo de dato en python:

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)

Como vemos recibe tres valores, la carga y sus dos nodos hijos, en un principio todo definido con None. Para crear un arbol podríamos hacer lo siguiente.

arbol = Arbol(5)

Esto nos dejaría lo siguiente.

Para añadirle dos nodos hijos bastaría con lo siguiente.

arbol = Arbol(5)
arbol.izquierda = Arbol(4)
arbol.derecha = Arbol(3)

Lo que nos dejaría el siguiente diagrama.

Lo anterior se puede resumir en una 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. Hemos definido el método __str__ que sustituye el valor de print aplicado al objeto, mostrando solo la carga.

Lo más importante para un tipo de dato es tener una manera de recorrerlo, vamos a implementar una función que recorra todos los nodos del árbol y nos devuelva la suma de sus cargas

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)


def suma(arbol):
	if arbol == None: return 0
	return suma(arbol.izquierda) + suma(arbol.derecha) + arbol.carga

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

Como vemos nuestra función suma recibe el nodo padre como parámetro. Tiene la condición base de que si el arbol vale None (esta 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 None 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.

En la segunda parte veremos como aplicar los árboles a un problema de Inteligencia Artificial.

Deja un comentario