COMPARANDO 4 TÉCNICAS DE DISEÑOS 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
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
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
s[i]=s1[i];
}
for(int j=0;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
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
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
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
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.
