Ayuda optimizacion busqueda de salida en laberinto

Foro de elhacker.net

Programación

Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)

Ayuda optimizacion busqueda de salida en laberinto

0 Usuarios y 1 Visitante están viendo este tema.

Páginas: [1] 2

Autor

Tema: Ayuda optimizacion busqueda de salida en laberinto (Leído 6,746 veces)

erest0r

Desconectado

Mensajes: 147

Ayuda optimizacion busqueda de salida en laberinto

« en: 28 Marzo 2014, 02:40 am »

Hola, aqui les traigo un problema que estoy haciendo sobre, dado un laberinto de 12 x 12 usar la regla de la mano derecha para conseguir la salida del laberinto e indicar si hay salida o no, como tal el programa corre y si encuentra la salida, pero no se si lo esta haciendo de la mejor manera, he aqui el codigo:

Código

#include <stdio.h>
#include <stdlib.h>     // Para usar funcion de limpiar pantalla
#include <windows.h>    // Para usar funcion de hacer pausa
#define TAM_FIL 12
#define TAM_COL 12
 
using namespace std;
 
typedef struct
{
    int estaEnInicio, estaEnFinal; //----- Para saber cuantas veces nuestro objeto ha estado en el inicio y si esta en el final
    char simbolo;
    int pos_x; //------------------------- Coordenada del objeto en X
    int pos_y; //------------------------- Coordenada del objeto en Y
}Objeto;
 
typedef struct
{
    // ----------------------------------- Simplemente para saber las coordenadas de los puntos X e Y de inicio y fin del laberinto ------------------------------------
 
    int ini_fil;
    int ini_col;
    int fin_fil;
    int fin_col;
}InformacionMapa;
 
void mostrarEstadoMapa( char laberinto[][TAM_COL] );
void recorrerLaberinto( char laberinto[][TAM_COL], InformacionMapa *punto, Objeto *obj );
 
int main( int argc, char* args[] )
{
 
    int cont_fil, cont_col;
 
    InformacionMapa mapa;
    mapa.ini_fil = 2;
    mapa.ini_col = 0;
    mapa.fin_fil = 4;
    mapa.fin_col = 11;
 
    Objeto obj;
    obj.simbolo = 'X';
    obj.estaEnInicio = 0;
    obj.estaEnFinal = 0;
    obj.pos_x = 2;
    obj.pos_y = 0;
 
    char laberinto[TAM_FIL][TAM_COL] = { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#',
                                         '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#',
                                         ' ', ' ', '#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#',
                                         '#', '#', '#', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', '#',
                                         '#', ' ', ' ', ' ', ' ', '#', '#', '#', ' ', ' ', ' ', ' ',
                                         '#', '#', '#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#',
                                         '#', ' ', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#',
                                         '#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#',
                                         '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#',
                                         '#', '#', '#', '#', '#', '#', ' ', '#', '#', '#', ' ', '#',
                                         '#', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#',
                                         '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'
                                       };
 
    recorrerLaberinto( laberinto, &mapa, &obj );
 
    getchar();
	return 0;
}
 
void mostrarEstadoMapa( char laberinto[][TAM_COL] )
{
    int cont_fil, cont_col;
 
    system("cls");
    for( cont_fil = 0; cont_fil < TAM_FIL; cont_fil++ )
    {
        for( cont_col = 0; cont_col < TAM_COL; cont_col++ )
        {
            printf("%c", laberinto[cont_fil][cont_col]);
            printf("  ");
        }
 
        printf("\n\n");
    }
    Sleep(500);
}
 
void recorrerLaberinto( char laberinto[][TAM_COL], InformacionMapa *mapa, Objeto *obj )
{
 
    if( obj->pos_x == mapa->ini_fil && obj->pos_y == mapa->ini_col )
        obj->estaEnInicio++;
    else if( obj->pos_x == mapa->fin_fil && obj->pos_y == mapa->fin_col )
        obj->estaEnFinal++;
 
    while( laberinto[4][11] != obj->simbolo && obj->estaEnInicio == 1 && !obj->estaEnFinal )
    {
        laberinto[obj->pos_x][obj->pos_y] = obj->simbolo;
 
        mostrarEstadoMapa( laberinto );
 
        if( laberinto[obj->pos_x][obj->pos_y + 1] != '#' && laberinto[obj->pos_x][obj->pos_y + 1] != obj->simbolo )
        {
            obj->pos_y++;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x + 1][obj->pos_y] != '#' && laberinto[obj->pos_x + 1][obj->pos_y] != obj->simbolo )
        {
            obj->pos_x++;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x - 1][obj->pos_y] != '#' && laberinto[obj->pos_x - 1][obj->pos_y] != obj->simbolo )
        {
            obj->pos_x--;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x][obj->pos_y - 1] != '#' && laberinto[obj->pos_x][obj->pos_y - 1] != obj->simbolo )
        {
            obj->pos_y--;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x][obj->pos_y - 1] != '#' )
        {
            obj->pos_y--;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x - 1][obj->pos_y] != '#' )
        {
            obj->pos_x--;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x + 1][obj->pos_y] != '#' )
        {
            obj->pos_x++;
            recorrerLaberinto( laberinto, mapa, obj );
        }
        else if( laberinto[obj->pos_x][obj->pos_y + 1] != '#' )
        {
            obj->pos_y++;
            recorrerLaberinto( laberinto, mapa, obj );
        }
 
    }
 
    if( obj->estaEnInicio > 1 )
        printf("\n\n\nNo hay salida en este laberinto.");
    if( obj->estaEnFinal )
        printf("\n\n\nFinal del laberinto encontrado");
}

Disculpen el exceso de if-else xD, debo mejorar esa parte.

Nota: Aun no lo he probado con un laberinto distinto con punto de partida y fin distintos.

He probado quitandole la salida y alli si que no hace la busqueda por todas las posibles rutas del laberinto, aunque se que esto seria un problema de backtracking, yo no soy muy experto cuando se trata de recursividad jeje


« Última modificación: 28 Marzo 2014, 03:00 am por Eternal Idol »	En línea

Cruzar la calle junto a mucha gente cuando el semáforo sigue en rojo da seguridad y espíritu de equipo... o cruzamos todos o morimos juntos.

eferion

Desconectado

Mensajes: 1.248

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #1 en: 28 Marzo 2014, 09:05 am »

Código

using namespace std;
 
typedef struct
{
    int estaEnInicio, estaEnFinal; //----- Para saber cuantas veces nuestro objeto ha estado en el inicio y si esta en el final
    char simbolo;
    int pos_x; //------------------------- Coordenada del objeto en X
    int pos_y; //------------------------- Coordenada del objeto en Y
}Objeto;

C++ y C en el mismo código ??? Entiendo que al final te has decantado por C porque no hay includes de C++, en tal caso deberías quitar el using namespace.

Si quieres usar C++ has de saber que el typedef no es necesario en este caso, las estructuras en C++ se usan igual que las clases ( es decir, sin poner el struct ) y sin necesidad de typedefs.

Otra cosa, la función recorrerLaberinto es un poco infernal, no?? usas recurrencia y un while a la vez... hay que tener bastante cuidado con esas cosas porque se puede pasar de vueltas la función. Sinceramente no creo que sea necesario para este caso que la función sea recursiva. Con un while ( !salida_encontrada ) { codigo } puedes resolver el ejercicio.

El problema de la recurrencia es que para determinados laberintos te puedes encontrar con que el número de pasos necesarios para salir desde una posición determinada sea superior al tamaño de la pila... en cuyo caso vas a tener un casque.

Otra cosilla. En el siguiente código:

Código

if( laberinto[obj->pos_x][obj->pos_y + 1] != '#' && laberinto[obj->pos_x][obj->pos_y + 1] != obj->simbolo )

Se supone que "simbolo" es el caracter que representa tu posición actual, no? en ese caso... ¿Cómo es posible que puedas estar en obj->pos_y y en obj->pos_y+1 a la vez?

Y para terminar:

Código

    if( obj->estaEnInicio > 1 )
        printf("\n\n\nNo hay salida en este laberinto.");

No creo que esta sea el chequeo correcto. Habría que tener en cuenta también la dirección en la que te estás moviendo... tu ponte que inicias el algoritmo en un cruce de caminos y se dirige primero hacia un pasillo cerrado... al volver a pasar por el cruce dirás, erroneamente, que no tiene salida.


	En línea

erest0r

Desconectado

Mensajes: 147

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #2 en: 28 Marzo 2014, 14:36 pm »

El using namespace std; si fue un descuido se me habia olvidado borrar esa linea, solo que cuando intente modificar el post cuando le daba previsualizar me mostraba algunos caracteres raros y lo deje asi y bueno estaba intentando resolverlo con recursividad, la linea

Código

if( laberinto[obj->pos_x][obj->pos_y + 1] != '#' && laberinto[obj->pos_x][obj->pos_y + 1] != obj->simbolo )

Simplemente la use para saber si cuando el objeto se mueva a la posicion siguiente no haya obstaculo '#' o no esté ya su simbolo (indicando que ya paso por alli), pero como dije, los problemas de recursividad me cuestan pensarlos.


	En línea

Cruzar la calle junto a mucha gente cuando el semáforo sigue en rojo da seguridad y espíritu de equipo... o cruzamos todos o morimos juntos.

eferion

Desconectado

Mensajes: 1.248

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #3 en: 28 Marzo 2014, 18:20 pm »

Cita de: erest0r en 28 Marzo 2014, 14:36 pm

Pero te das cuenta de que así impides que tu algoritmo pueda dar la vuelta tras meterse por el pasillo equivocado, no?

Código:

0123456789
##########
      XXX#
##########

Si tu algoritmo empieza en la posición 6 y tira hacia la derecha... llega a 8 y jaque mate, no tiene salida... a no ser que pueda dar la vuelta.


	En línea

erest0r

Desconectado

Mensajes: 147

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #4 en: 28 Marzo 2014, 20:01 pm »

Viendo ejemplos de códigos recursivos logre modificar mi programa ( hice que la función retornara valores, y modifique los if ), ahora el programa si busca caminos alternativos, pero aun asi existen caminos que no recorre, en el caso de mi laberinto, si a la posicion que deberia ser la salida lo hago un obstaculo, al programa le quedarían 2 caminos por verificar

Coloco todo el codigo de nuevo porque hice algun cambio en main

Código

#include <stdio.h>
#include <stdlib.h>     // Para usar funcion de limpiar pantalla
#include <windows.h>    // Para usar funcion de hacer pausa
#define TAM_FIL 12
#define TAM_COL 12
 
typedef struct
{
    int estaEnFinal; //------------------- Para saber si llego al final el objeto
    char simbolo;
    int pos_x; //------------------------- Coordenada del objeto en X
    int pos_y; //------------------------- Coordenada del objeto en Y
}Objeto;
 
typedef struct
{
    // ----------------------------------- Simplemente para saber las coordenadas de los puntos X e Y de inicio y fin del laberinto ------------------------------------
 
    int ini_fil;
    int ini_col;
    int fin_fil;
    int fin_col;
}InformacionMapa;
 
void mostrarEstadoMapa( char laberinto[][TAM_COL] );
int recorrerLaberinto( char laberinto[][TAM_COL], InformacionMapa *punto, Objeto obj );
 
int main( int argc, char* args[] )
{
 
 
    InformacionMapa mapa;
    mapa.ini_fil = 2;
    mapa.ini_col = 0;
    mapa.fin_fil = 4;
    mapa.fin_col = 11;
 
    Objeto obj;
    obj.simbolo = 'X';
    obj.estaEnFinal = 0;
    obj.pos_x = 2;
    obj.pos_y = 0;
 
    char laberinto[TAM_FIL][TAM_COL] = { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#',
                                         '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#',
                                         ' ', ' ', '#', ' ', '#', ' ', '#', '#', '#', '#', ' ', '#',
                                         '#', '#', '#', ' ', '#', ' ', ' ', ' ', ' ', '#', ' ', '#',
                                         '#', ' ', ' ', ' ', ' ', '#', '#', '#', ' ', ' ', ' ', ' ',
                                         '#', '#', '#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#',
                                         '#', ' ', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#',
                                         '#', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#', ' ', '#',
                                         '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#',
                                         '#', '#', '#', '#', '#', '#', ' ', '#', '#', '#', ' ', '#',
                                         '#', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#',
                                         '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'
                                       };
 
    if( recorrerLaberinto( laberinto, &mapa, obj ) == 1 )
        printf("\n\n\nFinal del laberinto encontrado");
    else
        printf("\n\n\nNo hay salida en este laberinto.");
 
    getchar();
	return 0;
}
 
void mostrarEstadoMapa( char laberinto[][TAM_COL] )
{
    int cont_fil, cont_col;
 
    system("cls");
    for( cont_fil = 0; cont_fil < TAM_FIL; cont_fil++ )
    {
        for( cont_col = 0; cont_col < TAM_COL; cont_col++ )
        {
            printf("%c", laberinto[cont_fil][cont_col]);
            printf("  ");
        }
 
        printf("\n\n");
    }
    Sleep(200);
}
 
int recorrerLaberinto( char laberinto[][TAM_COL], InformacionMapa *mapa, Objeto obj )
{
 
    if( obj.pos_x == mapa->fin_fil && obj.pos_y == mapa->fin_col )
    {
        obj.estaEnFinal++;
        return 1;
    }
 
    laberinto[obj.pos_x][obj.pos_y] = obj.simbolo;
 
    mostrarEstadoMapa( laberinto );
 
    if( laberinto[obj.pos_x][obj.pos_y + 1] == ' ' && obj.pos_y + 1 < TAM_COL )
    {
        obj.pos_y++;
        if( recorrerLaberinto( laberinto, mapa, obj ) == 1 )
            return 1;
    }
 
    if( laberinto[obj.pos_x + 1][obj.pos_y] == ' ' && obj.pos_x + 1 < TAM_FIL )
    {
        obj.pos_x++;
        if( recorrerLaberinto( laberinto, mapa, obj ) == 1 )
            return 1;
    }
 
    if( laberinto[obj.pos_x - 1][obj.pos_y] == ' ' && obj.pos_x - 1 >= 0 )
    {
        obj.pos_x--;
        if( recorrerLaberinto( laberinto, mapa, obj ) == 1 )
            return 1;
    }
 
    if( laberinto[obj.pos_x][obj.pos_y - 1] == ' ' && obj.pos_y - 1 >= 0 )
    {
        obj.pos_y--;
        if( recorrerLaberinto( laberinto, mapa, obj ) == 1 )
            return 1;
    }
 
    return 0;
}


	En línea

Cruzar la calle junto a mucha gente cuando el semáforo sigue en rojo da seguridad y espíritu de equipo... o cruzamos todos o morimos juntos.

vangodp

Desconectado

Mensajes: 455

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #5 en: 28 Marzo 2014, 20:16 pm »

Por eso me gustaba usar la función rand() para que elija una de las opciones.
Iba marcando el camino por si entrara en un camino sin salida y cuando no había salida hacia que volviera por donde entro hasta que tuviera un camino sin recorrer.
Hacia que por donde había estado le marcaba como 1, por explorar 0 y sin salida 2 por ejemplo.
cuando llega a un lugar que tenga 3 caminos posibles pues elija uno al azar. y vaya marcando con 1 por donde había estado.
lo mete cada paso dado en una matriz por si no hay salida que vuelva hasta encontrar un 0 otra vez XDD y importante es marcar esos caminos sin salida para que no vuelva entrar otra vez.
Aquí hicimos montón de cosas XDD
Algunos hicieron que lo encontrara el mas corto pero así no me molaba XDD
Si es un laberinto, debe buscar la salida no saber donde esta :laugh:

Todo depende de lo que quieres.
http://foro.elhacker.net/programacion_cc/ayuda_con_programa_urgente-t404470.0.html


	En línea

erest0r

Desconectado

Mensajes: 147

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #6 en: 28 Marzo 2014, 20:24 pm »

Si pero es que un algoritmo que busque aleatoriamente podria tardar una eternidad en recorrer todo el laberinto, redundando en caminos que ya hubiese pasado anteriormente


	En línea

Cruzar la calle junto a mucha gente cuando el semáforo sigue en rojo da seguridad y espíritu de equipo... o cruzamos todos o morimos juntos.

vangodp

Desconectado

Mensajes: 455

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #7 en: 28 Marzo 2014, 20:53 pm »

Pero buscar es una cosa y ir hacia el fin es otra.
Realmente cuando buscas haces elecciones no sabes donde esta en fin.
Y tanto no tarda. Allí tienes los algoritmos. Prueba los.
Para ir al final entonces lo programo para que lo haga señalando las casas por donde debe ir.
O le implemento un algoritmo de búsqueda que que me de el camino mas corto y en un ratico me dice donde esta el fin.
Para mi eso es trampa imagina que haces un juego, tu no sabes donde esta un personaje de la IA, tu quieres que el sepa donde estas?
Como dije depende de lo que quieres.
Lo que quería lo hice, haz tu lo mismo.


	En línea

erest0r

Desconectado

Mensajes: 147

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #8 en: 28 Marzo 2014, 22:20 pm »

Eso depende del escenario, para un juego es otra cosa, son distintas reglas


	En línea

Cruzar la calle junto a mucha gente cuando el semáforo sigue en rojo da seguridad y espíritu de equipo... o cruzamos todos o morimos juntos.

amchacon

Desconectado

Mensajes: 1.211

Re: Ayuda optimizacion busqueda de salida en laberinto

« Respuesta #9 en: 29 Marzo 2014, 11:13 am »

Cita de: erest0r en 28 Marzo 2014, 20:24 pm

Si pero es que un algoritmo que busque aleatoriamente podria tardar una eternidad en recorrer todo el laberinto, redundando en caminos que ya hubiese pasado anteriormente

Pero esque la idea esque no repitas caminos xD.

De todas formas si solo buscas una salida, no necesitas que sea aleatorio. Te abasta con hacerte alguna estructura que permita recursión (lista o pilas), le pones un while ya debería ir.

Función que determina si dos puntos A y B están conectados:

Código

#include <stack>
 
bool explora(char mat[][20],Cord inicio,Cord Destino,int TAMX,int TAMY)
{
    stack<Cord> Pila;
    Pila.push(inicio);
 
    while (Pila.size() != 0)
    {
        //cout<<Pila.top().x<<" , "<<Pila.top().y<<endl;
        // izquierda
 
        if (Pila.top().x > 0)
        {
            if (Pila.top().x-1 == Destino.x && Pila.top().y == Destino.y) return true;
            if (mat[Pila.top().x-1][Pila.top().y] == 0)
            {
                mat[Pila.top().x-1][Pila.top().y] = 1;
                Pila.push(Cord(Pila.top().x-1,Pila.top().y));
                continue;
            }
        }
 
        // derecha
 
        if (Pila.top().x < TAMX-1)
        {
            if (Pila.top().x+1 == Destino.x && Pila.top().y == Destino.y) return true;
            if (mat[Pila.top().x+1][Pila.top().y] == 0)
            {
                mat[Pila.top().x+1][Pila.top().y] = 1;
                Pila.push(Cord(Pila.top().x+1,Pila.top().y));
                continue;
            }
        }
 
        // arriba
 
        if (Pila.top().y > 0)
        {
            if (Pila.top().y-1 == Destino.y && Pila.top().x == Destino.x) return true;
            if (mat[Pila.top().x][Pila.top().y-1] == 0)
            {
                mat[Pila.top().x][Pila.top().y-1] = 1;
                Pila.push(Cord(Pila.top().x,Pila.top().y-1));
                continue;
            }
        }
 
        // abajo
 
        if (Pila.top().y < TAMY-1)
        {
            if (Pila.top().y+1 == Destino.y && Pila.top().x == Destino.x) return true;
            if (mat[Pila.top().x][Pila.top().y+1] == 0)
            {
                mat[Pila.top().x][Pila.top().y+1] = 1;
                Pila.push(Cord(Pila.top().x,Pila.top().y+1));
                continue;
            }
        }
 
       // mat[Pila.top().y][Pila.top().x] = 0;
        Pila.pop();
    }
 
    return false;
}

NOTA: Uso ceros en vez de ' '.


« Última modificación: 29 Marzo 2014, 11:19 am por amchacon »	En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

Páginas: [1] 2

Ir a:

Mensajes similares
	Asunto	Iniciado por	Respuestas	Vistas	Último mensaje
	[Ayuda] Necesito el Laberinto de MCKSys Argentina Programación Visual Basic	sebah97	5	3,484	23 Junio 2010, 19:37 pm por sebah97
	Ayuda con laberinto en una matriz Programación C/C++	edotropic	5	4,785	20 Diciembre 2013, 13:29 pm por leosansan
	urgente!ayuda, Laberinto C++ Programación C/C++	RuKsu	7	5,638	7 Diciembre 2014, 05:41 am por sebah97
	Ayuda, Codigo Laberinto Programación C/C++	RuKsu	0	2,785	10 Diciembre 2014, 21:03 pm por RuKsu
	guardar una salida de una búsqueda Desarrollo Web	mysqlway	0	1,916	21 Diciembre 2014, 01:28 am por mysqlway