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

[sergio sevillano]

Jaume Figueras escribió:
> Hola,
>
> pues yo no se ver que relación hay entre lo que pide Sergio y el cálculo 
> de rutas óptimas o del TSP. Para mi Sergio pide algo parecido a una 
> solución de un circuito Euleriano en un grafo, o sea, como recorrer 
> todas las aristas de un grafo pasando solamente una vez por cada arista.
>
> De hecho, Sergio nos pide el circuito dentro de un grafo dirigido que 
> pase mínimo número de veces por cada arista que no es exactamente un 
> circuito Euleriano, ya que éste es más restrictivo que lo que nos pide 
> Sergio.
>
> Y hasta aquí puedo leer... No se como se 'llama' el problema que plantea 
> Sergio y no se dónde buscar, os dejo los enlaces de la wikipedia a ver 
> si alguien que sepa más dá con la solución del problema.
>
> http://en.wikipedia.org/wiki/Eulerian_path
> http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
>
> Salud,
>
> Jaume.
>
> _______________________________________________
> Talk-es mailing list
> Talk-es en openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-es
>
>   
el problema tiene mucha mas miga de lo que me esperaba,
(la ignoracia nos hace osados)

me leeré el texto de Oscar, perfecto para tarde de domingo de perros

el link de Jynus http://www.tsp.gatech.edu/maps/index.html
el plan a trip funciona en ciertos casos ,
como el que buscaba solucionar,
que era un nudo de autopistas.

pero no es exactamente el problema que buscamos.

bueno esta claro que la ruta óptima a ciegas es imposible.
entonces la condición previa debe ser que conocemos la topología correcta
incluso las oneway=yes (o bien vamos en bici con lo que no hay oneways).

creo que buscamos "el problema del cartero chino"
he encontrados algo interesante:

http://www.cs.swan.ac.uk/~csharold/cpp/SPAEcpp.pdf

http://nova.alc.upv.es/wiki/doku.php
http://nova.alc.upv.es/joomla/index.php/remository?func=select&id=7


sergio