여행 판매원 문제에 대해 알고 있지만 다른 요구 사항/설명에 더 적합한 알고리즘/문제가 있습니까? 나는 수학적 묘사의 도움으로 나의 문제를 기술 할 필요가있다.시작 지점이나 끝 지점을 지정하지 않고 그래프의 모든 꼭지점 간의 최단 경로를 찾습니다.
저는 알려진 시작점과 끝점을 가진 일련의 노드가 있습니다. 그래서 나는 그 둘 사이의 모든 세 점을 방문하는 가장 짧은 길을 계산할 필요가 있습니다. Dijkstra와 유사한 알고리즘은 두 점 사이의 최단 경로를 찾으므로 여기서는 모든 점을 방문하지 않을 것입니다. 아니면 가장 짧은 길을 찾고 두 점 사이의 모든 점을 방문하는 알고리즘이 있습니까?
개미 식민지 최적화 알고리즘을 사용하여 얻을 수 있습니다. Ant colony optimization algorithms을 참조하십시오.
문제의 일반적인 경우의 복잡성은 최소한 여행 판매원 문제의 복잡성만큼 높습니다. 두 종점이 기본적으로 동일한 위치에있는 경우 상상해보십시오. 그런 다음 문제는 여행 판매원과 동일하게됩니다.
그래도 그래프에서 5 점 이상을 기대하지 않는다면 멋진 알고리즘을 고민해야합니까? 최상의 솔루션을 찾기 위해 철저한 검색을 수행 할 수 있습니다. 유일한 결정은 중간에있는 3 점을 방문하는 순서이므로 3 점을 테스트하면됩니다! = 6 개의 다른 경로. 내가 오해하고 모든 노드를 방문하는 가장 짧은 열린 경로를 원한다고하더라도, 그것은 여전히 5가 될 것입니다! = 테스트 할 120 개의 다른 경로 (거리가 양방향으로 동일하면 60).
내 문제는 50 점 이상입니다. 그렇다면 그것을 해결하는 방법 – user1293861
다르게. 귀하의 질문에 명시 적으로 "나는 알려진 시작점과 끝 점이 5 점이 있습니다." 나는 더 큰 문제를 효율적으로 해결하는 방법을 모르지만, Visruth의 대답은 좋은 리더처럼 보입니다. – Medo42