ARBOL DE DECISION

Árbol de decisión
DEFINICION:
Árboles de Decisión. Técnica que permite analizar decisiones secuenciales basada en
el uso de resultados y probabilidades asociadas.
Los árboles de decisión se pueden usar para generar sistemas expertos, búsquedas
binarias y árboles de juegos, los cuales serán explicados posteriormente.
Las ventajas de un árbol de decisión son:
•

Resume los ejemplos departida, permitiendo la clasificación de nuevos casos
siempre y cuando no existan modificaciones sustanciales en las condiciones bajo
las cuales se generaron los ejemplos que sirvieron para su construcción.

•

Facilita la interpretación de la decisión adoptada.

•

Proporciona un alto grado de comprensión del conocimiento utilizado en la toma
de decisiones.

•

Explica elcomportamiento respecto a una determinada tarea de decisión.

•

Reduce el número de variables independientes.

•

Es una magnifica herramienta para el control de la gestión empresarial.

Los árboles de decisión se utilizan en cualquier proceso que implique toma de
decisiones, ejemplos de estos procesos son:
-Búsqueda binaria.
-Sistemas expertos.
-Árboles de juego

Los árboles de decisióngeneralmente son binarios, es decir que cuentan con dos
opciones, aunque esto no significa que no puedan existir árboles de tres o mas
opciones.
BÚSQUEDA BINARIA
Búsqueda binaria es el método en el cual la búsqueda partiendo al árbol en dos partes.

15

17

5

3

1

16

8

6

21

11
25

23
13

24

En el árbol anterior realizaremos una búsqueda binaria con un árbol dedecisión.

Supongamos que deseas buscar un numero x en el árbol.
- Comparamos si el numero que estamos buscando es igual a la raíz, si es igual se
devuelve la raíz y se termina la búsqueda.
- Si no es igual se compara nuevamente el numero para saber si es mayor o menor que
la raíz con lo que se despreciaría la mitad del árbol volviendo la búsqueda mas rápida.
-Si es menor recorremos labúsqueda hacia el lado izquierdo hasta encontrar el
siguiente elemento del árbol, el cual volvemos a comparar como lo hicimos con la raíz.

-Si es mayor se realiza la búsqueda hacia el lado derecho del árbol, el cual lo
tomamos como si fuera una raíz y comparamos de la misma forma que la primera raíz.
Los pasos anteriores se realizan hasta encontrar el elemento buscado o llegar a NULL
que nosindicaría que el elemento no se encuentra en el árbol.
ÁRBOLES DE JUEGO.
Los árboles de juego son una aplicación de los árboles de decisión. Tomemos por
ejemplo el conocido juego del gato y consideremos una función evalúa que acepta una
posición del tablero y nos devuelve un valor numérico (entre mas grande es este valor,
mas “buena” es esta posición). Un ejemplo de la implantación de estafunción es
considerando el numero de renglones, columnas y diagonales restantes abiertas para
un jugador menos el numero de las mismas para su oponente, por ejemplo la sig.
Posición en un juego y sus posibles continuaciones:

X

XOX
X
O
2

XO
XX
2

X

O

XO
X
XO
2

XO
X
X O
2

XO
XX
1

O

Dada una posición del tablero, el mejor movimiento siguiente esta determinado porla
consideración de todos los movimientos posibles y las posiciones resultantes. Tal
análisis no conduce sin embargo al mejor movimiento, como se ve en el ejemplo

anterior cuando las cuatro primeras posibilidades dan todas el mismo valor de
evaluación, sin embargo la cuarta posición es sin duda mejor, por lo que se debe
mejorar esta función.
Ahora se introduce la posibilidad de prevervarios movimientos. Entonces la función se
mejorara en gran medida, se inicia con cualquier posición y se determinan todos los
posibles movimientos en un árbol hasta un determinado nivel de previsión. Este árbol
se conoce como “árbol de juego” cuya profundidad es igual a la profundidad de dicho
árbol. El sig. Árbol de juego para la posición inicial del gato y un nivel de previsión de
2 se...