mejor camino entre dos puntos en grafo gigante

[darknesrul]

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

[jazcks]

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!

[rrbenx]

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

[Pogacha]

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

[darknesrul]

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.

[Pogacha]

Post triplicado

[Pogacha]

Post quintuplicado

[Pogacha]

Post cuadruplicado

[Pogacha]

Post duplicado

[Pogacha]

En el dijsktra cuando llegas al nodo final ya tienes la solución.

Escrito al vuelo:

Código [Seleccionar] Expand

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

[marcode]

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.

[darknesrul]

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.

[darknesrul]

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)

[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.

[Pogacha]

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!