tsp/main.py

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)