위도와 경도가 50 노드 이상입니다. 그것들은 서로 연결되어 있지 않습니다. 하나의 노드를 시작과 끝으로 간주합니다.최단 경로를 찾으려면
'start'에서 시작하여 시작점에서 끝나고 모든 노드를 통과하는 노드를 통과하는 최단 경로를 찾아야합니다.
참고 : 구글지도 API
위도와 경도가 50 노드 이상입니다. 그것들은 서로 연결되어 있지 않습니다. 하나의 노드를 시작과 끝으로 간주합니다.최단 경로를 찾으려면
'start'에서 시작하여 시작점에서 끝나고 모든 노드를 통과하는 노드를 통과하는 최단 경로를 찾아야합니다.
참고 : 구글지도 API
당신이 설명하는 문제는 NP-하드입니다 Euclidean TSP 인을 사용하지 않고.
매우 작은 입력의 경우 무차별 대입을 사용하여 수행 할 수 있습니다. 더 큰 입력의 경우 근사 알고리즘을 사용할 수 있습니다 (링크에서 언급 한 것과 같이 2 근사를 보장합니다). 여기에 샘플 데이터가없는 그러나
참고할 수 있도록 여기에 코드를 붙여주십시오. TSP를 사용하고 있기 때문에 정확한 결과를 제공하지 못하기 때문입니다. 노드를 위해 왼쪽/오른쪽 자식을 찾아서 그래프를 연결하고 그 결과를 얻을 필요가 있습니다. –
, 나는이 작업을 할 수 있습니다 생각 :
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
}
}
자세히 설명해 주시겠습니까? –
예, 이름 파일에는 모든 노드가 포함됩니다. 그런 다음 그래프가 있습니다 (예 : ARACNE_graph). 따라서 파일 이름의 노드에서 동일한 노드 (names [i], names [i])까지의 최단 경로를 검색하려고합니다. – Sadegh
아이디어를 자세히 얻고 있습니다! –
하면 포인트 사이의 대략적인 거리가 충분합니까? 각 노드 쌍의 거리가 명시 적으로 주어 졌습니까? – Codor
질문에 간단한 설명을 제공해 주시겠습니까? 그래프가 지시됩니까? 그렇다면 최단 경로가 모든 노드를 통과 할 수 없습니다. – Dany
@DineshAppavoo 연결되지도 않고 지시되지도 않습니다. 나는 그것에 대한 최단 경로에 대한 해결책을 얻을 필요가있다. –