Título: Optimizar algoritmo de búsqueda BFS Publicado por: KINGARZA 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
Título: Re: Optimizar algoritmo de búsqueda BFS Publicado por: AlbertoBSD 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 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
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 |