La línea más corta para un montón de puntos en postgis

Question

Yo hava una muy interesante problema, que yo estoy trabajando ahora mismo. Yo hava un conjunto de datos con un par de puntos, y me gustaría saber la LÍNEA más corta para la interconexión de cada punto. Sin necesidad de enrutamiento etc. El resultado debe ser una lista ordenada con los puntos o un linestring...

Me gustaría realmente apreciamos su opinión, yo tengo una idea sobre el concepto, pero no sé por dónde empezar. Esta tuerca es duro de roer. Es como una dijkstra-uno-a-muchos problemas, pero sin la hoja de ruta, así que debería ser más fácil y más rápido....

Gracias! Martin

---

editar:

Answer 1

Parecería que lo que se quiere lograr es un camino Hamiltoniano.

En el campo matemático de la teoría de grafos, un camino Hamiltoniano (o trazabilidad camino), es un camino en un grafo no dirigido, que visita cada uno vértice exactamente una vez.

PostGIS 2.0 ha topología de apoyo, así que tal vez usted puede implementar con eso. No estoy seguro si hay fuera de la caja soluciones, aunque. Se advierte que este es un NP-completo el problema. Encontrar la ruta de acceso es un reto en sí mismo, mucho menos el menor. Aunque si los puntos no son muchos, a continuación, debe ser capaz de manejar. La buena suerte.

Answer 2

Gracias por la entrada! Se los agradezco. He encontrado mi solución y funciona! Para todos los demás, que tiene un problema similar a leer estos artículos en la Wikipedia y comenzar su investigación:

• http://en.wikipedia.org/wiki/Travelling_salesman_problem
• http://en.wikipedia.org/wiki/Local_search_%28optimization%29

Y tbh el vecino más cercano es ya una solución fuerte, con k-opt puede optimizar, pero para optimizar el 5% más abajo - se necesita un montón de tiempo. He probado con mis datos 'en bruto' y había 10ms para obtener un vecino más cercano solución en 100 puntos. Pero furtherdown el k-opt está ejecutando durante varios minutos...