You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
61 lines
1.8 KiB
61 lines
1.8 KiB
import sys
|
|
|
|
import numpy as np
|
|
|
|
|
|
def tsp_nearest_neighbor1(distances):
|
|
num_cities = len(distances)
|
|
visited = [False] * num_cities
|
|
path = [0] # 起始城市为0
|
|
visited[0] = True
|
|
|
|
for _ in range(num_cities - 1):
|
|
curr_city = path[-1]
|
|
min_distance = sys.maxsize
|
|
nearest_city = None
|
|
|
|
for city in range(num_cities):
|
|
if not visited[city] and distances[curr_city][city] < min_distance and distances[curr_city][city] != 0:
|
|
min_distance = distances[curr_city][city]
|
|
nearest_city = city
|
|
|
|
if nearest_city is not None:
|
|
path.append(nearest_city)
|
|
visited[nearest_city] = True
|
|
|
|
path.append(0) # 回到起始城市形成闭合路径
|
|
return path
|
|
def tsp_nearest_neighbor(distances):
|
|
num_cities = len(distances)
|
|
visited = [False] * num_cities
|
|
path = [0] # 起始城市为0
|
|
visited[0] = True
|
|
|
|
for _ in range(num_cities - 1):
|
|
curr_city = path[-1]
|
|
min_distance = sys.maxsize
|
|
nearest_city = None
|
|
|
|
for city in range(num_cities):
|
|
if not visited[city] and distances[curr_city][city] < min_distance and distances[curr_city][city] != 0:
|
|
min_distance = distances[curr_city][city]
|
|
nearest_city = city
|
|
|
|
if nearest_city is not None:
|
|
path.append(nearest_city)
|
|
visited[nearest_city] = True
|
|
|
|
path.append(0) # 回到起始城市形成闭合路径
|
|
return path
|
|
# 示例用法
|
|
distances = np.array([
|
|
[np.inf, 50, 99, np.inf, 64, np.inf],
|
|
[50, np.inf, 12, 45, 74, 13],
|
|
[99, 12, np.inf, 25, np.inf, 61],
|
|
[np.inf, 45, 25, np.inf, 45, 47],
|
|
[64, 74, np.inf, 45, np.inf, np.inf],
|
|
[np.inf, 13, 61, 47, np.inf, np.inf]
|
|
])
|
|
|
|
path = tsp_nearest_neighbor1(distances)
|
|
print(path) |