# -*- coding: utf-8 -*-
# Time : 2023/10/31 10:22
# Author : lirunsheng
# User : l'r's
# Software: PyCharm
# File : greedy.py

import numpy as np

def tsp_greedy(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 = float('inf')
        next_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]
                next_city = city

        if next_city is not None:
            path.append(next_city)
            visited[next_city] = True
    if distances[path[-1]][0] != np.inf:
        path.append(0)  # 回到起始城市形成闭合路径
    return path

distances = np.array([
    [np.inf, 80, 99, np.inf, 64, np.inf],
    [80, 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_greedy(distances)
if len(path) == 6:
    print('贪心算法路径：')
    print(path)
else:
    print('未找到！')