알고리즘 최적화 - 여러 지점 사이의 가장 짧은 경로

StackOverflow https://stackoverflow.com/questions/1511585

문제

문제 : 많은 포인트가 있습니다. 이 각 지점에는 이미 계산되고 저장된 거리가있는 다른 지점에 대한 참조가있는 목록이 있습니다. 원점에서 시작하여 특정 지점을 통과하는 가장 짧은 경로를 결정해야합니다.

예 : 나는 휴가 중이고 특정 도시에 머무르고 있습니다. 나는 4 개 도시를 볼 수있는 한 방향 여행을하고 있으며 가능한 최소한의 거리를 여행하고 싶습니다. 나는 같은 도시를 두 번 이상 방문 할 수 없습니다.

현재 솔루션 : 지금 당장 나는 모든 가능성을 수동으로 반복하고 가장 짧은 경로를 저장하고 있습니다. 이것은 작동하지만 비효율적입니다. 또한이 문제는 결국 여러 원산지 지점에서 여러 대상 지점으로 검색을 포함하도록 확장되므로 검색 공간을 폭발시킬 수 있다고 생각합니다.

가장 짧은 경로를 검색하는 더 좋은 방법은 무엇입니까?

도움이 되었습니까?

해결책

업데이트 된 게시물에 응답하면 모든 가능성을 확인하는 솔루션은 최적입니다 (적어도 지금까지 더 나은 알고리즘을 발견 한 사람은 누구도). 예, 그것은 여행하는 세일즈맨이며, 모든 도시에 닿지 않고 모든 도시를 만지는 에센스 한 번. 최상의 솔루션을 검색하지 않으려면 더 빠르게 작동하는 휴리스틱을 사용하는 것이 유용하지만 이상적인 솔루션에서 불일치가 제한 될 수 있습니다.

향후 답변 자 : Floyd-Warshall 알고리즘 그리고 모든 플로이드와 같은 변형은 여기에 적용 할 수 없습니다.

다른 팁

일반적으로 당신은 잘못된 변형을 엄격하게해야합니다 ... 나는 당신이 branch_and_bound 메소드의 변형을 사용해야한다고 생각합니다.http://en.wikipedia.org/wiki/branch_and_bound

Norheim.se가 말했다 Dijkstra의 알고리즘 내 제안도 될 것입니다.

이번은 세일즈맨을 여행하는 것처럼 들리나요? 한 가지 해결책은 진화 알고리즘과 같은 최적화 기술을 사용하는 것입니다. 현재 당신은 철저한 검색을하고 있습니다. 그러나 나는 이것이 여행하는 세일즈맨 문제라고 생각하며 수 세기가 아니라면 수십 년 동안 해결되어 왔으며, 그러한 몇 가지 가능한 공격 방법이 있습니다. 구글은 당신의 친구입니다.

아마도 이것은 원래 포스터가 "각 가능성을 수동으로 반복하고 가장 짧은 경로를 저장한다"는 의미이지만, 기준 솔루션으로 보이는 것을 명시 적으로 만들고 싶다고 생각했습니다.

이미 2 점 짧은 경로 알고리즘이 있다고 가정합니다. 이것은 다양한 종류의 그래프에 대한 고전적인 솔루션을 가지고 있습니다. 모든 거리가 음성이없고 d (a-> b-> c) = d (a-> b) + d (b-> c)라고 가정합니다.

필수 사항은 S에서 경로가 시작되는 중간 도시 "ABCD"중 하나를 통과하고 E로 끝나는 것입니다.

예를 들어 Sabcde, Sacbde 등 ...

4 개의 중간 도시 만 있으면 24 개의 순열을 모두 열거합니다. 각 순열마다 가장 짧은 2 포인트 알고리즘을 사용하여 머리에서 꼬리까지 경로를 계산하고 총 거리를 계산하십시오.

그런 다음 시작과 끝점을 감안할 때 ABCD 중 하나에 부착 된 12 가지 가능성과 내부의 두 가지 가능성이 있습니다. 이 거리를 이미 계산 했으므로 S에서 머리까지, 꼬리까지 E까지의 거리를 추가하십시오. 최소값을 선택하십시오. 따라서 고정 된 내부 도시 세트의 중간 거리를 사전 계산하면 한 쌍의 시작 및 엔드 포인트에 대해 12 개의 2 점 짧은 경로 문제를 수행해야합니다.

이것은 분명히 중간 도시의 수가 증가함에 따라 제한적이지 않습니다. 그래프 구조에 더 큰 제한을 부과하지 않으면 더 잘할 수 있다는 것은 분명하지 않습니다 (이것은 물리적 유클리 데난 공간에 있습니까? 삼각형 불평등?).

내 생각 예 : 도시 사이의 모든 중간 거리가 O (1)이라고 가정합니다. 그래프에 제한이 없으면 S에서 중간 도시까지의 거리는 1이 1을 제외하고는 1000이 될 수 있습니다. 꼬리는 동일합니다. 따라서 첫 번째 도시를 방문하도록 강요 할 수 있습니다. 이제 한 층을 내려 놓고 첫 번째 도시를 "시작점"으로 가져 가십시오. 동일한 인수를 적용하십시오 : 그래프의 거리를 조작하여 다음 도시로 최선의 길을 갈 수 있습니다.

따라서 추가 가정 없이는 복잡성을 도울 수없는 것 같습니다.

Google MAP 사용자 인터페이스는 동일한 순서로 경로를 제공하면 대상 목록을 추가합니다. 자체 Google Maps API가 솔루션을 제공하지만 최적의 경로를 제공하지 않습니다.

Google Maps API는 이에 대한 솔루션을 제공합니다. 경로를 찾으려는 요청에서 플래그 'OptimizeWayPoints : True'를 제공해야합니다. 요청은 이렇게 보일 것입니다.

var request = {
            origin: start,
            destination: end,
            waypoints: waypts,
            optimizeWaypoints: true,
            travelMode: google.maps.TravelMode.DRIVING
        };

완전한 유틸리티가 JavaScript 및 HTML로 개발되므로 View 소스에서 유틸리티의 전체 코드를 볼 수 있습니다.

도움이되기를 바랍니다.

그래프의 가장자리는 양방향 인 것 같습니다. 이 경우, 당신이 찾고있는 알고리즘은 Dijkstra의 알고리즘.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top