欲張りアルゴリズムTSP問題を解く(python)

ここでは貪欲アルゴリズムを用いてTSP問題のpythonバージョンを解く

# dist      ，start_index      
def tsp_quick(dist: list, start_index: int):
    sum_distance, seq_result, n = 0, [start_index, ], len(dist)
    for path_index in range(n - 1):
        distance_list = dist[start_index]
        min_dis = max(distance_list)
        for index, distance in enumerate(distance_list):
            if (index not in seq_result) and (distance < min_dis):
                min_dis = distance
                start_index = index
        sum_distance += min_dis
        seq_result.append(start_index)
    return sum_distance,seq_result

#    ：
dist = [
    [2, 5, 6, 7, 3],
    [5, 9, 3, 4, 5],
    [6, 3, 7, 2, 6],
    [7, 4, 2, 5, 2],
    [3, 5, 6, 2, 9],
]
sum_distance,seq_list = tsp_quick2(dist, 3) # dist     ，3      3  
#  sum_distance       
#     [3,2,1,0,4]    3 -> 2 -> 1 -> 0 -> 4