알고리즘 또는 경로 문제에 대한 접근, n <= 12에 대한 n 포인트가있는 최단 경로

Question

두 번째 평면에 n 개의 점이 있고 n은 < = 12이며 모든 점을 포함하여 사용 가능한 최단 경로의 거리가 필요합니다. 그들 중 하나에,하지만 폐쇄 회로를하지

나는 floyd - 마샬, 여행 세일즈맨 문제 및 기타 알고리즘을 시도하지 않고 성공하지 못했습니다.

문제는 내가 그 로라 근사치 정도를 필요로 생각하지 않도록 선생님 쉽게 생각하지만, 내가 가장 좋은 방법은이 문제를 해결하기 위해 무슨 잘 모릅니다 만, 어쩌면

for i = 0 to n 
    for j = 0 to n 
    if path_distance(i,j) < mininum 
     set minimum 

같은 일부 동적 알고리즘과 뭔가

어떤 도움이 필요합니까?

Answer 1

12 포인트 만 알고 모든 노드를 방문하는 최단 경로를 정확히 한 번 찾으려면 노드의 모든 가능한 순열을 시도하고 길이를 계산하여 솔루션을 무차별히 강요 할 수 있습니다. 그 순열을 따라가는 길. 이것은 잘 확장되지 않지만, 노드의 수에 대한 고정 된 상한선이 있다면 합리적이어야합니다.

Answer 2

n <= 12 인 경우에만 무작위 알고리즘의 향상된 버전 인 the Branch and Bound algorithm을 권하고 싶습니다. 이러한 종류의 문제를 분해 할 때

재귀가 매우 유용하다 :이 숙제이기 때문에

Answer 3

나는 단지 힌트를 제공 할 수 있습니다.

지금까지의 경로 목록, 지금까지의 최고/최소 거리 및 방문하지 않은 노드의 목록을 취하는 함수를 작성할 수 있습니다. 아직 방문하지 않은 각 노드에 대해 지금까지 경로에 추가하려고 시도했으며 그 경로가 아직까지 최상의/최소 거리보다 짧으면 새로운 경로와 방문하지 않은 노드의 목록을 호출합니다.