위도/경도 쌍이 52 세트 이상 있습니다. 나는 단순히 모든 것을 통해 최단 경로를 찾을 필요가있다. 시작 지점이나 끝 지점이 어디에 있는지는 중요하지 않습니다.위도/경도 집합 중 가장 짧은 총 경로
저는 Dijkstra의 알고리즘을 여러 번 손으로 구현 했었고 실제로 다시 할 시간이 없었습니다. 나는 가까이에 오는 몇 가지를 찾았지만 대부분의 경우 각 가장자리에 대해 미리 계산 된 가중치가있는 원시 그래프가 필요합니다.
이런 식으로 최단 경로를 계산할 라이브러리 또는 기존 스크립트/응용 프로그램을 알고 있습니까? 코드/라이브러리는 Python이나 Clojure를 사용하는 것이 바람직하지만 실제로는 중요하지 않습니다.
감사
, 그것은 외판원 문제이며,이를 해결하기 위해 서브 최적하지만 매우 효과적인 방법은 파이썬에서 Simulated Annealing
는 이것을 Traveling Salesman Problem되지 않으며, 따라서 그것을 해결하기 위해 더 효율적인 방법이 없다? 이 닫힌 경로 인 경우
당신이 시작한 곳에서 끝나는 것을 규정하지 않은 TSP이기 때문에 이론적으로는 총 거리가 훨씬 짧아야합니다. –
피쉬! TSP는 O (n!)가 아닙니까? 그는 단지 52 쌍 = 8.07e + 67 가능성, 아니야? : p – mpen
아마도 _optimal_ 솔루션을 찾을 수있는 효율적인 방법이 없을지 모르지만, _ 좋은 해결책이 있습니다. –
에게, 내가 할 수 있었다 최고의 그래프 처리 라이브러리를 사용하는 것입니다 내 손을 위에 두는 것은 networkx이다. short path search에 대해 광범위한 다른 알 고리를 지원합니다.
이동하십시오. 정말 완벽하고 잘 설계되었습니다.
TSP에는 닫힌 경로가 필요하지 않습니다. 닫힌 경로가 없으면 문제는 동일하며 전체 경로 길이의 메트릭 만 다릅니다. 닫힌 경로에서 가장 좋은 경로는 '모든 가장자리의 합'이 최소화 된 경로입니다. 경로가 닫히지 않으면 "모든 가장자리의 합 - 가장 긴 가장자리" –
@ THC4k 나는 그것이 전혀 문제가 아니라는 것을 알고 있지만 그 주석은 가장 간단한 방법으로 코드를 완전히 끝내도록 내버려 둔다. . TSP는 이미 닫힌 경로로 해결했습니다. 감사! –