Autor
|
Tema: problema de backtracking y programacion dinamica (Leído 6,573 veces)
|
aprendiz de programador
Desconectado
Mensajes: 4
|
Queria eliminar el mensaje pero no me dejais
|
|
« Última modificación: 13 Diciembre 2015, 13:42 pm por IvanCarras »
|
En línea
|
|
|
|
SnzCeb
Desconectado
Mensajes: 10
|
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 . 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
Mensajes: 4
|
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
Mensajes: 10
|
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
Mensajes: 10
|
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
Mensajes: 4
|
¿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
Mensajes: 10
|
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
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Programación Dinámica
Java
|
erikcdlm
|
0
|
1,881
|
7 Noviembre 2014, 20:32 pm
por erikcdlm
|
|
|
Problema Programación Dinamica
Programación C/C++
|
maxisolis
|
3
|
2,516
|
29 Junio 2015, 02:19 am
por maxisolis
|
|
|
Problema de Backtracking (recursion)
Programación C/C++
|
KINGARZA
|
0
|
2,424
|
6 Julio 2017, 08:17 am
por KINGARZA
|
|
|
Problema en ejercicio de backtracking
Programación General
|
xXJoSe13Xx
|
0
|
2,353
|
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,508
|
4 Octubre 2021, 23:07 pm
por fzp
|
|