최단 경로를 찾으려면

Question

위도와 경도가 50 노드 이상입니다. 그것들은 서로 연결되어 있지 않습니다. 하나의 노드를 시작과 끝으로 간주합니다.

'start'에서 시작하여 시작점에서 끝나고 모든 노드를 통과하는 노드를 통과하는 최단 경로를 찾아야합니다.

참고 : 구글지도 API

Answer 1

당신이 설명하는 문제는 NP-하드입니다 Euclidean TSP 인을 사용하지 않고.

매우 작은 입력의 경우 무차별 대입을 사용하여 수행 할 수 있습니다. 더 큰 입력의 경우 근사 알고리즘을 사용할 수 있습니다 (링크에서 언급 한 것과 같이 2 근사를 보장합니다). 여기에 샘플 데이터가없는 그러나

Answer 2

, 나는이 작업을 할 수 있습니다 생각 :

names<-#read your nodes 
rest<-list() 
A<-list() 
n=1 
for (i in 1:50){ 
    A<-get.all.shortest.paths(aracne_graph, names[i], names[i], mode = c("all"), weights=NULL) 
    rest[[n]]<-A$res 
    n<-n+1 
    } 
}