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

 

 


Tema destacado: Usando Git para manipular el directorio de trabajo, el índice y commits (segunda parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Optimizar algoritmo de búsqueda BFS
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Optimizar algoritmo de búsqueda BFS  (Leído 1,673 veces)
KINGARZA

Desconectado Desconectado

Mensajes: 33

Facebook: Luis Garza


Ver Perfil
Optimizar algoritmo de búsqueda BFS
« en: 3 Agosto 2016, 07:01 am »

Hola a todos!!
Como algunos sabran estoy aprendiendo busquedas y me he topado con el siguiente problema:
LINK: https://omegaup.com/arena/problem/colosus-Laberinto#problems
O bien aqui lo escribo:

Colosus (Laberinto)

Límite de memoria   32MB
Límite de tiempo (caso)   1s
Límite de tiempo (total)   60s

Descripción

En este problema tu tomas el papel de el gran héroe Colossus tiene la misión de rescatar a la princesa omitilda de un laberinto, pero el maligno pachus quiere matar a la princesa.Lo único con lo que cuentas es con el mapa del laberinto y el tiempo en el que pachus va a llegar a la princesa, por lo que tu tienes que llegar en el menor tiempo posible a ella. El mapa consta de una cuadricula la cual tiene una 'X' en el lugar donde no puedes pasar Una 'C' donde tú te encuentras al principio, y una 'O' donde se encuentra la hermosa omitilda y una 'L' en aquellos lugares donde el campo este libre y puedas pasar.

Problema

Tu tarea consiste en escribir un programa que determine el menor tiempo en el que puedes llegar a rescatar a tu princesa tomando en cuenta que tu te mueves a una velocidad de un cuadro por seg. En caso de que no puedas llegar a salvarla escribirás en la pantalla un -1 en el caso contrario escribirás el tiempo en el que llegaste a ella. en caso de llegar al mismo tiempo considera que la princesa se salva.

Entrada

Tu programa deberá leer del teclado los siguientes datos: En la primera línea los números M, N y T separados por un espacio donde los primeros dos son las dimensiones del laberinto y T el tiempo en que pachus llegara con la princesa. Las siguientes M líneas contendrán N caracteres que representaran el mapa. Donde 3 <= M,N <=1000.

Salida

Tu programa deberá escribir un solo número que represente el tiempo en que llegaste ó -1 en caso de que no hayas llegado.

Ejemplos

Entrada   Salida
5 5 8           6
XXXXX
XCLLX
XXXLX
XOLLX
XXXXX

Consideraciones

Tu programa deberá ejecutarse en un tiempo máximo de 1 segundo.

Lo que yo hago es usar el algoritmo de búsqueda por anchura en un grafo (BFS), desafortunadamente mi respuesta me la 80% porque da limite de memoria podrian explicarme como puedo optimizar este programa por favor?
GRACIAS.
Código
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 1000
  5. char ady[MAX][MAX];
  6. bool visitado[MAX][MAX];
  7.  
  8. struct Estado{
  9.    int x;
  10.    int y;
  11.    int d;
  12.    Estado(int x1, int y1, int d1) : x(x1), y(y1), d(d1) {}
  13. };
  14.  
  15. int BFS(int x, int y, int h, int w){
  16.    Estado inicial(x,y,0);
  17.    queue<Estado>estados;
  18.    estados.push(inicial);
  19.    memset(visitado, false, sizeof(visitado));
  20.    int dx[4] = {0, 0, 1, -1};
  21.    int dy[4] = {1, -1, 0, 0};
  22.  
  23.    while(!estados.empty()){
  24.        Estado actual = estados.front();
  25.        estados.pop();
  26.        if(ady[actual.x][actual.y] == 'O')
  27.            return actual.d;
  28.        visitado[actual.x][actual.y] = true;
  29.        for(int i = 0; i < 4; i++){
  30.            int nx = dx[i] + actual.x;
  31.            int ny = dy[i] + actual.y;
  32.  
  33.            if(nx >= 0 && nx < h && ny >= 0 && ny < w && ady[nx][ny] != 'X' && !visitado[nx][ny]){
  34.                Estado adyacente(nx, ny, actual.d + 1);
  35.                estados.push(adyacente);
  36.            }
  37.        }
  38.    }
  39.    return -1;
  40. }
  41.  
  42. int main(){
  43.    cin.tie(0);
  44.    ios_base::sync_with_stdio(0);
  45.    int h, w, x, y, t;
  46.    cin>>h>>w>>t;
  47.    for(int i = 0; i < h; i++){
  48.        for(int j = 0; j < w; j++){
  49.            cin>>ady[i][j];
  50.            if(ady[i][j] == 'C'){
  51.                x = i;
  52.                y = j;
  53.            }
  54.        }
  55.    }
  56.    cout<<BFS(x, y, h, w);
  57.    return 0;
  58. }


En línea

AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.619


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Optimizar algoritmo de búsqueda BFS
« Respuesta #1 en: 3 Agosto 2016, 13:26 pm »

Tienes que resumir el Grafo.

Este problema se parece al que propuse en

https://foro.elhacker.net/programacion_cc/iquestimposible_juego_de_rompecabezas_imposible-t455410.0.html

En tan solo ese ese cuadro de 4x4 y con las reglas de ese juego, el generar todos los nodos consume toda la ram de mi humilde sistema XD

Ahora tu caso, cada que haces un push de un nodo nuevo generas una mini clase por lo que veo, tiene su constructor y todo eso, eso necesita mas memoria por nodo. Creo no estoy seguro ya que NUNCA he visto un constructor en una estrucutura.

Mejor creo crea una funcion aparte que te genere un nodo y te reserve la memoria necesaria para cada nodo.

Acabo de validar que lo anterior NO es cierto usan la misma momoria que la estructura normal.

Ahora como te mencione al principio es posible Resumir el grafo. En lugar de generar un nodo por cada espacio recorrible es posible que generar un Grafo mas compacto.

Ejemplo del ejemplo usado en la descripcion del problema.


nodo 0 una sola arista peso 2 a la izquierda.
nodo 1 una sola arista peso 2 arriba
nodo 2 una sola arista peso 2 a la derecha
Fin

Suma de la ruta 6

Incluso si solo es una arista puedes omitir ese nodo y solo dejar nodos que tengan mas de una arista (donde existan mas de un camino)

La otra es
Código
  1. #define MAX 1000
  2. char ady[MAX][MAX];
  3. bool visitado[MAX][MAX];

Ahi ya estas desperdiciando al menos 2 MB

por que no lo declaras dinamicamente en tiempo de ejecución y los usas solo mientras es necesario, una vez que ya no son necesarios puedes hacerles free y te ahorras hasta 2 MB de memoria.

Saludos


« Última modificación: 3 Agosto 2016, 17:06 pm por AlbertoBSD » En línea

Donaciones
1Coffee1jV4gB5gaXfHgSHDz9xx9QSECVW
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Python] Optimizar busqueda de primos
Scripting
camaleonh 0 2,279 Último mensaje 28 Febrero 2012, 08:16 am
por camaleonh
Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor
Programación General
painkillerpucela 1 2,440 Último mensaje 20 Noviembre 2012, 13:37 pm
por Oblivi0n
Algoritmo A* , Busqueda en Profundidad y Busqueda en Anchura
Java
HackingLikor 0 1,630 Último mensaje 4 Mayo 2016, 01:08 am
por HackingLikor
Optimizar busqueda en un datagridview
.NET (C#, VB.NET, ASP)
carlos7x 4 3,185 Último mensaje 6 Septiembre 2017, 15:33 pm
por Serapis
Busqueda de Algoritmo
Ingeniería Inversa
platano99 2 927 Último mensaje 19 Enero 2019, 20:35 pm
por kub0x
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines