[Talk-es] cálculo de ruta óptima

[Iván Sánchez Ortega]

El Sábado, 13 de Diciembre de 2008, Jaume Figueras escribió:
> pues yo no se ver que relación hay entre lo que pide Sergio y el cálculo
> de rutas óptimas o del TSP.

Pues yo creo que sí se puede convertir el problema de Sergio en un TSP. A 
saber:

Coges el grafo, y transformas los nodos en aristas y las aristas en nodos. Es 
decir, por cada arista del grafo creas un nodo; por cada nodo que tienen en 
común un par de aristas, creas una arista. Se le da un peso cero a todas las 
aristas del nuevo grafo.

(No se puede llamar un grafo dual, porque la dualidad de grafos es otro 
concepto distinto).

En este nuevo grafo, el recorrer un nodo corresponde a completar una calle. 
Cada nodo tendrá asociada la longitud de la arista correspondiente en el 
grafo origen, pero este número no es un peso, a priori.

Ahora bien, ¿qué pasa con las calles que hay que recorrer dos veces? Aquí es 
donde entran en juego las simplificaciones y el TSP.

Para cada nodo del nuevo grafo, se calcula el "spanning tree" al resto de 
nodos, para calcular el peso de hacer un recorrido entre un par de nodos 
cualesquiera (el peso será el sumatorio de las longitudes asociadas a todos 
los nodos por los que se ha pasado al hacer el árbol).


Así que al final, se tiene un conjunto de nodos, una tabla que te da las 
distancias entre todos los nodos... y el problema es recorrer todos los nodos 
con un coste mínimo. Un TSP de toda la vida.

(Véase que el coste intrínseco del problema no se tiene en cuenta, dado que 
hay que recorrer todas las calles al menos una vez sí o sí; en el caso 
óptimo, que es que el TSP te diga que el coste es cero, significa que no se 
repite ninguna calle).



Saludos algorítmicos,
-- 
----------------------------------
Iván Sánchez Ortega <ivan en sanchezortega.es>

Aviso: Este e-mail es confidencial y no debería ser usado por nadie que no sea 
el destinatario original. No se permite la reproducción mediante fotocopia, 
walkie-talkie, emisora de radioaficionado, satélite, televisión por cable, 
proyector, señales de humo, código morse, braille, lenguaje de signos, 
taquigrafía o cualquier otro medio. Bajo ningún concepto debe traducirse al 
francés este e-mail. Este e-mail no puede ser ridiculizado, parodiado, 
juzgado en una competición, o leído en voz alta con un acento gracioso 
llevando un bigote falso y/o cualquier tipo de sombrero, incluyendo pero no 
limitándose a pañuelos. No inciten ni provoquen a este e-mail. Si está 
medicándose, puede experimentar nauseas, desorientación, histeria, vómitos, 
pérdida temporal de la memoria a corto plazo y malestar general al leer este 
e-mail. Consulte a su médico o farmacéutico antes de leer este e-mail. Todas 
las modelos descritas en este e-mail son mayores de 18 años. Si ha recibido 
este e-mail por error es probablemente porque estaba bebiendo cuando escribí 
la dirección del destinatario.
------------ próxima parte ------------
Se ha borrado un mensaje que no está en formato texto plano...
Nombre     : no disponible
Tipo       : application/pgp-signature
Tamaño     : 197 bytes
Descripción: This is a digitally signed message part.
Url        : http://lists.openstreetmap.org/pipermail/talk-es/attachments/20081214/c80efb86/attachment.pgp