경로 계획 - 여러 대상

Question

문제는 다음과 같습니다.

그래프 G = (V, E)입니다. 정점 서브 ​​그룹 U < = V 및 시작 정점 s. 에지에 대한 가중 함수 w.

내가 U.

계산은 근사 할 수있다

• 의 모든 정점 통과의 '에서 최단 경로를 찾을 필요, 계산 시간 및 경로 길이 사이에 균형이 있어야한다. 최단 경로에 대한 근사값을 생성하는 빠른 알고리즘/경험이 필요합니다.
• 이 알고리즘은 너무 복잡해서는 안됩니다 (C++). 예를 들어, 이것을 여행 세일즈맨 문제로 만들고 TSP 솔버 라이브러리 또는 일종의 발견 적 방법을 사용하지만 아무 것도 찾을 수없는 방법을 생각해 보았습니다. 그리고 나 자신을 발견 적으로 구현하는 것도 나을 것입니다 단단한.

감사합니다. =]

Answer 1

3 개의 꼭지점 S, A 및 B가 있다고 가정하십시오. 자, 이제부터는 A에서 B까지의 최단 경로를 찾아야합니다. 가장 쉬운 방법은 어떤 점을 찾는 것입니까? S : A 또는 B에 더 가깝습니다. 그래프에 실제로 공간 데이터가있는 경우 정점의 좌표를 사용하여 근사값을 구할 수 있습니다. 그렇지 않으면 S에서 각 대상으로 최단 경로를 가져야합니다. 가장 가까운 목적지를 선택하십시오.이 경우 A라고 말한 다음 거기로 여행하십시오. 이제 당신이 떠나야 할 유일한 곳은 B입니다. A에서 B까지 최단 경로를 계산하고 거기로 가십시오.

이제 2 개 이상의 대상이있는 상황에서이 작업을 재귀 적으로 수행 할 수 있습니다. 당신이 당신의 그래프, A *, 다 익스트라의 알고리즘에 맞는 어떤 검색 알고리즘을 사용하여, 나는 C++를 모르겠지만, 여기 당신이 closestNode 및 getShortestPath 기능을위한

function pathThrough(startNode,destinationNodes[]) 
    closestNode = getClosestNode(startNode,destinationNodes) 
    newDestinations = removeFromArray(destinationNodes,closestNode) 
    return joinPaths(getShortestPath(startNode,closestNode),pathThrough(closestNode,newDestinations.)) 

을 시작 얻을 수있는 일부 의사이야 ...

Answer 2

이것은 TSP 설정 문제 또는 일반화 된 TSP라고하는 여행 판매원 문제의 변형입니다. 위키피디아 link입니다.

일반화 된 TSP 문제를 그래프의 노드 수를 두 배로 늘리지 않고 TSP 문제로 변환하기위한 위의 문서 링크는 method에 대한 링크입니다.

레코드 보유 TSP 솔버는 무료로 사용할 수 있으며 Concorde로 알려져 있으며 here에서 다운로드 할 수 있습니다.이 파일은 명령 줄 도구 (아마도 확실하지 않은 라이브러리)로 실행할 수 있습니다.

게임마다 RevolvoMan4k에 대한 솔버를 만들려고 시도 할 때 GTSP를 보았을 때 버튼을 최소로 눌렀을 때 각 레벨에서 모든 돈을 얻었습니다. (재미있는 게임이지만 레벨 50 이후에는 레벨이 무작위이므로 일부는 불가능할 수 있으므로 'N'으로 건너 뛸 필요가 있음).