삽입 알고리즘이 모든 노드를 삽입 할 수 없습니다

Question

저는 파이썬에서 초보자입니다. 현재 경로에 새 노드를 삽입하여 경로가 짧아 지는지 여부를 확인하려고합니다. 그러나 내 코드가 잘 돌아 가지 않으면 내게 실수를 보여주십시오. 단계는 다음과 같습니다. 1. 임의 하위 집합 만들기 (예 : 0-2-0) 2. 방문하지 않은 노드를 임의로 가져 와서 현재 경로의 각 노드 쌍에서이 노드를 확인합니다. 노드가 더 짧은 요구 사항을 만족하면 현재 노드에 삽입합니다 (예 : 0-4-2-0). 3. 경로에 모든 노드가 삽입 될 때까지 계속하십시오. 그대로

import random 
distMatrix = [ 
     [100, 14, 20, 10, 35, 18, 5], 
     [6, 100, 7, 35, 17, 9, 24], 
     [8, 35, 100, 36, 27, 3, 15], 
     [21, 7, 12, 100, 7, 4, 26], 
     [33, 25, 6, 18, 100, 19, 11], 
     [6, 2, 22, 30, 9, 100, 8], 
     [24, 3, 12, 5,17, 16, 100], 
     ] 
def get_total_distance(route,d): 
    total = 0 
    for i in range (len(route)-1): 
     pre = route[i] 
     succ = route[i+1] 
     total += d[pre][succ] 
    return total 
def insertion(d): 
    numNodes = len(d) 
    notVisited = list(range(1, numNodes)) 
    first_random_node = random.choice(notVisited) 
    route = [0] 
    route.append(first_random_node) 
    notVisited.remove(first_random_node) 
    route.append(0) #create first subtour 
    print("1st",route) 
    location = 0 
    while len(notVisited) != 0: 
     for j in notVisited: 
      for i in range (len(route)-1): 
       pre = route[i] 
       succ = route[i+1] 
       check_route = d[pre][j] + d[j][succ] 
       current_distance = d[pre][succ] 
       if check_route <= current_distance: 
        print(j) 
        route.insert(i + 1, j) 
        notVisited.remove(j) 
        print("2nd", route) 
    return route 
solution = insertion(distMatrix) 
print("The solution for the route is:",solution) 
print("The total distance is:", get_total_distance(solution,distMatrix)) 

Answer 1

, 코드가 실행되지 않습니다 random : 로컬 기능을 사용하려는 패키지와 같은 이름 때문에 구문 오류가있다. 함수 random 안에 이름을 다시 정의했기 때문에 해당 이름의 패키지에 더 이상 액세스 할 수 없습니다. 그 문제가 해결되면

, 당신의 코드는 출력을 중단 :

1st [0, 5, 0] 
3 
2nd [0, 3, 5, 0] 
6 
2nd [0, 6, 3, 5, 0] 

이 조합 논리에 문제가 :

while 루프에서 유일한 출구가 모든 것을 제거하는 것입니다

while len(notVisited) != 0: 
    print("WHILE", len(notVisited)) 
    for j in notVisited: 
     .... 
      if check_route <= current_distance: 
       print(j) 
       route.insert(i + 1, j) 
       notVisited.remove(j) 
       print("2nd", route) 

notVisited에서. 논리적 인 보장은 일어나지 않습니다. 그렇지 않을 경우, 존재하지 않는 더 짧은 경로를 찾기 위해 무한 루프에 빠지게됩니다.