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

 

 


Tema destacado: (TUTORIAL) Aprende a emular Sentinel Dongle By Yapis


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  .NET (C#, VB.NET, ASP) (Moderador: kub0x)
| | | |-+  [Reto] Backtracking - Laberinto
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Reto] Backtracking - Laberinto  (Leído 13,635 veces)
hadree

Desconectado Desconectado

Mensajes: 6


Ver Perfil
[Reto] Backtracking - Laberinto
« en: 22 Noviembre 2010, 17:17 pm »

************************************

Hola a todos, soy nuevo en el foro y se ma ha ocurrido la idea de este hilo para explicar como realizar el algoritmo de "backtracking" para calcular el camino de ida desde la entrada de un laberinto, hasta la salida del mismo (en caso de haberla).

Os propongo realizar un pequeño programa que cumpla lo siguiente:

Código:

Dado un laberinto escriba un programa que usando
los cuatro movimientos del laberinto, arriba, abajo,
izquierda y derecha calcule (si existen):

1) La primera solución.
2) El total de las soluciones
3) La mejor solución en cuanto a menor número de pasos.

Los datos de entrada son recibidos en un fichero
de texto laberinto.txt que tiene la siguiente estructura:

a.) La primera línea tiene dos números enteros que
son el número de filas nf y el número de columnas nc  del laberinto.
b.) Las siguientes nf líneas tienen un total de nc números enteros cada
una de ellas separados por blancos que pueden ser: 0, 1, 2, 3 y 4

CERO: Indica muro (no se puede pisar la casilla);
UNO: Libre sin penalización. (+1 pasos)
DOS: Libre con penalización. (+2 pasos)
TRES: Libre con penalización. (+3 pasos)
CUATRO: Libre con penalización. (+4 pasos)

c.) La última línea del fichero tiene cuatro números enteros:

Fe = fila de entrada.
Ce = columna de entrada.
Fs = fila de salida.
Cs = columna de salida.


Código:

La estructura del laberinto en el archivo sería la siguiente:

---------------------------
nf nc
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
x x x x x x x x
fe fs ce cs
---------------------------
12 12
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 1 1 1 0
0 4 0 4 0 4 3 3 4 0 4 0
0 3 0 2 0 3 0 1 0 0 1 0
0 4 0 3 0 3 0 1 0 1 4 0
0 3 0 4 0 3 0 4 0 1 0 0
0 4 0 1 1 1 3 1 2 1 0 0
0 3 0 0 1 0 0 1 0 1 3 1
0 4 0 0 1 1 0 2 0 4 0 0
0 2 0 0 0 1 0 3 0 4 0 0
0 1 1 1 1 1 0 4 1 4 3 0
0 0 0 0 0 0 0 0 0 0 0 0
1 0 7 11
---------------------------


Os animáis a intentarlo :cool: ??

Código:
//El código lo pondré en unos días, a ver si la gente participa...:D


.


« Última modificación: 23 Noviembre 2010, 05:29 am por [D4N93R] » En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: [Reto] Backtracking - Laberinto
« Respuesta #1 en: 23 Noviembre 2010, 05:30 am »

Hola,

Excelente idea. Me tomé la molestia de modificar un poquito el títle del post :P Y bueno, a ver quién se anota!!


En línea

hadree

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Re: [Reto] Backtracking - Laberinto
« Respuesta #2 en: 23 Noviembre 2010, 22:27 pm »

Gracias, me parece bien así...."reto" suena más interesante....jajajaja
En línea

diego_lp

Desconectado Desconectado

Mensajes: 180


In a free world, who needs gates and windows?


Ver Perfil WWW
Re: [Reto] Backtracking - Laberinto
« Respuesta #3 en: 24 Noviembre 2010, 16:35 pm »

La idea esta muy buena!
Yo me anoto!
En cuanto tenga un rato libre lo voy a intentar  ;-)
Saludos.
En línea

Los programadores hicimos un pacto con Dios, él no hace sistemas y nosotros no hacemos milagros!
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: [Reto] Backtracking - Laberinto
« Respuesta #4 en: 24 Noviembre 2010, 18:57 pm »

El enunciado tiene muchas imprecisiones. Cuando dice la primera solución, entiendo que se refiere a la primera que encuentre el backtracking, pero no queda claro ni especifica qué criterio usar.

Lo segundo que pide es, bajo mi punto de vista, erróneo. Con el enunciado actual no se prohíben los ciclos, de forma que existen infinitos caminos para la gran mayoría de laberintos. Se tendría que especificar una longitud máxima o bien exigir que no haya ciclos.

Lo tercero es correcto, pero en lugar de un backtracking puede resolverse mediante Dijkstra, cuya complejidad para un grafo G = (V, E) es O((V + E)logV) mientras que el backtracking no es polinómico.

He picado Dijkstra  en C++ para el problema, he probado un par de ejemplos y los resuelve bien. El código es simple así que no debería ser problema pasarlo a otro lenguaje sabiendo un poco de C++.
Código
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. const int INF = 1000000000;
  7. const int arr1[] = {1, -1, 0, 0};
  8. const int arr2[] = {0, 0, 1, -1};
  9.  
  10. typedef pair<int, int> PII;
  11. typedef pair<int, PII> PIPII;
  12.  
  13. void dijkstra(int fini, int cini, int ffin, int cfin, vector<vector<int> >& M) {
  14.    int n = M.size(), m = M[0].size();
  15.    vector<vector<int> > d(n, vector<int>(m, INF));
  16.    d[fini][cini] = 0;
  17.    priority_queue<PIPII> Q;
  18.    Q.push(PIPII(0, PII(fini, cini)));
  19.    while (not Q.empty()) {
  20.        int f = Q.top().second.first, c = Q.top().second.second, dist = -Q.top().first;
  21.        Q.pop();
  22.        if (dist != d[f][c]) continue;
  23.        for (int i = 0; i < 4; ++i) {
  24.            int nf = f + arr1[i], nc = c + arr2[i];
  25.            if (nc < 0 or nc >= m or nf < 0 or nf >= n or M[nf][nc] == 0) continue;
  26.            if (d[nf][nc] > d[f][c] + M[nf][nc]) {
  27.                d[nf][nc] = d[f][c] + M[nf][nc];
  28.                Q.push(PIPII(-d[nf][nc], PII(nf, nc)));
  29.            }
  30.        }
  31.    }
  32.    if (d[ffin][cfin] == INF) cout << "No existe camino" << endl;
  33.    else cout << "Minima distancia: " << d[ffin][cfin] << endl;
  34. }
  35.  
  36. int main() {
  37.    int n, m;
  38.    cin >> n >> m;
  39.    vector<vector<int> > M(n, vector<int> (m));
  40.    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> M[i][j];
  41.    int fini, ffin, cini, cfin;
  42.    cin >> fini >> ffin >> cini >> cfin;
  43.    if (M[fini][cini] == 0) cout << "Muro en posicion inicial" << endl;
  44.    else dijkstra(fini, cini, ffin, cfin, M);
  45. }
En línea

.::IT::.

Desconectado Desconectado

Mensajes: 167



Ver Perfil
Re: [Reto] Backtracking - Laberinto
« Respuesta #5 en: 24 Noviembre 2010, 21:44 pm »

No se porque paso por mi mente que podría ser una tarea jaja en fin esta interesante
En línea

Simplemente .::IT::.
hadree

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Re: [Reto] Backtracking - Laberinto
« Respuesta #6 en: 25 Noviembre 2010, 16:57 pm »



El enunciado tiene muchas imprecisiones. Cuando dice la primera solución, entiendo que se refiere a la primera que encuentre el backtracking, pero no queda claro ni especifica qué criterio usar.

Lo segundo que pide es, bajo mi punto de vista, erróneo. Con el enunciado actual no se prohíben los ciclos, de forma que existen infinitos caminos para la gran mayoría de laberintos. Se tendría que especificar una longitud máxima o bien exigir que no haya ciclos.

Lo tercero es correcto, pero en lugar de un backtracking puede resolverse mediante Dijkstra, cuya complejidad para un grafo G = (V, E) es O((V + E)logV) mientras que el backtracking no es polinómico.

He picado Dijkstra  en C++ para el problema, he probado un par de ejemplos y los resuelve bien. El código es simple así que no debería ser problema pasarlo a otro lenguaje sabiendo un poco de C++.


1) Por supuesto lo de la primera solución se refiere a la primera solución es decir la primera encontrada, no me parece que haya ninguna duda...

2) En cuanto a los ciclos, si la verdad es que no lo había puesto, pero se da por hecho ya que realizando los movimientos básicos comentados se quedaría atascado si intentase pasar de nuevo por una casilla ya recorrida.

3) Se puede resolver con Dijkstra, pero la idea original era que fuera por backtracking y con una representación matricial que no que fuera considerada como un grafo.

4) El código no lo he probado pero parece tener buena pinta... :rolleyes:

****************************************************************


No se porque paso por mi mente que podría ser una tarea jaja en fin esta interesante


PD: Yo ya lo tengo resuelto y pensaba ponerlo más adelante simplemente quería saber si había gente dispuesta a intentarlo... ::)

****************************************************************


.
« Última modificación: 25 Noviembre 2010, 17:06 pm por hadree » En línea

pisa2

Desconectado Desconectado

Mensajes: 1



Ver Perfil
Re: [Reto] Backtracking - Laberinto
« Respuesta #7 en: 17 Diciembre 2010, 13:35 pm »

hola
pues a mi me iría genial la solución de este "maldito" problema en java!! ;D

si la pones, me habrás hecho el regalo de navidad perfecto ;-)
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Recursividad y Backtracking!!!!
Java
bwsr 2 8,100 Último mensaje 28 Junio 2007, 00:40 am
por bwsr
Backtracking - Laberinto
Programación C/C++
hadree 3 6,657 Último mensaje 23 Noviembre 2010, 03:08 am
por do-while
Suma de Conjuntos con Vuelta Atrás (Backtracking) en C
Programación General
maritere22 6 7,988 Último mensaje 31 Mayo 2013, 05:39 am
por Kenkox
BACKTRACKING CIRCUITO HAMILTONIANO
Programación C/C++
yeah_2796 1 2,630 Último mensaje 23 Mayo 2015, 11:19 am
por Stakewinner00
problema de backtracking y programacion dinamica
Programación C/C++
aprendiz de programador 6 5,369 Último mensaje 12 Diciembre 2015, 16:08 pm
por SnzCeb
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines