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 <i...@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.
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Talk-es mailing list Talk-es@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-es
