problema de backtracking y programacion dinamica

[aprendiz de programador]

Queria eliminar el mensaje pero no me dejais

[SnzCeb]

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?

[aprendiz de programador]

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 

[SnzCeb]

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)

[SnzCeb]

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?

[aprendiz de programador]

¿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

[SnzCeb]

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 ... ?