Autor Tema: Backtacking, Problema En El Algoritmo (Leído 2414 veces)

clausula · « **en:** Sábado 31 de Julio de 2004, 12:21 »

Hola a todos!

Simplemente, tengo un vector con 5 elementos, i me suma los que en contienen valor 1 en otro vector, es decir:

a[5] = {1,2,3,4,5}
b[5] = {1,0,0,1,0}

Me sumara 1 mas 4.

El problema es que tengo que hacer en backtraking, io poner X numeros, y saber si pueden sumar Y.

Lo he probado horas y horas, sin resultado, el codigo del backtracking aqui viene (el que e intentado yo)

while(!trobat && pos < 5) {
solucio[pos] = 1;
sumar(numeros,solucio,suma_total,trobat);
if(trobat) { cout << "S'ha trobat la suma" << endl; }
buscar(numeros,solucio,suma_total,trobat,pos+1);
if(!trobat) {
solucio[pos] = 0;
}
pos++;
}
}

Gracias a todos

Binary

A ver...
antes que nada... el metodo que quieres ocupar es muy lento...
un backtracking (o recursion por niveles mejor), porque el backtracking es diferente, te costara mucho tiempo para N > 30. (numeros)

Lo que te recomiendo es que checkees el metodo de la mochila, que hace todas las sumas de numeros en tan solo unas 5-6 lineas de codigo. Eso es de la parte dinammic programming (hacer soluciones a partir de soluciones mas chicas ya calculadas).

Asi, ese codigo ententara con el primer numero, segundo, tercero, hasta que encuentre una suma == X.
Incluso te puede encontrar la suma con la menor cantidad de numeros posibles (como optimazicacion), sin agregarle ni una linea de codigo.

Ahora no tengo tiempo para escribirlo...
Si alguien otro puede hacerlo por aqui, excelente, si no... esperame unas 6 horas, luego te lo codifico y explico.

Saludos.

Binary

ah, y dime si de verdad necesitas el backtracking, o prefieres el metodo de la mochila, porque no se para que lo necesitas...

Lo que si, es que el backtrack es lentisimo. Yo nunca lo ocuparia para hacer sumas. Eso sirve solo para puzles, caballos y reinas

(todos se saben esos clasicos de la demostracion del backtrack)

clausula

Ante todo ,muchas gracias por responder.

Tiene que ser con backtracking..., es uno de los temas de la asignatura de mtp (metodologia y tecnica de la programacion), el profe nos a dicho que podemos ir probando con las sumas.

Si puedes decir-me en que estoy actuando mal en el algoritmo, ia sabes

Gracias otra vez.

Binary

Entretenido tu codigo, pero no lo entiendo...
No dice donde tienes los numeros, donde anotas el 0/1 ni nada.

Mira... la idea del algoritmo es dejar un numero dentro o fuera del conjunto que dara la suma deseada. Asi... tenemos 2^N posibilidades (para cada numero: 0/1 (usarlo, no usarlo))

Eso se llama trabajo en niveles....
EN el caso, tenemos N niveles, y en cada uno debemos decidir si el nivel sera 1 o 0.

En el fondo, estamos generando un vector de 0 i 1... ej: 010101010.
Como se hace esto: para cada nivel de la recursion (backtracking), probamos con 0 i luego con 1, y probamos asi para este nivel.

El codigo debe ser asi:

nivel: nivel que estamos determinando (si usar el numero num[nivel] o no)
sum: la suma que nos queda por generar a tal nivel de la recursion

int rec(int nivel, int sum)
{
if(nivel > N) { // Si nivel esta fuera del rango de los numeros que tenemos
if(sum == 0) { print(); return 1; } // Si hemos logrado producir la suma
else return 0; // si no, nos devolvemos sin exito
}
else {
b[nivel] = 0;
if(rec(nivel+1, sum)) // probamos con el proximo numero sin usar el num[nivel]
return 1;

if(num[nivel] <= sum) { // si el numero que ponemos no excede la suma que buscamos
b[nivel] = 1;
if(rec(nivel+1, sum-num[nivel]))
return 1;
}
return 0;
}
}

la funcion print sera asi:

void print()
{
for(int i = 1; i <= n; i++)
if(b == 1) // si usamos el numero con indice i
cout<<num;
}

int find() devuelve 1 si encontro una suma, 0 si no.

Binary

se me olvidaba....
Debes tener ingresados los numeros en: int num[] (1 based) o sea... tu primer numero debe ser el 1, y el ultimo el N.

Debes llamar a la funcion find asi: find(1, suma), donde suma es la suma que quieres producir de los numeros en num[].

Saludos.

P.D. escribi el codigo en el foro directo... no me he dado el trabajo de depurarlo, pero lo mas importante es que lo entiendas... pregunta si tienes algo inclaro por alli....

Binary

hahaha.... rec() = find()

my mistake... srry

clausula

Hola Binary!

Antes de conectarme me vuelto a poner un rato, s'havia que andaba en el buen camino y asi a sido:

Los numeros, los introduce el usuario, con una funcion, pone 5 valores, los cuales se guardan en un vector llamado numeros.

Entonces tengo otro vector que se llama solucio, donde guardo los 0/1, inicializados a 0 previamente.

El codigo es el mismo que el de mi primer mensaje practicamente, lo que el error estaba fuera del codigo javascript:emoticon(':P') perdonen.

while(!trobat && pos < 5) {
      solucio[pos] = 1; //pruebo el numero a 1
      sumar(numeros,solucio,suma_total,trobat);
      buscar(numeros,solucio,suma_total,trobat,pos+1);
      if(!trobat) {
         solucio[pos] = 0; //sino sa la solucion, el numero que he probado lo pongo a 0
      }
      pos++;
      }

Luego me miro tu forma mas detalladamente.

PD: si alguien quiere el codigo corxat@wanadoo.es

Muchas gracias Binary!

SoloCodigo

Autor Tema: Backtacking, Problema En El Algoritmo (Leído 2414 veces)

clausula

Backtacking, Problema En El Algoritmo

Binary

Re: Backtacking, Problema En El Algoritmo

Binary

Re: Backtacking, Problema En El Algoritmo

clausula

Re: Backtacking, Problema En El Algoritmo

Binary

Re: Backtacking, Problema En El Algoritmo

Binary

Re: Backtacking, Problema En El Algoritmo

Binary

Re: Backtacking, Problema En El Algoritmo

clausula

Re: Backtacking, Problema En El Algoritmo