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

camrename

4 marzo 2007

No me gustan nada los nombres que le ponen automáticamente las cámaras de fotos digitales a los archivos, además este nombre depende de la marca de la cámara.

Mi actual Sony Cibershot DSC-W50 nombra las fotografías con el patrón dscXXXXXX y mi difunta Canon Powershot A85 lo hacía de la siguiente forma img_XXXX. La Canon venía con un software de importación de fotografías para Windows bastante útil que comparaba las fotos que ibas a importar de la cámara con el directorio de tu equipo donde tuvieras todas tus fotos de forma que te avisaba cuando importabas algo que ya tenias y además te permitía organizar las fotografías en directorios descriptivos con la fecha en que tomaste la foto siguiendo el patrón AAAA_MM_DD.

Hasta ahora bajo GNU/Linux no conocía ningún software que te permitiera ordenar las fotografías a nivel de directorios. Por ejemplo F-Spot te permite categorizar y ver las fotografías por fechas pero de forma virtual, ya que en el disco siguen desordenadas.

Hoy he encontrado un script para shell llamado camrename que me ha hecho la vida más fácil. Este sencillo script te permite renombrar tus fotografías con el siguiente formato a partir de los datos EXIF de las mismas:

	Pyyyy.mm.dd-hh.mm.ss-seqn.jpg
	 ^^^^ ^^ ^^ ^^ ^^ ^^ ^^^^
	  |   |  |  |  |  |   |
	  |   |  |  |  |  |   +--- Image sequence number
	  |   |  |  |  |  |
	  |   |  |  |  |  +------- Seconds of image creation date/time
	  |   |  |  |  |
	  |   |  |  |  +---------- Minutes of image creation date/time
	  |   |  |  |
	  |   |  |  +------------- Hours of image creation date/time
	  |   |  |
	  |   |  +---------------- Day of month image created
	  |   |
	  |   +------------------- Month image created
	  |
	  +----------------------- Year image created

Con esto ya tengo todos los archivos bien renombrados. Cuando tenga ganas me pondré a retocar dicho script para que además me cree directorios con los días en los que tome las fotografías e incluya las correspondientes dentro.

Gracias a Geoff Kuenning por su conjunto de herramientas para manejar fotografías en GNU/Linux.

:wq