Temas variados
Páginas: 2 (256 palabras)
Publicado: 26 de mayo de 2010
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 relacionadoscon 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 lasventajas e inconvenientes de aplicarlas en diferentes tipos de problemas.
Desarrollo:
Imaginemos que queremos resolver un problema que debe encontrar una parte de unagregado 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 lascondiciones 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 enterospositivos 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;
staticboolean[] 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
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 relacionadoscon 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 lasventajas e inconvenientes de aplicarlas en diferentes tipos de problemas.
Desarrollo:
Imaginemos que queremos resolver un problema que debe encontrar una parte de unagregado 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 lascondiciones 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 enterospositivos 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;
staticboolean[] 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
Leer documento completo
Regístrate para leer el documento completo.