Diseño de Algoritmos

Comparando 4 técnicas de diseño de algoritmos

A continuación se pasa a exponer 4 de las técnicas de diseño de algoritmos más conocidas: voraz, divide y vencerás, programación dinámica y backtracking. Al contrario de lo que puede encontrarse en muchos trabajos que tratan estos temas, aquí se pretende unificar los conceptos relacionados con todas ellas. De esta manera el programador que desee usarlas, podrá aclararse en cuanto a las similitudes y diferencias que existen entre ellas, así como evaluar las ventajas e inconvenientes de aplicarlas en diferentes tipos de problemas.

Desarrollo:

Imaginemos que queremos resolver un problema que debe encontrar una parte de un agregado de datos. Dicha parte cumple una propiedad impuesta por el problema.

Algoritmo voraz:

El algoritmo más sencillo que puede ocurrírsenos es, partiendo de un agregado solución vacío, recorrer el agregado de entrada, y añadir el elemento considerado en cada paso al agregado solución siempre que se cumplan las condiciones derivadas de la propiedad que se apuntó.

Un ejemplo muy sencillo puede aportar más luz al anterior párrafo.

Así, sea un agregado de números enteros positivos de tamaño n. Supongamos, para mayor sencillez, que lo tenemos almacenado en un array c de enteros de tamaño n. El siguiente algoritmo resuelve nuestro problema:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int n=c.length;

static boolean[] algoritmo1(int p, int s){

int n=s-p+1;

boolean[] ss=new boolean[n]; //agregado solución vacío

int i=-1,k;

while(i<n-1){ //condición de terminación del recorrido

k=i+1; //candidato

i++; //eliminar candidato del agregado

if(par(c[k+p])){ //condición de prometedor

ss[k]=true; //añadir candidato a la solución

}

}

return ss;

}

static boolean par(int i){

return (i%2==0);

}

public static void main(String[] args){

solución=algoritmo1(0,n-1);

System.out.println("Los pares son: ");

for(int k=0;k<n;k++){

if(solución[k]){

System.out.println(c[k]+" es par");

}

}

}

}

Algoritmo divide y vencerás :

Un segundo algoritmo que puede ocurrírsenos es dividir el agregado en el número de partes que queramos, siempre que el tamaño sea superior a un tamaño umbral que admitamos. Obtener la solución de cada parte y combinar dichas soluciones para construir la solución al agregado completo. Para el caso de que el tamaño sea inferior o igual a umbral, la solución se obtiene mediante el algoritmo anterior (o cualquier otro conocido que no divida el agregado en partes).

El siguiente algoritmo divide el agregado en dos partes:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int umbral=2,n=c.length;

... //código de algoritmo1 y par

static boolean[] algoritmo2(int p,int s){

boolean[] ss=null;

if(p>s){ //parte vacía

;

}

else{

if(s-p+1<=umbral){ //la parte no se divide

ss=algoritmo1(p,s); //algoritmo conocido

}

else{

int m=(p+s)/2;//dividir

boolean[] ss1=algoritmo2(p,m-1);

boolean[] ss2=algoritmo2(m,s);

ss=unión(ss1,ss2); //combinar

}

}

return ss;

}

static boolean[] unión(boolean[] s1,boolean[] s2){

boolean[] s=null;

if(s1==null){

s=s2;

}

else if(s2==null){

s=s1;

}

else{

s=new boolean[s1.length+s2.length];

for(int i=0;i<s1.length;i++){

s[i]=s1[i];

}

for(int j=0;j<s2.length;j++){

s[s1.length+j]=s2[j];

}

}

return s;

}

public static void main(String[] args){

solución=algoritmo2(0,n-1);

System.out.println("Los pares son: ");

for(int k=0;k<n;k++){

if(solución[k]){

System.out.println(c[k]+" es par");

}

}

}

}

Algoritmo de programación dinámica:

Un tercer algoritmo que puede ocurrírsenos es, a partir de la de la relación que establece cómo combinar las soluciones para distintas partes de los datos de entrada, establecer los casos en que puede obtenerse la solución sin utilizar dicha relación (casos base), y partiendo de dichos casos, guardar la solución para los mismos en una matriz de registros (multidimensional), y reconstruir la solución al problema utilizando los valores almacenados en la matriz de registros.

El siguiente algoritmo soluciona el problema de encontrar los pares de un conjunto dado de esta última manera:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int n=c.length;

static boolean[][] pares= new boolean[n+1][];

//una posición más para la parte vacía

static boolean[] algoritmo3(){

pares[0]=null; //caso base: parte vacía

for(int i=1;i<=n;i++){

boolean[] cc={false}; //solución a parte

if(par(c[i-1])){

cc[0]=true; //solución a la parte

}

pares[i]=unión(pares[i-1],cc); //combinar

}

return pares[n]; //solución al todo

}

...//código de par y unión

public static void main(String[] args){

solución=algoritmo3();

System.out.println("Los pares son: ");

for(int k=0;k<n;k++){

if(solución[k]){

System.out.println(c[k]+" es par");

}

}

}

}

Algoritmo backtracking:

Un cuarto algoritmo que puede ocurrírsenos es, interpretando al agregado como un conjunto, obtener todos los subconjuntos del conjunto (cuyo número es 2n), hasta encontrar uno que cumpla con las condiciones impuestas por el

problema. Es decir, se trata de realizar una búsqueda exhaustiva. Llamamos árbol de expansión al árbol formado por todas las posibilidades que se estudian. En cada hoja hay una posible solución.

En el problema de encontrar el conjunto de pares, nos quedaremos con el subconjunto que tenga el tamaño máximo y en el que todos sean pares.

El siguiente algoritmo soluciona el problema de encontrar los pares de un conjunto dado de esta última manera:

class Pares{

static int[] c={3,5,1,7,8,9,34,56,122,44};

static boolean[] solución=null;

static int cardinal=Integer.MIN_VALUE, n=c.length;

... //código de par

static void algoritmo4(){

algoritmo4(-1,new boolean[n]);

}

static void algoritmo4(int k, boolean[] sol){

if(k==n-1){ //hoja del árbol de expansión

if(todosPares(sol)&&sol.length>cardinal){

//condición para admitir una solución mejor

cardinal=sol.length;

solución=(boolean[])sol.clone();

//para evitar efectos laterales

}

}

else{

sol[k+1]=true; //c[k+1] está

algoritmo4(k+1,sol);

sol[k+1]=false; //c[k+1] no está

algoritmo4(k+1,sol);

}

}

static boolean todosPares(boolean[] sol){

boolean b=true;

int i=0;

while(b&&i<n){

if(sol[i]){

b=par(c[i]);

}

i++;

}

return b;

}

public static void main(String[] args){

algoritmo4();

System.out.println("Los pares son: ");

for(int k=0;k<n;k++){

if(solución[k]){

System.out.println(c[k]+" es par");

}

}

}

}

Si ahora estudiamos las cotas superiores asintóticas de los algoritmos propuestos, encontramos que el 1 está en O(n), el 2 en O(nlog n) el 3 en O(n2) y el 4 en O(n2n). está claro que si todos resuelven el problema el algoritmo 1 es el más recomendado por ser el más fácil de desarrollar, entender y verificar.

Lamentablemente no siempre el algoritmo voraz (el más rápido), encuentra la solución correcta. Dependiendo del problema, podremos encontrar una solución con divide y vencerás o con programación dinámica que sea correcta. El algoritmo que siempre encuentra una solución correcta es el de backtracking pero, debido a que suelen ser exponenciales (a menos que encontremos una forma de podar la búsqueda exhaustiva), preferiremos en muchos casos conformarnos con un algoritmo voraz aproximado. Un ejemplo muy conocido en el que ocurre esto es el del llamado problema del cambio de monedas. En dicho problema se busca el reparto óptimo de unidades de moneda de un sistema monetario, de manera que se pague una cantidad c con el mínimo número de ellas. La solución voraz que consiste en elegir de entre las monedas que restan la de mayor valor sin superar a la cantidad que queda por pagar, no siempre encuentra la solución exacta. Por ejemplo si las unidades son {10,6,1} y hay que pagar 12, el voraz encontrará como solución: 1 moneda de 10 y 2 de 1, mientras que la exacta es 2 de 6. Sin embargo, no es necesario acudir al backtracking para encontrar la solución exacta. La técnica de programación dinámica la encuentra en un algoritmo que está en O(mc), siendo m el tamaño del array de unidades de moneda.

En muchas ocasiones, sin embargo, hemos de conformarnos con la solución encontrada con backtracking. Sin embargo, también podremos encontrar a veces alguna función de cota que reduzca bastante la búsqueda exhaustiva. Se trata de las llamadas técnicas de mejora del backtracking, entre las que se encuentra la de ramificación y acotación, pero esto es otra historia.

BACKTRACKING

Introducción* La vuelta del caballo* El problema de las ocho reinas* El problema de la mochila (selección óptima)* Problemas propuestos

 

Introducción

Los algoritmos de vuelta atrás se utilizan para encontrar soluciones a un problema. No siguen unas reglas para la búsqueda de la solución, simplemente una búsqueda sistemática, que más o menos viene a significar que hay que probar todo lo posible hasta encontrar la solución o encontrar que no existe solución al problema. Para conseguir este propósito, se separa la búsqueda en varias búsquedas parciales o subtareas. Asimismo, estas subtareas suelen incluir más subtareas, por lo que el tratamiento general de estos algoritmos es de naturaleza recursiva.

¿Por qué se llaman algoritmos de vuelta atrás?. Porque en el caso de no encontrar una solución en una subtarea se retrocede a la subtarea original y se prueba otra cosa distinta (una nueva subtarea distinta a las probadas anteriormente).

Puesto que a veces nos interesa conocer múltiples soluciones de un problema, estos algoritmos se pueden modificar fácilmente para obtener una única solución (si existe) o todas las soluciones posibles (si existe más de una) al problema dado.

Estos algoritmos se asemejan al recorrido en profundidad dentro de un grafo (ver sección de grafos, estructuras de datos, y recorrido de grafos, algoritmos), siendo cada subtarea un nodo del grafo. El caso es que el grafo no está definido de forma explícita (como lista o matriz de adyacencia), sino de forma implícita, es decir, que se irá creando según avance el recorrido. A menudo dicho grafo es un árbol, o no contiene ciclos, es decir, al buscar una solución es, en general, imposible llegar a una misma solución x partiendo de dos subtareas distintas a y b; o de la subtarea a es imposible llegar a la subtaréa b y viceversa.Gráficamente se puede ver así:

 

A menudo ocurre que el árbol o grafo que se genera es tan grande que encontrar una solución o encontrar la mejor solución entre varias posibles es computacionalmente muy costoso. En estos casos suelen aplicarse una serie de restricciones, de tal forma que se puedan podar algunas de las ramas, es decir, no recorrer ciertas subtareas. Esto es posible si llegado a un punto se puede demostrar que la solución que se obtendrá a partir de ese punto no será mejor que la mejor solución obtenida hasta el momento. Si se hace correctamente, la poda no impide encontrar la mejor solución.

A veces, es imposible demostrar que al hacer una poda no se esté ocultando una buena solución. Sin embargo, el problema quizás no pida la mejor solución, sino una que sea razonablemente buena y cuyo coste computacional sea bastante reducido. Esa es una buena razón para aumentar las restricciones a la hora de recorrer un nodo. Tal vez se pierda la mejor solución, pero se encontrará una aceptable en un tiempo reducido.

Los algoritmos de vuelta atrás tienen un esquema genérico, según se busque una o todas las soluciones, y puede adaptarse fácilmente según las necesidades de cada problema. A continuación se exponen estos esquemas, extraídos de Wirth (ver Bibliografía). Los bloques se agrupan con begin y end, equivalentes a los corchetes de C, además están tabulados.

- esquema para una solución:

procedimiento ensayar (paso : TipoPaso)  repetir  |  seleccionar_candidato  |  if aceptable then  |  begin  |    anotar_candidato  |    if solucion_incompleta then  |    begin  |      ensayar(paso_siguiente)  |      if no acertado then borrar_candidato  |    end  |    else begin  |      anotar_solucion  |      acertado <- cierto;  |  end  hasta que (acertado = cierto) o (candidatos_agotados)fin procedimiento

 

- esquema para todas las soluciones:

procedimiento ensayar (paso : TipoPaso)  para cada candidato hacer  |  seleccionar candidato  |  if aceptable then  |  begin  |    anotar_candidato

  |    if solucion_incompleta then  |      ensayar(paso_siguiente)      |    else   |      almacenar_solucion  |    borrar_candidato   |  end  hasta que candidatos_agotadosfin procedimiento

 

Por último, se exponen una serie de problemas típicos que se pueden resolver fácilmente con las técnicas de vuelta atrás. El primero que se expone es muy conocido. Se trata de la vuelta del caballo. Muchos problemas de los pasatiempos de los periódicos pueden resolverse con la ayuda de un ordenador y en esta web se muestran algunos de ellos.

 

La vuelta del caballo

Se dispone de un tablero rectangular, por ejemplo el tablero de ajedrez, y de un caballo, que se mueve según las reglas de este juego. El objetivo es encontrar una manera de recorrer todo el tablero partiendo de una casilla determinada, de tal forma que el caballo pase una sola vez por cada casilla. Una variante es obligar al caballo a volver a la posición de partida en el último movimiento.Por último se estudiará como encontrar todas las soluciones posibles partiendo de una misma casilla.

Para resolver el problema hay que realizar todos los movimientos posibles hasta que ya no se pueda avanzar, en cuyo caso hay que dar marcha atrás, o bien hasta que se cubra el tablero. Además, es necesario determinar la organización de los datos para implementar el algoritmo.

- ¿Cómo se mueve un caballo?. Para aquellos que no sepan jugar al ajedrez se muestra un gráfico con los ocho movimientos que puede realizar. Estos movimientos serán los ocho candidatos.

Con las coordenadas en las que se encuentre el caballo y las ocho coordenadas relativas se determina el siguiente movimiento. Las coordenas relativas se guardan en dos arrays:

ejex = [2, 1, -1, -2, -2, -1,   1,  2]ejey = [1, 2,  2,  1,  -1, -2, -2, -1]

El tablero, del tamaño que sea, se representará mediante un array bidimensional de números enteros. A continuación se muestra un gráfico con un tablero de tamaño 5x5 con todo el recorrido partiendo de la esquina superior izquierda.

 

Cuando se encuentra una solución, una variable que se pasa por referencia es puesta a 1 (cierto). Puede hacerse una variable de alcance global y simplificar un poco el código, pero esto no siempre es recomendable.

Para codificar el programa, es necesario considerar algunos aspectos más, entre otras cosas no salirse de los límites del tablero y no pisar una casilla ya cubierta (selección del candidato). Se determina que hay solución cuando ya no hay más casillas que recorrer.

A continuación se expone un código completo en C, que recubre un tablero cuadrado de lado N partiendo de la posición (0,0).

#include <stdio.h>

#define N 5#define ncuad N*N

void mover(int tablero[][N], int i, int pos_x, int pos_y, int *q);

const int ejex[8] = { -1,-2,-2,-1, 1, 2, 2, 1 }, ejey[8] = { -2,-1, 1, 2, 2, 1,-1,-2 };

int main(void){ int tablero[N][N]; /* tablero del caballo. */ int i,j,q;

/* inicializa el tablero a cero */ for (i = 0; i < N; i++) for (j = 0; j < N; j++) tablero[i][j] = 0;

/* pone el primer movimiento */ tablero[0][0] = 1; mover(tablero,2,0,0,&q);

if (q) { /* hay solucion: la muestra. */ for (i = 0; i < N; i++) { for (j = 0; j < N; j++) printf("%3d ", tablero[i][j]); putchar('\n'); } } else printf("\nNo existe solucion\n");

return 0;}

void mover(int tablero[][N],int i, int pos_x, int pos_y, int *q){ int k, u, v;

k = 0; *q = 0; do { u = pos_x + ejex[k]; v = pos_y + ejey[k]; /* seleccionar candidato */ if (u >= 0 && u < N && v >= 0 && v < N) { /* esta dentro de los limites? */ if (tablero[u][v] == 0) { /* es valido? */ tablero[u][v] = i; /* anota el candidato */ if (i < ncuad) { /* llega al final del recorrido? */ mover(tablero,i+1,u,v,q); if (!*q) tablero[u][v] = 0; /* borra el candidato */ } else *q = 1; /* hay solucion */ } } k++; } while (!*q && k < 8);}

Cambiando el valor de N puede obtenerse una solución para un tablero cuadrado de tamaño N.

A continuación, se muestra una adaptación del procedimiento que muestra todas las soluciones. Si se ejecuta para N = 5 se encuentra que hay 304 soluciones partiendo de la esquina superior izquierda.Cuando se encuentra una solución se llama a un procedimiento (no se ha codificado aquí) que imprime todo el tablero.

void mover(int tablero[][N],int i, int pos_x, int pos_y){  int k, u, v;

  for (k = 0; k < 8; k++) {    u = pos_x + ejex[k]; v = pos_y + ejey[k];     if (u >= 0 && u < N && v >= 0 && v < N) { /* esta dentro de los limites */      if (tablero[u][v] == 0) {         tablero[u][v] = i;          if (i < ncuad)   

          mover(tablero,i+1,u,v);        else imprimir_solucion(tablero);        tablero[u][v] = 0;        }    }  }}

 

El problema de las ocho reinas

Continuamos con problemas relacionados con el ajedrez. El problema que ahora se plantea es claramente, como se verá, de vuelta atrás. Se recomienda intentar resolverlo a mano.

Se trata de colocar ocho reinas sobre un tablero de ajedrez, de tal forma que ninguna amenace (pueda comerse) a otra. Para los que no sepan ajedrez deben saber que una reina amenaza a otra pieza que esté en la misma columna, fila o cualquiera de las cuatro diagonales.

La dificultad que plantea este problema es la representación de los datos. Se puede utilizar un array bidimensional de tamaño 8x8, pero las operaciones para encontrar una reina que amenace a otra son algo engorrosas y hay un truco para evitarlas. La solución aquí expuesta vuelve a ser tomada de Wirth (ver Bibliografía).

Es lógico que cada reina debe ir en una fila distinta. Por tanto, en un array se guarda la posición de cada reina en la columna que se encuentre. Ejemplo: si en la tercera fila hay una reina situada en la quinta columna, entonces la tercera posición del array guardará un 5. A este array se le llamará col.Hace falta otro array que determine si hay puesta una reina en la fila j-ésima. A este array se le llamará fila.Por último se utilizan dos arrays más para determinar las diagonales libres, y se llamarán diagb y diagc.

Para poner una reina se utiliza esta instrucción:col[i] = j ; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;

Para quitar una reina esta otra:fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;

Se considera válida la posición para este caso:if (fila[j] && diagb[i+j] && diagc[7+i-j]) entonces proceder ...

A continuación se expone el código completo en C. Se han utilizado tipos enumerados para representar los valores booleanos.

#include <stdio.h>

enum bool {FALSE, TRUE};typedef enum bool boolean;

void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[]);

int main(void){ int i; boolean q;

int col[8]; boolean fila[8],diagb[15], diagc[15];

for (i = 0; i < 8; i++) fila[i] = TRUE; for (i = 0; i < 15; i++) diagb[i] = diagc[i] = TRUE;

ensayar(0,&q,col,fila,diagb,diagc); if (q) { printf("\nSolucion:"); for (i = 0; i < 8; i++) printf(" %d", col[i]); } else printf("\nNo hay solucion");

return 0;}

void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[]){ int j;

j = 0; *q = FALSE; do { if (fila[j] && diagb[i+j] && diagc[7+i-j]) { col[i] = j; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE; if (i < 7) { /* encuentra solucion? */ ensayar(i+1,q,col,fila,diagb,diagc); if (!*q) fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE; } else *q = TRUE; /* encuentra la solucion */ } j++; } while (!*q && j < 8);}

Por último, se deja al lector que implemente un procedimiento que encuentre todas las soluciones. Si se desea complicar más entonces se puede pedir que encuentre todas las soluciones distintas, es decir, aquellas que no sean rotaciones o inversiones de otras soluciones.

Ahora que se conoce el método general, puede hacerse extensible a múltiples piezas simultáneamente.

 

El Problema de la mochila (selección óptima)

Con anterioridad se ha estudiado la posibilidad de encontrar una única solución a un problema y la posibilidad de encontrarlas todas. Pues bien, ahora se trata de encontrar la mejor solución, la solución óptima, de entre todas las soluciones.

Partiendo del esquema que genera todas las soluciones expuesto anteriormente se puede obtener la mejor solución (la solución óptima, seleccionada entre todas las soluciones) si se modifica la instrucción almacenar_solucion por esta otra:si f(solucion) > f(optimo) entonces optimo <- solucionsiendo f(s) función positiva, optimo es la mejor solucion encontrada hasta el momento, y solucion es una solucion que se está probando.

El problema de la mochila consiste en llenar una mochila con una serie de objetos que tienen una serie de pesos con un valor asociado. Es decir, se dispone de n tipos de objetos y que no hay un número limitado de cada tipo de objeto (si fuera limitado no cambia mucho el problema). Cada tipo i de objeto tiene un peso wi positivo y un valor vi

positivo asociados. La mochila tiene una capacidad de peso igual a W. Se trata de llenar la mochila de tal manera que se maximice el valor de los objetos incluidos pero respetando al mismo tiempo la restricción de capacidad. Notar que no es obligatorio que una solución óptima llegue al límite de capacidad de la mochila.

Ejemplo: se supondrá: n = 4W = 8w() = 2, 3, 4, 5v() = 3, 5, 6, 10Es decir, hay 4 tipos de objetos y la mochila tiene una capacidad de 8. Los pesos varían entre 2 y 5, y los valores relacionados varían entre 3 y 10.Una solución no óptima de valor 12 se obtiene introduciendo cuatro objetos de peso 2, o 2 de peso 4. Otra solución no óptima de valor 13 se obtiene introduciendo 2 objetos de peso 3 y 1 objeto de peso 2. ¿Cuál es la solución óptima?.

A continuación se muestra una solución al problema, variante del esquema para obtener todas las soluciones.

void mochila(int i, int r, int solucion, int *optimo){ int k;

for (k = i; k < n; k++) { if (peso[k] <= r) { mochila(k, r - peso[k], solucion + valor[k], optimo); if (solucion + valor[k] > *optimo) *optimo = solucion+valor[k]; } }}

Dicho procedimiento puede ser ejecutado de esta manera, siendo n, W, peso y valor variables globales para simplificar el programa:

n = 4,W = 8, peso[] = {2,3,4,5},

valor[] = {3,5,6,10},optimo = 0;...mochila(0, W, 0, &optimo);

 

Observar que la solución óptima se obtiene independientemente de la forma en que se ordenen los objetos.

 

Problemas propuestos

- Caminos. OIE 97.   Enunciado - Solución- Tom y Jerry (solamente el apartado 3). OIE 97.  Enunciado- Buque. OIE 98.  Enunciado- Sellos (El correo del zar). OIE 99.  Enunciado- El salto del caballo. OIE 2001.  Enunciado- Islas en el mar. IOI 92.  Enunciado (en inglés: Islands in the sea)- Números primos. IOI 94.  Enunciado (en inglés: The Primes) - Solución

- Muchos otros problemas requieren vuelta atrás, en general se trata de algoritmos auxiliares para resolver una pequeña tarea.

- También los algoritmos de vuelta atrás permiten la resolución del problema del laberinto, puesto que la vuelta atrás no es más que el recorrido sobre un grafo implícito finito o infinito. De todas formas, los problemas de laberintos se resuelven mucho mejor mediante exploración en anchura (ver grafos).

Grafos

Definición

Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos.

Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrán varias carreteras, por lo que para ir de una ciudad a otra se podrán tomar diversos caminos. Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra, etc.

El estudio de grafos es una rama de la algoritmia muy importante. Estudiaremos primero sus rasgos generales y sus recorridos fundamentales, para tener una buena base que permita comprender los algoritmos que se pueden aplicar.

 

Glosario

Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende de su representación.

Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas.

Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol (ver árboles). Varios árboles independientes forman un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos.

Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles (es decir, todos los nodos están conectados con todos), disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo.

Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A: estos son llamados grafos no dirigidos. Sin embargo, en ocasiones tenemos que las uniones son unidireccionales. Estas uniones se suelen dibujar con una flecha y definen un grafo dirigido. Cuando las aristas llevan un coste asociado (un entero al que se denomina peso) el grafo es ponderado. Una red es un grafo dirigido y ponderado.

 

Representación de grafos

Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos veremos que

adoptarán tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso o disperso.

Para nombrar los nodos utilizaremos letras mayúsculas, aunque en el código deberemos hacer corresponder cada nodo con un entero entre 1 y V (número de vértices) de cara a la manipulación de los mismos.

 

Representación por matriz de adyacencia

Es la forma más común de representación y la más directa. Consiste en una tabla de tamaño V x V, en que la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor será 0. Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el peso de la arista. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 (o con el peso) tanto la entrada a[i][j] como la entrada a[j][i], puesto que se puede recorrer en ambos sentidos.

int V,A;int a[maxV][maxV];

void inicializar(){ int i,x,y,p; char v1,v2; // Leer V y A memset(a,0,sizeof(a)); for (i=1; i<=A; i++) { scanf("%c %c %d\n",&v1,&v2,&p); x=v1-'A'; y=v2-'A'; a[x][y]=p; a[y][x]=p; } }

En esta implementación se ha supuesto que los vértices se nombran con una letra mayúscula y no hay errores en la entrada. Evidentemente, cada problema tendrá una forma de entrada distinta y la inicialización será conveniente adaptarla a cada situación. En todo caso, esta operación es sencilla si el número de nodos es pequeño. Si, por el contrario, la entrada fuese muy grande se pueden almacenar los nombres de nodos en un árbol binario de búsqueda o utilizar una tabla de dispersión, asignando un entero a cada nodo, que será el utilizado en la matriz de adyacencia.

Como se puede apreciar, la matriz de adyacencia siempre ocupa un espacio de V*V, es decir, depende solamente del número de nodos y no del de aristas, por lo que será útil para representar grafos densos.

 

Representación por lista de adyacencia

Otra forma de representar un grafo es por medio de listas que definen las aristas que conectan los nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia al nodo A.

Las listas de adyacencia serán estructuras que contendrán un valor entero (el número que identifica al nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado. En el ejemplo se ha utilizado un nodo z ficticio en la cola (ver listas, apartado cabeceras y centinelas).

struct nodo{ int v; int p; nodo *sig;};

int V,A; // vértices y aristas del grafostruct nodo *a[maxV], *z;

void inicializar(){ int i,x,y,peso; char v1,v2; struct nodo *t; z=(struct nodo *)malloc(sizeof(struct nodo)); z->sig=z; for (i=0; i<V; i++) a[i]=z; for (i=0; i<A; i++) { scanf("%c %c %d\n",&v1,&v2,&peso); x=v1-'A'; y=v2-'A';

t=(struct nodo *)malloc(sizeof(struct nodo)); t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;

t=(struct nodo *)malloc(sizeof(struct nodo)); t->v=x; t->p=peso; t->sig=a[y]; a[y]=t; }}

En este caso el espacio ocupado es O(V + A), muy distinto del necesario en la matriz de adyacencia, que era de O(V2). La representación por listas de adyacencia, por tanto, será más adecuada para grafos dispersos.

Hay que tener en cuenta un aspecto importante y es que la implementación con listas enlazadas determina fuertemente el tratamiento del grafo posterior. Como se puede ver en el código, los nodos se van añadiendo a las listas según se leen las aristas, por lo que nos encontramos que un mismo grafo con un orden distinto de las aristas en la entrada producirá listas de adyacencia diferentes y por ello el orden en que los nodos se procesen variará. Una consecuencia de esto es que si un problema tiene varias soluciones la primera que se encuentre dependerá de la entrada dada. Podría presentarse el caso de tener varias soluciones y tener que mostrarlas siguiendo un determinado

orden. Ante una situación así podría ser muy conveniente modificar la forma de meter los nodos en la lista (por ejemplo, hacerlo al final y no al principio, o incluso insertarlo en una posición adecuada), de manera que el algoritmo mismo diera las soluciones ya ordenadas.

 

Exploración de grafos

A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.

En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.

Suponiendo que el orden en que están almacenados los nodos en la estructura de datos correspondiente es A-B-C-D-E-F... (el orden alfabético), tenemos que el orden que seguiría el recorrido en profundidad sería el siguiente:

A-B-E-I-F-C-G-J-K-H-D

En un recorrido en anchura el orden sería, por contra:

A-B-C-D-E-G-H-I-J-K-F

Es decir, en el primer caso se exploran primero los verdes y luego los marrones, pasando primero por los de mayor intensidad de color. En el segundo caso se exploran primero los verdes, después los rojos, los naranjas y, por último, el rosa.

Es destacable que el nodo D es el último en explorarse en la búsqueda en profundidad pese a ser adyacente al nodo de origen (el A). Esto es debido a que primero se explora la rama del nodo C, que también conduce al nodo D.

En estos ejemplos hay que tener en cuenta que es fundamental el orden en que los nodos están almacenados en las estructuras de datos. Si, por ejemplo, el nodo D estuviera antes que el C, en la búsqueda en profundidad se tomaría primero la rama del D (con lo que el último en visitarse sería el C), y en la búsqueda en anchura se exploraría antes el H que el G.

 

Búsqueda en profundidad

Se implementa de forma recursiva, aunque también puede realizarse con una pila. Se utiliza un array val para almacenar el orden en que fueron explorados los vértices. Para ello se incrementa una variable global id (inicializada a 0) cada vez que se visita un nuevo vértice y se almacena id en la entrada del array val correspondiente al vértice que se está explorando.

La siguiente función realiza un máximo de V (el número total de vértices) llamadas a la función visitar, que implementamos aquí en sus dos variantes: representación por matriz de adyacencia y por listas de adyacencia.

int id=0;int val[V];

void buscar(){ int k; for (k=1; k<=V; k++) val[k]=0; for (k=1; k<=V; k++) if (val[k]==0) visitar(k);}

void visitar(int k) // matriz de adyacencia{ int t; val[k]=++id; for (t=1; t<=V; t++) if (a[k][t] && val[t]==0) visitar(t);}

void visitar(int k) // listas de adyacencia{ struct nodo *t; val[k]=++id; for (t=a[k]; t!=z; t=t->sig) if (val[t->v]==0) visitar(t->v);}

 

El resultado es que el array val contendrá en su i-ésima entrada el orden en el que el vértice i-ésimo fue explorado. Es decir, si tenemos un grafo con cuatro nodos y fueron explorados en el orden 3-1-2-4, el array val quedará como sigue:

val[1]=2; // el primer nodo fue visto en segundo lugar

val[2]=3; // el segundo nodo fue visto en tercer lugarval[3]=1; // etc.val[4]=4;

Una modificación que puede resultar especialmente útil es la creación de un array "inverso" al array val que contenga los datos anteriores "al revés". Esto es, un array en el que la entrada i-ésima contiene el vértice que se exploró en i-ésimo lugar. Basta modificar la línea

val[k]=++id;

sustituyéndola por

val[++id]=k;

Para el orden de exploración de ejemplo anterior los valores serían los siguientes:

val[1]=3;val[2]=1;val[3]=2;val[4]=4;

 

Búsqueda en amplitud o anchura

La diferencia fundamental respecto a la búsqueda en profundidad es el cambio de estructura de datos: una cola en lugar de una pila. En esta implementación, la función del array val y la variable id es la misma que en el método anterior.

struct tcola *cola;

void visitar(int k) // listas de adyacencia{ struct nodo *t; encolar(&cola,k); while (!vacia(cola)) { desencolar(&cola,&k); val[k]=++id; for (t=a[k]; t!=z; t=t->sig) { if (val[t->v]==0) { encolar(&cola,t->v); val[t->v]=-1; } } }}

Arboles

Árboles

* Definición de árbol* Formas de representación* Nomenclatura sobre árboles* Declaración de árbol binario* Recorridos sobre árboles binarios* Construcción de un árbol binario* Árbol binario de búsqueda* Problemas

Definición de árbol

Un árbol es una estructura de datos, que puede definirse de forma recursiva como:

- Una estructura vacía o- Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo (ver grafos): un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación.

Formas de representación

- Mediante un grafo:

  Figura 1

- Mediante un diagrama encolumnado:

a  b    d  c    e    f

En la computación se utiliza mucho una estructura de datos, que son los árboles binarios. Estos árboles tienen 0, 1 ó 2 descendientes como máximo. El árbol de la figura anterior es un ejemplo válido de árbol binario.

Nomenclatura sobre árboles

- Raíz: es aquel elemento que no tiene antecesor; ejemplo: a. - Rama: arista entre dos nodos. - Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.- Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d- Nodo interno: aquel que tiene al menos un descendiente.- Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.- Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.- Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y a y d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

Declaración de árbol binario

Se definirá el árbol con una clave de tipo entero (puede ser cualquier otra tipo de datos) y dos hijos: izquierdo (izq) y derecho (der). Para representar los enlaces con los hijos se utilizan punteros. El árbol vacío se representará con un puntero nulo.

Un árbol binario puede declararse de la siguiente manera:

typedef struct tarbol{ int clave; struct tarbol *izq,*der;} tarbol;

Otras declaraciones también añaden un enlace al nodo padre, pero no se estudiarán aquí.

Recorridos sobre árboles binarios

Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel. Puesto que los árboles no son secuenciales como las listas, hay que buscar estrategias alternativas para visitar todos los nodos.

- Recorridos en profundidad:

* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.Si se hace el recorrido en preorden del árbol de la figura 1 las visitas serían en el orden siguiente: a,b,d,c,e,f.

void preorden(tarbol *a){ if (a != NULL) { visitar(a); preorden(a->izq); preorden(a->der); }}

* Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodo actual, y después se visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en este orden: b,d,a,e,c,f.

void inorden(tarbol *a){ if (a != NULL) { inorden(a->izq); visitar(a); inorden(a->der); }}

* Recorrido en postorden: se visitan primero el subárbol izquierdo, después el subárbol derecho, y por último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría

así: d,b,e,f,c,a.

void postorden(arbol *a){ if (a != NULL) { postorden(a->izq); postorden(a->der); visitar(a); }}

La ventaja del recorrido en postorden es que permite borrar el árbol de forma consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrará el árbol o subárbol que se pasa como parámetro. La razón para hacer esto es que no se debe borrar un nodo y después sus subárboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar, pero es innecesario aplicando este recorrido.

- Recorrido en amplitud:

Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más. Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en este orden: a,b,c,d,e,fEn este caso el recorrido no se realizará de forma recursiva sino iterativa, utilizando una cola (ver Colas) como estructura de datos auxiliar. El procedimiento consiste en encolar (si no están vacíos) los subárboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta que la cola esté vacía. En la codificación que viene a continuación no se implementan las operaciones sobre colas.

void amplitud(tarbol *a){ tCola cola; /* las claves de la cola serán de tipo árbol binario */ arbol *aux;

if (a != NULL) { CrearCola(cola); encolar(cola, a); while (!colavacia(cola)) { desencolar(cola, aux); visitar(aux); if (aux->izq != NULL) encolar(cola, aux->izq); if (aux->der != NULL) encolar(cola, aux->der); } }}

Por último, considérese la sustitución de la cola por una pila en el recorrido en amplitud. ¿Qué tipo de recorrido se obtiene?

Construcción de un árbol binario

Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin embargo no se ha estudiado ningún método para crearlos. A continuación se estudia un método para crear un árbol binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en sendos arrays.

Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el árbol viendo sus recorridos pero sin haber visto el árbol terminado.

Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede determinarse que la raíz es el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raíz forman el subárbol izquierdo. Asimismo los elementos entre der y la raíz forman el subárbol derecho. Por tanto se tiene este árbol:

A continuación comienza un proceso recursivo. Se procede a crear el subárbol izquierdo, cuyo tamaño está limitado por los índices izq y der. La siguiente posición en el recorrido en preorden es la raíz de este subárbol. Queda esto:

El subárbol b tiene un subárbol derecho, que no tiene ningún descendiente, tal y como indican los índices izq y der. Se ha obtenido el subárbol izquierdo completo de la raíz a, puesto que b no tiene subárbol izquierdo:

Después seguirá construyéndose el subárbol derecho a partir de la raíz a.

La implementación de la construcción de un árbol partiendo de los recorridos en preorden y en inorden puede consultarse aquí (en C).

Árbol binario de búsqueda

Un árbol binario de búsqueda es aquel que es:

- Una estructura vacía o- Un elemento o clave de información (nodo) más un número finito -a lo sumo dos- de estructuras tipo árbol, disjuntos, llamados subárboles y además cumplen lo siguiente:

  * Todas las claves del subárbol izquierdo al nodo son menores que la clave del nodo.  * Todas las claves del subárbol derecho al nodo son mayores que la clave del nodo.  * Ambos subárboles son árboles binarios de búsqueda.

Un ejemplo de árbol binario de búsqueda:

Figura 5

Al definir el tipo de datos que representa la clave de un nodo dentro de un árbol binario de búsqueda es necesario que en dicho tipo se pueda establecer una relación de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual a lo que apunte). Si se codifica el árbol en Pascal no se puede establecer una relación de orden para las claves, puesto que Pascal no admite determinar si un puntero es mayor o menor que otro.

En el ejemplo de la figura 5 las claves son números enteros. Dada la raíz 4, las claves del subárbol izquierdo son menores que 4, y las claves del subárbol derecho son mayores que 4. Esto se cumple también para todos los subárboles. Si se hace el recorrido de este árbol en orden central se obtiene una lista de los números ordenada de menor a mayor. Cuestión: ¿Qué hay que hacer para obtener una lista de los números ordenada de mayor a menor?

Una ventaja fundamental de los árboles de búsqueda es que son en general mucho más rápidos para localizar un elemento que una lista enlazada. Por tanto, son más rápidos para insertar y borrar elementos. Si el árbol está perfectamente equilibrado -esto es, la diferencia entre el número de nodos del subárbol izquierdo y el número de nodos del subárbol derecho es a lo sumo 1, para todos los nodos- entonces el número de comparaciones necesarias para localizar una clave es aproximadamente de logN en el peor caso. Además, el algoritmo de inserción en un árbol binario de búsqueda tiene la ventaja -sobre los arrays ordenados, donde se emplearía búsqueda dicotómica para localizar un elemento- de que no necesita hacer una reubicación de los elementos de la estructura para que esta siga ordenada después de la inserción. Dicho algoritmo

funciona avanzando por el árbol escogiendo la rama izquierda o derecha en función de la clave que se inserta y la clave del nodo actual, hasta encontrar su ubicación; por ejemplo, insertar la clave 7 en el árbol de la figura 5 requiere avanzar por el árbol hasta llegar a la clave 8, e introducir la nueva clave en el subárbol izquierdo a 8.El algoritmo de borrado en árboles es algo más complejo, pero más eficiente que el de borrado en un array ordenado.

Ahora bien, suponer que se tiene un árbol vacío, que admite claves de tipo entero. Suponer que se van a ir introduciendo las claves de forma ascendente. Ejemplo: 1,2,3,4,5,6Se crea un árbol cuya raíz tiene la clave 1. Se inserta la clave 2 en el subárbol derecho de 1. A continuación se inserta la clave 3 en el subárbol derecho de 2. Continuando las inserciones se ve que el árbol degenera en una lista secuencial, reduciendo drásticamente su eficacia para localizar un elemento. De todas formas es poco probable que se de un caso de este tipo en la práctica. Si las claves a introducir llegan de forma más o menos aleatoria entonces la implementación de operaciones sobre un árbol binario de búsqueda que vienen a continuación son en general suficientes.

Existen variaciones sobre estos árboles, como los AVL o Red-Black (no se tratan aquí), que sin llegar a cumplir al 100% el criterio de árbol perfectamente equilibrado, evitan problemas como el de obtener una lista degenerada.

Operaciones básicas sobre árboles binarios de búsqueda

- Búsqueda

Si el árbol no es de búsqueda, es necesario emplear uno de los recorridos anteriores sobre el árbol para localizarlo. El resultado es idéntico al de una búsqueda secuencial. Aprovechando las propiedades del árbol de búsqueda se puede acelerar la localización. Simplemente hay que descender a lo largo del árbol a izquierda o derecha dependiendo del elemento que se busca.

boolean buscar(tarbol *a, int elem){ if (a == NULL) return FALSE; else if (a->clave < elem) return buscar(a->der, elem); else if (a->clave > elem) return buscar(a->izq, elem); else return TRUE;}

- Inserción

La inserción tampoco es complicada. Es más, resulta practicamente idéntica a la búsqueda. Cuando se llega a un árbol vacío se crea el nodo en el puntero que se pasa como parámetro por referencia, de esta manera los nuevos enlaces mantienen la

coherencia. Si el elemento a insertar ya existe entonces no se hace nada.

void insertar(tarbol **a, int elem){ if (*a == NULL) { *a = (arbol *) malloc(sizeof(arbol)); (*a)->clave = elem; (*a)->izq = (*a)->der = NULL; } else if ((*a)->clave < elem) insertar(&(*a)->der, elem); else if ((*a)->clave > elem) insertar(&(*a)->izq, elem);}

- Borrado

La operación de borrado si resulta ser algo más complicada. Se recuerda que el árbol debe seguir siendo de búsqueda tras el borrado. Pueden darse tres casos, una vez encontrado el nodo a borrar:1) El nodo no tiene descendientes. Simplemente se borra.2) El nodo tiene al menos un descendiente por una sola rama. Se borra dicho nodo, y su primer descendiente se asigna como hijo del padre del nodo borrado. Ejemplo: en el árbol de la figura 5 se borra el nodo cuya clave es -1. El árbol resultante es:

3) El nodo tiene al menos un descendiente por cada rama. Al borrar dicho nodo es necesario mantener la coherencia de los enlaces, además de seguir manteniendo la estructura como un árbol binario de búsqueda. La solución consiste en sustituir la información del nodo que se borra por el de una de las hojas, y borrar a continuación dicha hoja. ¿Puede ser cualquier hoja? No, debe ser la que contenga una de estas dos claves:· la mayor de las claves menores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del árbol de la figura 5. Se sustituirá la clave 4 por la clave 2.· la menor de las claves mayores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del árbol de la figura 5. Se sustituirá la clave 4 por la clave 5.

El algoritmo de borrado que se implementa a continuación realiza la sustitución por la mayor de las claves menores, (aunque se puede escoger la otra opción sin pérdida de

generalidad). Para lograr esto es necesario descender primero a la izquierda del nodo que se va a borrar, y después avanzar siempre a la derecha hasta encontrar un nodo hoja. A continuación se muestra gráficamente el proceso de borrar el nodo de clave 4:

Codificación: el procedimiento sustituir es el que desciende por el árbol cuando se da el caso del nodo con descencientes por ambas ramas.

void borrar(tarbol **a, int elem){ void sustituir(tarbol **a, tarbol **aux); tarbol *aux;

if (*a == NULL) /* no existe la clave */ return;

if ((*a)->clave < elem) borrar(&(*a)->der, elem); else if ((*a)->clave > elem) borrar(&(*a)->izq, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->izq == NULL) *a = (*a)->der; else if ((*a)->der == NULL) *a = (*a)->izq; else sustituir(&(*a)->izq, &aux); /* se sustituye por la mayor de las menores */

free(aux); }}

Ficheros relacionados

Implementación de algunas de las operaciones sobre árboles binarios.

Ejercicio resuelto

Escribir una función que devuelva el numero de nodos de un árbol binario. Una solución recursiva puede ser la siguiente:

funcion nodos(arbol : tipoArbol) : devuelve entero;inicio si arbol = vacio entonces devolver 0; en otro caso devolver (1 + nodos(subarbol_izq) + nodos(subarbol_der));fin

Adaptarlo para que detecte si un árbol es perfectamente equilibrado o no.

Problemas propuestos

Árboles binarios: OIE 98. (Enunciado)

Aplicación práctica de un árbol

Se tiene un fichero de texto ASCII. Para este propósito puede servir cualquier libro electrónico de la librería Gutenberg o Cervantes, que suelen tener varios cientos de miles de palabras. El objetivo es clasificar todas las palabras, es decir, determinar que palabras aparecen, y cuantas veces aparece cada una. Palabras como 'niño'-'niña', 'vengo'-'vienes' etc, se consideran diferentes por simplificar el problema.

Escribir un programa, que recibiendo como entrada un texto, realice la clasificación descrita anteriormente.Ejemplo: Texto: "a b'a c. hola, adios, hola"

La salida que produce es la siguiente:a 2adios 1b 1c 1hola 2

Nótese que el empleo de una lista enlazada ordenada no es una buena solución. Si se obtienen hasta 20.000 palabras diferentes, por decir un número, localizar una palabra cualquiera puede ser, y en general lo será, muy costoso en tiempo. Se puede hacer una implementación por pura curiosidad para evaluar el tiempo de ejecución, pero no merece la pena.

La solución pasa por emplear un árbol binario de búsqueda para insertar las claves. El valor de log(20.000) es aproximadamente de 14. Eso quiere decir que localizar una

palabra entre 20.000 llevaría en el peor caso unos 14 accesos. El contraste con el empleo de una lista es simplemente abismal. Por supuesto, como se ha comentado anteriormente el árbol no va a estar perfectamente equilibrado, pero nadie escribe novelas manteniendo el orden lexicográfico (como un diccionario) entre las palabras, asi que no se obtendrá nunca un árbol muy degenerado. Lo que está claro es que cualquier evolución del árbol siempre será mejor que el empleo de una lista.

Por último, una vez realizada la lectura de los datos, sólo queda hacer un recorrido en orden central del árbol y se obtendrá la solución pedida en cuestión de segundos.

Una posible definición de la estructura árbol es la siguiente:

typedef struct tarbol{ char clave[MAXPALABRA]; int contador; /* numero de apariciones. Iniciar a 0 */ struct tarbol *izq, *der;} tarbol;

HASHING

Búsqueda mediante transformación de claves (hashing)

Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash. La correspondencia más sencilla es la identidad, esto es, al número 0 se le asigna el índice 0, al elemento 1 el índice 1, y así sucesivamente. Pero si los números a almacenar son demasiado grandes esta función es inservible. Por ejemplo, se quiere guardar en un array la información de los 1000 usuarios de una empresa, y se elige el núemro de DNI como elemento identificativo. Es inviable hacer un array de 100.000.000 elementos, sobre todo porque se desaprovecha demasiado espacio. Por eso, se realiza una transformación al número de DNI para que nos de un número menor, por ejemplo coger las 3 últimas cifras para guardar a los empleados en un array de 1000 elementos. Para buscar a uno de ellos, bastaría con realizar la transformación a su DNI y ver si está o no en el array.

La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar. La función de hash depende de cada problema y de cada finalidad, y se pueden utilizar con números o cadenas, pero las más utilizadas son:

Restas sucesivas: esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Por ejemplo, si el número de expediente de un alumno universitario está formado por el año de entrada en la universidad, seguido de un número identificativo de

tres cifras, y suponiendo que entran un máximo de 400 alumnos al año, se le asignarían las claves:

1998-000 --> 0 = 1998000-19980001998-001 --> 1 = 1998001-19980001998-002 --> 2 = 1998002-1998000     ...1998-399 --> 399 = 1998399-19980001999-000 --> 400 = 1999000-1998000+400     ...yyyy-nnn --> N = yyyynnn-1998000+(400*(yyyy-1998))

Aritmética modular: el índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que cuando hay N+1 elementos, al menos un índice es señalado por dos elementos (teorema del palomar). A este fenómeno se le llama colisión, y es tratado más adelante. Si el número N es el 13, los números siguientes quedan transformados en:

13000000 --> 012345678 --> 713602499 --> 171140205 --> 673062138 --> 6

Mitad del cuadrado: consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión:

123*123=15129 --> 51136*136=18496 --> 84730*730=532900 --> 29301*301=90601 --> 06625*625=390625 --> 06

Truncamiento: consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 8 cifras se debe ordenar en un array de 1000 elementos, se pueden coger la primer, la tercer y la última cifras para formar un nuevo número:

13000000 --> 10012345678 --> 13813602499 --> 16971140205 --> 71573162135 --> 715

Plegamiento: consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos los número de 8 cifras en 3, 3 y 2 cifras y se suman, dará otro número de tres cifras (y si no, se cogen las tres últimas cifras):

13000000 --> 130=130+000+0012345678 --> 657=123+456+7871140205 --> 118 --> 1118=711+402+0513602499 --> 259=136+024+9925000009 --> 259=250+000+09

Tratamiento de colisiones: Pero ahora se nos presenta el problema de qué hacer con las colisiones, qué pasa cuando a dos elementos diferentes les corresponde el mismo índice. Pues bien, hay tres posibles soluciones:

Cuando el índice correspondiente a un elemento ya está ocupada, se le asigna el primer índice libre a partir de esa posición. Este método es poco eficaz, porque al nuevo elemento se le asigna un índice que podrá estar ocupado por un elemento posterior a él, y la búsqueda se ralentiza, ya que no se sabe la posición exacta del elemento.

También se pueden reservar unos cuantos lugares al final del array para alojar a las colisiones. Este método también tiene un problema: ¿Cuánto espacio se debe reservar? Además, sigue la lentitud de búsqueda si el elemento a buscar es una colisión.

Lo más efectivo es, en vez de crear un array de número, crear un array de punteros, donde cada puntero señala el principio de una lista enlazada. Así, cada elemento que llega a un determinado índice se pone en el último lugar de la lista de ese índice. El tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones al tamaño del array, ya que se pueden añadir nodos dinámicamente a la lista (ver listas).