elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  problema de backtracking y programacion dinamica
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: problema de backtracking y programacion dinamica  (Leído 6,411 veces)
aprendiz de programador

Desconectado Desconectado

Mensajes: 4


Ver Perfil
problema de backtracking y programacion dinamica
« en: 12 Diciembre 2015, 09:59 am »

Queria eliminar el mensaje pero no me dejais


« Última modificación: 13 Diciembre 2015, 13:42 pm por IvanCarras » En línea

SnzCeb

Desconectado Desconectado

Mensajes: 10


Ver Perfil
Re: PROBLEMA DE BACKTRACKING Y PROGRAMACION DINAMICA
« Respuesta #1 en: 12 Diciembre 2015, 12:55 pm »

Hola Ivan, estás de suerte porque tengo muy reciente estos temas ya que yo los estoy estudiando también xD, aunque no tengo que usar C por suerte  :xD.

El backtracking es una técnica que se aplica al algoritmo de búsqueda en profundidad. El código se encuentra en wikipedia. Es un algoritmo de búsqueda en grafos, por lo que tenemos que modelizar el laberinto como un grafo, como estamos en C, deberemos definir un TAD Grafo mediante estructuras.

Antes de seguir, ¿Cómo llevas los grafos? ¿Los has estudiado?


En línea

aprendiz de programador

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Re: PROBLEMA DE BACKTRACKING Y PROGRAMACION DINAMICA
« Respuesta #2 en: 12 Diciembre 2015, 14:11 pm »

Pues los estoy dando tambien en estructuras de datos, es mi segundo año en ingenieria informatica en sistemas de información, yo también pensé que es así, pensé que en vez de grafos para volver hacia atrás usar arboles, pero me dijo que no era necesario usar ninguna estructura de datos, me dijo que usará una matriz booleana la cual nos indica los pasos que llevamos y otra de pasillos y beneficios y hasta ahí he hecho, pero mequedado un poco atascado.
Muchas gracias por las ideas y demás, un saludo  :-*
En línea

SnzCeb

Desconectado Desconectado

Mensajes: 10


Ver Perfil
Re: PROBLEMA DE BACKTRACKING Y PROGRAMACION DINAMICA
« Respuesta #3 en: 12 Diciembre 2015, 14:40 pm »

No te digo yo que sea mala opción, pero cuando no tienes soltura es más sencillo modelizarlo con estructuras, aparte de que te queda un código más sencillo de entender y ese TAD grafo lo puedes reutilizar para numerosos problemas, ya que créeme te hartarás a ver grafos en la carrera xD.  

Como primera idea se me ocurre algo así, definir el tipo arista y el tipo nodo


typedef int NODO;

typedef struct {
NODO u;
NODO v;
int peso;
}ARISTA;


typedef struct {
 ARISTA[] aristas;
 NODO [] vertices;
}GRAFO;

Ahora el siguiente paso, seria definir las primitivas que el algoritmo de BT va a necesitar. Te pongo es pseudocódigo y me respondes que se te ocurre

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

    root(P): return the partial candidate at the root of the search tree.
    reject(P,c): return true only if the partial candidate c is not worth completing.
    accept(P,c): return true if c is a solution of P, and false otherwise.
    first(P,c): generate the first extension of candidate c.
    next(P,s): generate the next alternative extension of a candidate, after the extension s.
    output(P,c): use the solution c of P, as appropriate to the application.

The backtracking algorithm reduces the problem to the call bt(root(P)), where bt is the following recursive procedure:

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ Λ do
    bt(s)
    s ← next(P,s)
« Última modificación: 12 Diciembre 2015, 15:09 pm por SnzCeb » En línea

SnzCeb

Desconectado Desconectado

Mensajes: 10


Ver Perfil
Re: PROBLEMA DE BACKTRACKING Y PROGRAMACION DINAMICA
« Respuesta #4 en: 12 Diciembre 2015, 15:12 pm »

Pues los estoy dando tambien en estructuras de datos, es mi segundo año en ingenieria informatica en sistemas de información, yo también pensé que es así, pensé que en vez de grafos para volver hacia atrás usar arboles, pero me dijo que no era necesario usar ninguna estructura de datos, me dijo que usará una matriz booleana la cual nos indica los pasos que llevamos y otra de pasillos y beneficios y hasta ahí he hecho, pero mequedado un poco atascado.
Muchas gracias por las ideas y demás, un saludo  :-*

Los arboles son grafos no ponderados y este es un grafo ponderado en funcion del beneficio, que no sé que métrica seguirá ¿Puedes ponernos un laberinto de ejemplo?
En línea

aprendiz de programador

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Re: problema de backtracking y programacion dinamica
« Respuesta #5 en: 12 Diciembre 2015, 15:42 pm »

¿Con metrica te refieres al objetivo de nuestro laberinto? Pues si es eso el objetivo es sin pasar dos veces por un mismo sitio obtener el maximo beneficio comenzando en el punto (0,0) de la matriz y saliendo por el (n,n), muchas gracias por las ideas ;), pero esque el profesor me dijo que mejor sin estructuras aun así si no se me ocurre otra idea lo intentaré con estructuras de datos(era mi idea desde el principio xD).
Si quieres ver un ejemplo compila este gcc nombre -lm, y asi ves como funciona los -1 son paredes y los numeros mayores o iguales a 0 pasillos
En línea

SnzCeb

Desconectado Desconectado

Mensajes: 10


Ver Perfil
Re: problema de backtracking y programacion dinamica
« Respuesta #6 en: 12 Diciembre 2015, 16:08 pm »

No, me refiero a que magnitudes usas para cuantificar el "beneficio", ¿qué significa tener más beneficio en un camino respecto de otro?, ¿Longitud, tiempo de recorrido ... ?
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Programación Dinámica
Java
erikcdlm 0 1,868 Último mensaje 7 Noviembre 2014, 20:32 pm
por erikcdlm
Problema Programación Dinamica
Programación C/C++
maxisolis 3 2,498 Último mensaje 29 Junio 2015, 02:19 am
por maxisolis
Problema de Backtracking (recursion)
Programación C/C++
KINGARZA 0 2,418 Último mensaje 6 Julio 2017, 08:17 am
por KINGARZA
Problema en ejercicio de backtracking
Programación General
xXJoSe13Xx 0 2,333 Último mensaje 3 Noviembre 2018, 18:15 pm
por xXJoSe13Xx
Ayuda con problema de backtracking (recursividad) de optimización en C
Programación C/C++
Albpenu 2 6,332 Último mensaje 4 Octubre 2021, 23:07 pm
por fzp
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines