Bueno, este es mi primer mensaje asi que antes que nada me gustaria presentarme. Mi nombre es Jose luis y vivo en Argentina. Estoy estudiando el segundo año de la carrera Ingenieria en Sistemas en la Universidad de Tandil (UNICEN), (creo que ahi se resume lo mas importante sobre mi....)
Bueno ahora les paso a explicar mi problema para ver si alguien me podria ayudar un poco:
El tema es que como trabajo final de una materia me hacen hacer una aplicacion que, ingresadas dos ciudades (de Argentina), me diga el mejor camino por ruta que puedo seguir para llegar desde el origen al destino, tomando en cuenta no solo las distancias sino tambien los costos por peajes, estaciones de servicio, tipos de rutas (asfaltadas o no),etc,etc.
Claramente lo primero que se me ocurrio (y creo que asi deberia ser) es modelar el problema utilizando grafos.
De esta manera cada nodo del grafo representa una ciudad y cada arco la carretera que une a esas dos ciudades.
El primer problema con esto es que el grafo tiene una gran cantidad de nodos y arcos, ya que el programa tiene que contemplar aun la mas pequeña ciudad que ni sus habitantes saben que existe, teniendo un total aproximado de 14350 nodos y 33000 arcos.
Teniendo ya el grafo entero cargado (lo cual no fue tarea facil), probe con el algoritmo de Dijkstra para obtener el mejor camino entre dos nodos pero obviamente con tantos vertices y arcos el algoritmo no da una respuesta en un tiempo razonable.
Llegado a este punto me encuentro sin salida ya que todos los grafos con los que he trabajado anteriormente eran mucho menores y el algoritmo funcionaba perfectamente por lo que nunca tuve necesidad de buscar otras alternativas.
Bueno ese es basicamente mi problema.... se acepta cualquier sugerencia
Desde ya muchas gracias
ni idea, pero asi rapido veo:
a) en vez de calcularlos cada vez, guarda todas las posibles soluciones de cada nodo, y luego solo tendras que acceder a la solucion ya calculada, lo que deberia ser mucho más rápido.
no se si es viable, porque salen millones de caminos posibles :P
b) divide y engloba el mapa en otros nodos/arcos mas generales, algo como: del nodo 1 al 1000, sera el nodo A, del 1000 al 2000 el B, etc...
c) probar con otro algoritmo? :P
suerte!
Floyd-Warshall (aunque yo solo lo llamaba Floyd)
Webs:
http://euitio178.ccu.uniovi.es/wiki/index.php/TP:Algoritmo_de_Floyd_-_Programaci%C3%B3n_din%C3%A1mica
http://sertel.upc.es/redes/floyd.pdf
http://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall
Espero que te sirva
No, lamentablemente el floyd no te servirá para eso.
Y si, la solución es el dijsktra modificado.
Tendrias que especificar si el costo a minimizar es el dinero empleado o el recorrido recorrido. Solo puede haber uno, luego de eso te pueden dar un limite de dinero a pagar en peajes o cosas así lo cual tan solo lleva a descartar nodos cuando se pasen de costo.
Si al dijsktra lo haces con un heap la complejidad será NLog2N, para N = 1<<16 tenemos 16 << 16 = 1M. Lo cual con una constante de 100 instrucciones por iteración te lo tiene que comer en 1 segundo en un pentium 100, 1/24 de segundo en un Pentium 4 de 2.4ghz. Como peor caso!
Por pocos $ te lo hago ... jaja
Bueno antes que nada muchas gracias por las respuestas.
Como bien dice Pogacha en este caso Floyd no me sirve ya que estaria calculando el mejor camino entre cada par de nodos y esto solo me suma trabajo extra que no necesito.
Tambien creo que la solucion seria un Dijkstra modificado para que no calcule el mejor costo entre el nodo origen y todos los demas sino solamente entre el origen y el destino que son los dos que me interesan.
En cuanto a la implementacion del Dijkstra ya lo tengo hecho con un heap, lo que no se es como "frenarlo" cuando encuentra el mejor camino al nodo que a mi me interesa.
Sobre el costo a minimizar no es solo la distancia o el costo empleado o el dinero (cada uno por separado) sino que tiene que ser un "promedio" por decirlo de alguna manera de todos, por lo que para comparar los arcos tengo una variable double "coeficiente" donde tengo en cuenta tanto la distancia, costo de dinero, etc, que van multiplicando o dividiendo en esta variable segun sea proporcional o inversamente proporcional respectivamente.
Mmm... creo que esto ultimo no quedo muy claro. Por ejemplo seria algo asi:
coeficiente= (distancia * dinero) / estaciones de servicio
Es decir, cuanto mayor sea la distancia o el dinero requerido mayor sera el coeficiente y menor prioridad tendra en el heap. A su vez, cuantas mas estaciones de servicio haya en el recorrido, mas chico se hara el coeficiente y mayor prioridad tendra en el heap.
Post triplicado
Post quintuplicado
Post cuadruplicado
Post duplicado
En el dijsktra cuando llegas al nodo final ya tienes la solución.
Escrito al vuelo:
void HacerDijsktra(Nodo *origen, Nodo *destino)
{
Heap<Nodo*, 1<<16> elHeap;
// el arranque:
elHeap.Push(origen);
origen->Poner_Origen( null );
origen->Poner_Costo( 0.0 );
while(elHeap.IsNotEmpty() && (Nodo *este = elHeap.Pop()) != destino) {
for(Arco *a = este->Tomar_Primer_Arco(); a; a=a->Siguiente())
{
double costo=a->Tomar_Costo() + este->Tomar_Costo();
// ademas tenes que ver aqui que no te pases de limites
if(costo < a->Tomar_Nodo_Destino()->Tomar_Costo()) {
// todos los nodos devieron ser previamente inicializados con un
// peor caso EJ: for(n=Nodos::Begin; n!=Nodos::End; n++) n->Poner_Costo(INF);
elHeap.Push(a->Tomar_Nodo_Destino());
a->Tomar_Nodo_Destino()->Poner_Costo(costo);
a->Tomar_Nodo_Destino()->Poner_Origen(a);
}
}
}
// aca haces el trackback.
List<Nodo*> Camino;
for(Nodo *n = destino; n; n=n->Tomar_Origen()) Camino->Push(n);
// Aca supuse mal que siempre se llega ojo con esto!
}
Saludos
No sé a que te refieres cuando dices que te tarda mucho tiempo, pero el que tengo yo para 16.000 nodos y varias decenas de miles de arcos me tarda entre 1 y 10 milisegundos dependiendo de la distancia a la que se encuentren el origen y el destino.
No utilizo ninguna heurística ni busqueda especial ni nada, ya que comprobé que le quitaba un tiempo precioso a la optimización que hice. simplemente expando la búsqueda en anchura hasta que alguna rama encuentra el destino, y a partir de ahí cualquier otra búsqueda que supere el coste de la mejor ruta encontrada hasta el momento es descartada.
Si a ti te tarda muchísimo más el problema puede estar en la implementación.
Cita de: marcode
Si a ti te tarda muchísimo más el problema puede estar en la implementación.
No se si esto tendra algo que ver pero el grafo esta implementado mediante templates y utilizando como estructura para los vertices y arcos, mapas (de la STL) por lo que quizas puede tener un costo un poco mayor operaciones como obtener la lista de vertices o de adyacentes a un nodo que mediante otras implementaciones.
Igual ahora voy a probar un poquito con lo que tiro ahi Pogacha y despues les comento.
ah me olvidaba..... una preguntita de ignorante.... el Dijkstra deberia andar igual de bien en grafos no dirigidos, no?. O sea que siempre los arcos vayan de a pares (de A a B y de B a A)
Cita de: darknesrulCita de: marcode
Si a ti te tarda muchísimo más el problema puede estar en la implementación.
No se si esto tendra algo que ver pero el grafo esta implementado mediante templates y utilizando como estructura para los vertices y arcos, mapas (de la STL) por lo que quizas puede tener un costo un poco mayor operaciones como obtener la lista de vertices o de adyacentes a un nodo que mediante otras implementaciones.
Pues seguramente. Operaciones que no sean a nivel de procesador y memoria repetidas miles de veces al final se acaban notando mucho. Yo incluso usé aritmética de punteros para las listas, aunque tampoco creo que sea necesario llegar a ese punto.
pd: Los nodos adyacentes los tengo en una lista individual de punteros en la estructura del nodo por lo que así la comprobación se hace rápida en un bucle.
Como te dice marcode, hasta un backtracking con la primera heuristica (BFS) puede andar bastante bien en un problema tan geometricamente soluble. Pensa que el grafo se desarrolla en un plano y que la respuesta tiende a ser el camino mas recto.
De todos modos el dijsktra es lo correcto y es muy sencillo también. Solo si cometiste un error garrafal podrias tener tantas penalidades ...
Lo mejor es que te hagas listas enlazadas para todo lo que sean listas y el heap en un pool y ya (ya tenes la cantidad de nodos y es constante así que no hay problemas).
Puedes trabajar también por indexación y vectores paralelos lo cual hace que el algoritmo sea mas digerible en su codificación y creo la penalidad en tiempo es casi nula.
Saludos!
bueno muchas gracias por sus respuestas. Ahora voy a probar utilizando un Heap Fibonacci para ver si mejoro el tiempo. Despues comento como fue esto...
Bueno amigos, problema resuelto. Resulto que no era ningun problema de implementacion, ni de estructuras ni nada de lo que uno piensa en primera instancia...... que era entonces? Era la MIERDA de compilador (o IDE mejor dicho, no se que compilador usa) de Micro$oft (Microsoft Visual Studio 2005).
De casualidad se me ocurrio probar el mismo codigo en el IDE de Dev-c++ de Bloodshed (compilador gcc, creo) y anda perfecto. Responde instantaneamente con nodos que estan en dos puntas opuestas del mapa.
Con lo que ahora surge una nueva preguntilla, esta vez mas facil jeje.... Que IDE me recomiendan usar para crear una aplicacion tipo Windows que no sea demasiado dificil de entender. Lo primero que se me ocurre es Borland pero no se..... Como siempre, se escuchan propuestas!!! :D :D
De nuevo gracias por todas las respuestas..... muy buen foro y muy buena gente en el
Para mi el mejor compilador es el GCC, esta mas actualizado que cualquiera, si intentas usar constructores virtuales en los demas (Borland C++ Builder 6.0, Visual C++, Visual Studio, Open Watcom) no te compilara.
Y para que sea mas facil de usar te recomiendo code blocks, yo antes usaba DevC++ pero me cambie. No me gustaba como ponian los errores y unas cuantas cosas mas.
Pero si quieres usar ventanas y cosas por el estilo... yo me decanto por el Borland C++ Builder.
Creo que el compilador no puede tener nada que ver, mejor revisa el codigo a ver que has hecho mal.
Por otro lado creo que Visual Studio 2005 debe ser bastante mejor que el GCC.
De todas formas el code blocks no es malo para nada y es mucho mas recomendable que el DevC++
Saludos
es que el codigo es exactamente el mismo, si fuera problema de este tendria que andar mal en los dos pero sin embargo en el Dev anda perfecto.
Y en cuanto a que compilador o IDE es mejor creo que ya es una cuestion de gustos y costumbre asi que cada uno tendra sus preferencias, yo por mi parte pongo las manos en el fuego por el GCC 8)
Despues voy a probar con el Builder a ver que onda....
El Visual 2005 trae una implementación de la STL que añade muchos checks por seguridad que no había en otras versiones. Es probable que encuentres diferencias de rendimiento incluso entre Visual 2003 y Visual 2005. Existen macros que desactivan esos checks pero no las recuerdo porque no uso esta versión del compilador. Busca en google, hay varias discusiones relativas a pérdidas de rendimiento en la STL en el 2005.
Citar
Para mi el mejor compilador es el GCC, esta mas actualizado que cualquiera, si intentas usar constructores virtuales en los demas (Borland C++ Builder 6.0, Visual C++, Visual Studio, Open Watcom) no te compilara.
¿Constructores virtuales? Esto no existe, a no ser que te refieras a implementar el idiom en cuyo caso no veo que problema hay con cualquiera de los compiladores que indicas.
mmm.... esto de los checks de la stl me intereso. Podrias explicar un poquito mas sobre esto ya que busque en google pero nada, sobre todo como deshabilitarlos, ya que probe el mismo codigo en Borland y anda perfecto pero estoy mas acostumbrado al Visual y no me gustaria tener que cambiarme a otro entorno a estas alturas
No se si seran los mismos que causan perdidas de rendimiento, pero en Visual Studio 2005 para desactivar los checked iterators tienes que poner el flag de compilacion _SECURE_SCL a 0. Eso si, en TODOS los proyectos de la solución, o empezaras a tener errores en el proceso de linkado o, aun peor, comportamientos extraños en tiempo de ejecución.
Cita de: hotcamus¿Constructores virtuales? Esto no existe, a no ser que te refieras a implementar el idiom en cuyo caso no veo que problema hay con cualquiera de los compiladores que indicas.
Es un patron de diseño, no me refiero a poner virtual antes de un constructor.
[/code]
_SECURE_SCL es una de las macros. La otra que yo conozco es _HAS_ITERATOR_DEBUGGING.
Lo mejor para deshabilitarlos es añadirlas en las opciones de todos los proyectos de la solución /D_SECURE_SCL=0 por ejemplo.
Citar
Es un patron de diseño, no me refiero a poner virtual antes de un constructor.
A eso me referia con idiom. Si no recuerdo mal, para implementarlo sólo se hace uso de dos métodos virtuales (create y clone), por eso decía que no sé dónde encontraste el problema.
class A
{
...
virtual A *Clone() const;
};
class B : public A
{
virtual B *Clone() const;
};
Esto solo compila en GCC, y los constructores virtuales se añadieron en el 97 asi que han tenido tiempo de sobra para implementarlo.
Se puede cambiar el tipo que devuelve el B::Clone, pero paso, prefiero cambiar de compilador a cambiar codigo que ya funciona.
Esto funciona en el Visual 2005:
class A
{
virtual A *Clone() const { return new A; }
};
class B : public A
{
virtual B *Clone() const { return new B; }
};
B b;
A* ese = b.Clone();
En cualquier caso, que use el que más le guste hasta que encuentre un problema que no pueda solucionar (yo los he tenido con el Borland).
Yo hice la prueba con el Visual 2003 y no funciono. Ya era hora de que lo arreglaran, ya que esto se añadio en el 96 o 97.