Una pincelada a dos algoritmos: Divide y Vencerás & Backtracking

21:30

Hoy me ha dado por publicar un post sobre algoritmia, una materia que no me gusta para nada tener que estudiarla para aprobarla, pero que sino tuviera la presión de los exámenes incluso podría resultar atractiva.

Los algoritmos que aparecen hoy aquí resuelven problemas de alta carga computacional en unas pocas líneas de código. Siguen una estructura recursiva (aunque también podemos encontrar versiones iterativas) y bien definida, lo que se supone que nos hace más sencillo su estudio e implementación.


· El primer algoritmo que os presento es el Divide y Vencerás:

- Su objetivo es bien simple y el propio nombre declara sus intenciones perversas, que consiste en descomponer un problema en subproblemas, hallar las subsoluciones y al finalizar combinarlas en una única solución.

- A continuación os pongo el esquema general que sigue el algoritmo:

Public TipoSolución dyv(TipoProblema problema){
 TipoSolución solución;
 TipoProblema[] subproblema;
 TipoSolución subsolución;

 //CASO BASE
 if(EsCasoBase(problema)){
   solución=ResuelveCasoBase(problema);
}else{
   //TAREAS DE DIVISIÓN
   int k=dividir(problema,subproblemas);

   //RESOLUCIÓN DE SUBPROBLEMAS
   for(int i=0; i<k; i++){
     subsoluciones[i]= dyv(subproblemas[i]);
   }

   //COMBINACIÓN
   solución=combinar(subsoluciones);

 }

 return solucion;

}

· Por otra parte tenemos al amigo Backtracking:

- Se encargar de buscar la solución a un problema, puede ser una única solución, todas las soluciones o la mejor solución que este tenga, a base de ensayo y error, es decir, prueba un camino y si ese camino no es válido, lo apunta (en matrices/vectores deja el valor como estaba por defecto) y vuelve al paso anterior.

- Su característica principal es que hace una búsqueda por profundidad a un árbol recursivo de búsqueda, cosa que también lo hace complejo de entender en algún punto.

- El algoritmo para hallar todas las soluciones es el siguiente:

Public static void buscarTodas(int n_1, int i, valor[] solucion){

 for(int k=0; k<m; k++){
   <<generar candidato k-ésimo >>
   if(<<candidato válido>>){
       <<incluirlo en solución>>;
       if(i==n_1){
           imprimirSolución(solución);
       }else{
           buscarTodas(n,n+1,solución);
       }
       <<borrado de solución>>;
   }
 }

}

- También tenemos el algoritmo para una única solución:


Public static void buscarUna(int n_1, int i, valor[] solucion){

 for(int k=0; k<m && !exito; k++){
   <<generar candidato k-ésimo >>
   if(<<candidato válido>>){
       <<incluirlo en solución>>;
       if(i==n_1){
           exito=true;
       else{
           exito=buscarUna(n,i+1,solucion);
           if(!exito){
              <<borrado de solución>>;
           }
      }
 }
 return éxito;
}

Eso es todo por este domingo de junio.

PD: No se me olvida que os debo la última parte de Ingeniería de Requisitos.

Fuente: Apuntes de D.A.A. URJC 2012 y http://www.fdi.ucm.es/profesor/jcorreas/mtpIS09/

You Might Also Like

0 comentarios

Sé respetuoso/a, en este blog caben todo tipo de opiniones con respeto y serenidad.

statistics :: ヽ(*・ω・)ノ

Contact Form :: (」゜ロ゜)」