Iván Sánchez Ortega escribió:
> 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.
>
>
el problema de tu solución es que a veces entra en el nodo (un tramo de
calle) y vuelve a salir por donde ha entrado,
es decir, imaginando una doble T entro por {1} y puedo girar a dcha {2}
o izq {3}, elijo izq {3} y vuelvo a tener la opción de dcha {4} o izq
{5} pero la solución puede mandarme a dcha anterior {2}. lo que supone
en la realidad a recorrer el tramo y hacer un cambio de sentido. como
hemos simplificado los arcos como nodos la solución no entiende que
estoy volviendo sobre mis pasos.
lo que hay que evitar para que funcione bien. (no se si me he explicado
con claridad)
> 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).
>
>
>
esto ultimo me he perdido
he intentado
resolver un problema como dices con el software Grafos del que os pasé
un link
y que solo resuelve TSP, creo que solo funcionaría de manera correcta si
es dirigido (todas las calles oneway)
unas fotos de ejemplo
http://www.tumbao.ws/osm/cpp/pinocentinelaJOSM (calles reales de ejemplo)
http://www.tumbao.ws/osm/cpp/pinocentinelaGrafoTSP_cruces.png (los nodos
son los cruces del ejemplo) esta solución es la ruta óptima para
recorrer todos los cruces, valdría para recoger los nombres de todas las
calles pero no para trazas de todas las calles.
http://www.tumbao.ws/osm/cpp/pinocentinelaGrafoTSP_arcos.png (los nodos
son las calles del ejemplo) ocurre el problema que he mencionado antes.
> Saludos algorítmicos,
>
>
idem
> ------------------------------------------------------------------------
>
> _______________________________________________
> Talk-es mailing list
> Talk-es@openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-es
>
_______________________________________________
Talk-es mailing list
Talk-es@openstreetmap.org
http://lists.openstreetmap.org/listinfo/talk-es
