Tecnicas Para Diseñar Un Algoritmo
Enviado por rey_jose • 25 de Abril de 2012 • 1.741 Palabras (7 Páginas) • 598 Visitas
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;
}
...