Autor Tema: backtracking  (Leído 2871 veces)

Desconectado good

  • PHPerit@
  • *
  • Mensajes: 49
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
backtracking
« en: 26 de Agosto de 2011, 00:03:41 am »
la idea del backtracking es "llegar hasta el fondo" y si no es correcto, retroceder.
Un ejemplo de aplicación es la solución de un laberinto.

pero voy a poner algo más sencillo, un programa que genera todas las combinaciones de 0 y 1 de longitud n

#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<bool> VB;
 
void combinaciones (VB& v, int count) {
     if (count == int(v.size())) {
          // imprimir el vector
          for (int i = 0; i < int(v.size()); ++i) cout << v;
          cout << endl;
          return;
     }
     v[count] = true;
     combinaciones(v, count+1);
 
     v[count] = false;
     combinaciones(v, count+1);
}
 
int main () {
     int n;
     cin>>n;
     VB v(n);
 
     combinaciones(v, 0);
}

Comunidad PHPeros

backtracking
« en: 26 de Agosto de 2011, 00:03:41 am »

Desconectado Physlet

  • PHPero Experto
  • *****
  • Mensajes: 822
  • Karma: 41
  • Sexo: Masculino
  • Todo es posible con esfuerzo, dedicación e interés
    • Ver Perfil
    • PanamaDev
Re:backtracking
« Respuesta #1 en: 26 de Agosto de 2011, 01:14:32 am »
La mejor forma para que los usuarios comprendan esta técnica, es que conozcan los grafos.
En mi caso, como no tengo tiempo para hacer estudios independientes por trabajo y demás, voy a esperarme a unas semanas en lo que entramos a dar el tema de grafos en la asignatura de Estructura de Datos.

Desconectado good

  • PHPerit@
  • *
  • Mensajes: 49
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
Re:backtracking
« Respuesta #2 en: 26 de Agosto de 2011, 01:25:12 am »
La mejor forma para que los usuarios comprendan esta técnica, es que conozcan los grafos.
En mi caso, como no tengo tiempo para hacer estudios independientes por trabajo y demás, voy a esperarme a unas semanas en lo que entramos a dar el tema de grafos en la asignatura de Estructura de Datos.

si pongo un reto de búsqueda en grafos lo harás? xD
« Última modificación: 26 de Agosto de 2011, 01:27:06 am por good »

Desconectado Physlet

  • PHPero Experto
  • *****
  • Mensajes: 822
  • Karma: 41
  • Sexo: Masculino
  • Todo es posible con esfuerzo, dedicación e interés
    • Ver Perfil
    • PanamaDev
Re:backtracking
« Respuesta #3 en: 26 de Agosto de 2011, 02:34:45 am »
si pongo un reto de búsqueda en grafos lo harás? xD
Cuando comprenda grafos, sí. Esperaré a que toquen el tema en la u.

Desconectado good

  • PHPerit@
  • *
  • Mensajes: 49
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
Re:backtracking
« Respuesta #4 en: 26 de Agosto de 2011, 12:32:31 pm »
Cuando comprenda grafos, sí. Esperaré a que toquen el tema en la u.

lo peor es la programación dinámica, dinámicas everywhere, contar cosas everywhere. Los grafos son mas guapos xDD

Desconectado Physlet

  • PHPero Experto
  • *****
  • Mensajes: 822
  • Karma: 41
  • Sexo: Masculino
  • Todo es posible con esfuerzo, dedicación e interés
    • Ver Perfil
    • PanamaDev
Re:backtracking
« Respuesta #5 en: 26 de Agosto de 2011, 17:09:34 pm »
lo peor es la programación dinámica, dinámicas everywhere, contar cosas everywhere. Los grafos son mas guapos xDD
Cada estructura tiene un fin, la idea no es mezclar conceptos. Por eso no te puedo decir si son más guapos o más prácticos porque aún no toco el tema.

Ya pasé por las primitivas, arreglos, listas enlazadas, pilas, colas, registros y voy ahora mismo en árboles.

Desconectado madbeto

  • PHPerit@
  • *
  • Mensajes: 1
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
Re:backtracking
« Respuesta #6 en: 26 de Marzo de 2012, 04:33:22 am »
Buenas.. me aparece un error en tu codigo.. lo arregle poniendo esto en donde imprimes el vector

asi quedo:
for (int i = 0; i < int(v.size()); ++i) cout << v;

Muy buen codigo, muchas gracias