10 점이 있다고 가정합니다. 나는 각 지점 사이의 거리를 안다.알고리즘 : 모든 점 사이의 최단 경로
모든 포인트를 통과하는 가능한 가장 짧은 경로를 찾아야합니다.
몇 가지 알고리즘 (Dijkstra, Floyd Warshall, ...)을 시도해 보았습니다. 시작과 끝 사이의 최단 경로를 모두 제공하지만 경로상의 모든 지점을 만들지는 않습니다.
순열은 잘 작동하지만 리소스가 너무 비쌉니다.
이 문제를 조사하기 위해 어떤 알고리즘을 사용하면 좋을까요? 아니면 위에서 언급 한 알고리즘을 사용하여 문서화 된 방법이 있습니까?
travelling salesman problem을 살펴보십시오.
일부는 heuristic solutions입니다. 그들은 당신에게 100 % 정확한 결과를 줄 수는 없지만 적당한 시간 내에 충분한 솔루션을 제공 할 수 있습니다 (최적 솔루션에서 2 ~ 3 % 정도).
선형 시간으로 2 MST 미만을 보장 할 수 있습니다. –
여행 세일즈맨은 폐쇄 회로가 아니라는 점에서 내가 필요한 것처럼 보입니다. 휴리스틱 솔루션을 살펴 봅니다. Tnx! – Jeroen
이것은 분명히 Travelling Salesman problem입니다. N=10의 경우 구체적으로 O(N!) 알고리즘을 사용하거나 Dynamic Programming을 사용하면 거래 공간을 기준으로 O(n^2 2^n)으로 줄일 수 있습니다.
그 외에도 NP 하드 문제이므로 일반적인주의 사항을 고려할 때 근사값이나 경험적 추론을 기대할 수 있습니다.
다른 언급했듯이, 이것은 TSP의 인스턴스입니다. Georgia Tech에서 개발 한 Concord은 현재 최첨단의 솔버입니다. 몇 초 안에 10,000 포인트 이상을 처리 할 수 있습니다. 또한 작업하기 쉬운 API도 있습니다.
가 난 사실, 이것이 당신이 찾고있는 무슨 생각 :
컴퓨터 과학에서, 때로는 로 알려진 플로이드 - 워셜 알고리즘합니다 (WFI 알고리즘 [명확한 설명은 필요로했다], Roy-Floyd 알고리즘 또는 Floyd의 알고리즘)은 가중치 그래프 (양 또는 음의 에지 가중치)에서 가장 짧은 경로를 찾는 그래프 분석 알고리즘입니다. 이 "경로 복원"섹션에서 자신
을 경로의 세부 사항을 반환하지 않습니다하지만 길이를 찾을 수 알고리즘의 단일 실행은 정점의 모든 쌍 사이의 최단 경로 ( 가중치 합산)이 "경로"를 저장하는 데 필요한 데이터 구조를 설명합니다 (실제로는 다음 노드를 저장하고 필요에 따라 필요한 경로를 간단히 재구성합니다).
실제로 OP는 FW를 언급하고 있으며 그가 요구하는 것이 분명하지 않습니다. – ziggystar
OP가 그것을 언급했을지 모르지만 그가 경로 재구성에 대해 알고 있다는 것을 의미하지는 않습니다. 이는 위의 주석이 추가 한 것입니다. –
단지 10 점이 있다면 3,628,800 개의 순열입니다. 그것은 굉장히 비싸지 않습니다. 이것들을 많이하기를 기대하십니까? –
10 포인트가 그 예였습니다. 우리는 몇 가지 점을 취할 수있는 스크립트를 작성해야합니다. – Jeroen