挿入アルゴリズムですべてのノードを挿入できない

Question

私はPythonで初心者です。現在のルートに新しいノードを挿入してルートが短くなっているかどうかをチェックします。しかし、私のコードはうまく動かないので、間違いを教えてください。手順は次のとおりです。 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 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) 

whileループからあなたの唯一の出口はすべてを削除することですnotVisitedから。それが起こらないという論理的な保証はありません。存在しない場合、あなたは存在しない短いルートを見つけようと無限ループに陥っています。