Algoritmos Voraces

9 agosto 2007

Los algoritmos voraces son algoritmos genéricos que se usan normalmente para intentar resolver problemas de optimización. Esto es, problemas en los que hay que maximizar o minimizar una función objetivo.

Se parte de un número de elementos de entrada y se van seleccionando o descartando formando el conjunto final de seleccionados que cumplen las restricciones del problema inicial.

No se tiene la posibilidad de dar marcha atrás y rehacer la selección. La solución no tiene porque ser óptima siempre.

Podemos utilizar el siguiente esquema para resolver problemas mediante algoritmos voraces:

alg
   inicializa()
   mientras (No fin() )
      seleccionaYElimina()
      si prometedor():
         anotaEnSolucion()
      fsi
   fmientras
fin

Con la función inicializa() pretendemos establecer las variables necesarias para resolver el problema y asociarles un valor. La función fin() establece el final de las iteraciones sobre el conjunto de elementos de entrada. seleccionaYElimina() es la encargada de elegir el elemento de entrada que se va a procesar y lo elimina del conjunto. prometedor() se encarga de determinar si el elemento elegido añadido al conjunto de salida hace que este mantenga las restricciones del problema. En ese caso se anotaEnSolucion().

Partiendo de este esquema podemos intentar solucionar algunos problemas mediante algoritmos voraces que suelen tener unos ordenes de complejidad bajos.

:wq

Anuncios

En otro ejercicio de clase se nos pide que diseñemos una función que, dado un natural h, devuelva un árbol binario que cumpla que es el árbol equilibrado de altura h con el menor número de nodos posible. El contenido de los nodos de dicho árbol será un natural en el rango de 1 hasta el número de nodos del árbol, de forma que todos los nodos tengan información diferente y el árbol esté ordenado.

Recordemos los conceptos de,

Árbol equilibrado: es un árbol binario de búsqueda en el que para cada nodo el número de niveles de sus subárboles izquierdo y derecho no debe diferir en más de una unidad.

Árbol binario de búsqueda: es un árbol binario que tiene la propiedad que hace que todos los elementos almacenados en el subárbol izquierdo son menores que la raíz y ésta es menor que todos los elementos del subárbol derecho.

Veamos algunos ejemplos de árboles equilibrados,

Árboles equilibrados para una altura dada

Podemos ver que el número de nodos para una altura dada coincide con la expresión 2^(altura – 1). Mi implementación se basa en una función auxiliar recursiva que vaya construyendo los árboles binarios desde las hojas a la raíz sabiendo que los nodos que compondrán el árbol irán ordenados desde 2 hasta el número de nodos además de la primera hoja etiquetada con 1 que hace que se alcance la altura pedida con el mínimo número de nodos.

Esta es mi implementación:

func generaAVL (h: natural) dev (a: BinaryTree)
alg
	// Funcion recursiva auxiliar que genera el arbol binario de búsqueda
	// a partir del número de nodos del árbol que viene dado por 2^(altura -1)
	a := generaAVLaux(2, 2^(h-1)) 
fin

func generaAVLaux (ini, fin) dev (a: BinaryTree)
var
	raiz: Entero
	izq, der: BinaryTree
alg
	raiz := (ini + fin) / 2
	
	si ((raiz - ini) = 1):		// Caso base
		si (ini = 2)
			izq := BinaryTree(BinaryTree(null,1,null), ini, null )
		| otras:
			izq := BinaryTree(null, ini, null)
		fsi
		der := BinaryTree(null, fin, null)
		a := BinaryTree(izq, raiz, der)
	| otras:			// Caso recursivo
		a := BinaryTree( generaAVLaux(ini, raiz-1), raiz, generaAVLaux(raiz+1, fin) )
	fsi
fin

Creo que se trata de una implementación un poco sucia en cuanto al código pero creo que es bastante eficiente. Se trata del ejercicio 4 del boletín de árboles de EDA.

:wq

Código de Huffman

20 abril 2007

Hace poco intenté explicar cómo se utiliza el algoritmo de Huffman para codificar e incluso encriptar una cadena de caracteres.

Llegamos a un punto en el que tenemos un árbol de Huffman y tenemos que recorrerlo para obtener la codificación asociada a cada carácter.

Arbol binario algoritmo Huffman

Esto es precisamente lo que se nos pide en clase: realizar un algoritmo que recibe un árbol binario de Huffman y devuelve dos listas, una con los caracteres y otra con las cadenas que representan el código que se le asigna al carácter. Carácter y código en las listas están relacionadas por la posición que ocupan.

Mi solución en pseudo-código sería la siguiente:

alg codigoHuffman
var
	lcar: Lista de Cadena 	// Lista de caracteres
	lcod: Lista de Cadena 	// Lista de codigos asociados a los caracteres
	a: BinaryTree		// Arbol binario de Huffman
	aux: Cadena		// Cadena auxiliar para ir almacenando los codigos
prin
	recorridoArbolHuffman (a, aux, lcar, lcod) 	//Funcion recursiva
fin

proc recorridoArbolHuffman (a: BinaryTree, aux: Cadena, ent/sal lcar, lcod: Lista de Cadena)
var
	numcar: Entero		// Número de caracteres que tiene el árbol
alg
	si a.isLeaf():		// Caso base
		numcar:= numcar + 1
		lcar.add(numcar, a.getRoot())
		lcod.add(numcar, aux)
	| otras:
		recorridoArbolHuffman( a.Left(), aux.addCaracter("0"), lcar, lcod )
		aux.removeLast()	// Borramos el último elemento de la cadena auxiliar
		recorridoArbolHuffman( a.Right(), aux.addCaracter("1"), lcar, lcod )
		aux.removeLast()
	fsi
fin

Se trata del ejercicio 3 del boletín de árboles de EDA.

:wq

Árbol monodistante

17 abril 2007

Un árbol monodistante de orden N es un árbol binario de números enteros en el que la suma de los valores de los nodos de cada camino que va desde la raíz a un nodo hoja es igual a N.

Ejemplo de árbol monodistante de orden 15:

arbol monodistante de orden 15

En un ejercicio de clase se nos pide que diseñemos una función que compruebe si un árbol es monodistante o no.

El prototipo de la función puede ser el siguiente:

func esMonodistante(a:BinaryTree; n: Natural) dev b:Boolean

La función tiene como entrada un arbol binario (BinaryTree) y un natural que indica el orden y devuelve cierto si el árbol es monodistante o falso en cualquier otro caso.

Siempre que vayamos a trabajar con árboles conviene pensar en una solución recursiva. El caso base de esta función recursiva podría ser que el árbol estuviera vacio o que el árbol sólo tuviera una hoja. En el resto de casos sólo tendríamos que comprobar que el subarbol derecho y el subarbol izquierdo son monodistantes haciendo una llamada recursiva y decrementando el orden del árbol.

Mi solución recursiva es esta:

func esMonodistante (a:BinaryTree, n:Natural) dev (b:Logico)
alg
	si a.isEmpty():   //el árbol está vacio
		b := cierto
	| a.isLeaf():     //el árbol es una hoja
		b := ( a.getRoot() = n )
	otras
		b := (esMonodistante(a.left() , n-a.getRoot())
		    Y esMonodistante(a.right(), n-a.getRoot()) )
	fsi
fin

Por si os sirve de algo se trata del Ejercicio 19 del Boletín de Árboles de la asignatura Estructuras de Datos y Algoritmos

:wq

Algoritmo de Huffman

23 marzo 2007

Se trata de un algoritmo que se usa para compresión o encriptación de datos desarrollado por David A. Huffman en 1952.

Se basa en el concepto de asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión de ficheros.

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

  1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.
  2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.
  3. Se repite el paso 2 hasta que sólo quede un árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código. Lo normal es pasar la asociación de código y símbolos a una tabla para trabajar con ella y desechar el árbol.

Como ejemplo vamos a aplicarlo a la cadena “tres_tristes_tigres”. Hay que tener en cuenta los espacios en blanco para codificar la cadena completa.

Primero. Asignamos la frecuencia de aparición (absoluta o relativa) a cada carácter de la cadena.

t (4) r (3) e (3) s (4) _ (2) i (2) g (1)

Segundo. Ordenamos de menor a mayor los caracteres según su frecuencia. Si se repiten las frecuencias no importa.

g (1) _ (2) i (2) r (3) e (3) t (4) s (4)

Tercero. Creamos un árbol con un único nodo por cada carácter (con su respectiva frecuencia).
Cuarto. Cogemos los 2 arboles con menos frecuencia y los unimos compartiendo un nuevo nodo raíz que contiene la suma de las frecuencias. Además etiquetamos la arista del nodo derecho con un 1 y del nodo izquierdo con un 0.
Quinto. Repetimos el paso anterior hasta que sólo quede un árbol.

Arbol binario algoritmo Huffman

Ahora recorremos las ramas desde las hojas hasta el nodo raíz apuntando las etiquetas de cada rama. El código de cada hoja será el inverso de cada una de las secuencias obtenidas. En el ejemplo, para el carácter “r” recorremos desde su hoja hasta la raíz obteniendo la secuencia 110 por lo que el código de Huffman asociado al carácter “r” es el inverso 011.

Para el resto de los caracteres tenemos la siguiente asociación:

s 10
t 11
e 001
r 011
i 010
_ 0001
g 0000

Vemos que los caracteres que más se repiten tienen códigos más cortos para que sea efectiva la compresión.

Fuente: Wikipedia y apuntes de Estructuras de Datos y Algoritmos del LSI.

:wq