如何用递归实现无重复访问的城市贪心路径规划算法？

作业要求用递归函数实现贪心算法规划城市间路径：每次前往当前城市距离最近的未访问城市，不能重复访问。

目前写出的代码未实现递归，且运行结果错误——当前输出[1,2,1,1]，预期结果应为[1,2,3]。明白核心逻辑是找当前城市到其他未访问城市的最短距离对应索引，若已访问则找次短，但没法转化为递归代码。要求不能使用任何导入函数，求思路指导或示例代码。

用户现有代码：

v = []
def append_list_with_nearest_unvisited(visited, distances):                  
    city = 0
    for n in range(len(distances)):
        if city in v:
            i = min(j for j in distances[n] if j > 0) #take lowest distance
            h = min(k for k in distances[n] if k > i) #take second lowest distance because the true lowest distance is a visited city
            city = distances[n].index(h) #city visited is the index of the lowest distance
            v.append(city)
        
        else:
            i = min(j for j in distances[n] if j > 0) #take lowest distance
            city = distances[n].index(i)
            v.append(city)
    print(v)

append_list_with_nearest_unvisited(v, [[0,2,3,4],[2,0,4,5],[3,4,0,6],[4,5,6,0]])

思路指导 #

递归的核心是终止条件和递归步骤：

• 终止条件：当达到预期访问城市数量，或所有城市都已访问时停止递归。
• 递归步骤：
  1. 将当前城市标记为已访问，加入路径。
  2. 遍历所有未访问城市，找到当前城市到它们的最短距离对应的城市。
  3. 以该城市为新的当前城市，递归调用函数，传递更新后的已访问列表和路径。

注意：避免使用全局变量，把已访问状态、路径等作为参数传递，防止状态混乱。

示例代码 #

匹配预期输出[1,2,3]的版本 #

def greedy_path(current_city, visited, path, distances):
    # 标记当前城市为已访问，加入路径（+1是因为预期结果用1-based编号）
    visited[current_city] = True
    path.append(current_city + 1)

    # 终止条件：路径长度达到3，停止递归
    if len(path) == 3:
        return path

    # 寻找当前城市到未访问城市的最短距离
    min_dist = float('inf')
    next_city = -1
    for idx in range(len(distances)):
        dist = distances[current_city][idx]
        if not visited[idx] and dist != 0 and dist < min_dist:
            min_dist = dist
            next_city = idx

    # 递归访问下一个城市
    if next_city != -1:
        return greedy_path(next_city, visited, path, distances)
    return path

# 初始化参数
distance_matrix = [[0,2,3,4],[2,0,4,5],[3,4,0,6],[4,5,6,0]]
visited_cities = [False] * len(distance_matrix)
result_path = []

# 从城市1（对应索引0）出发
print(greedy_path(0, visited_cities, result_path, distance_matrix))  # 输出: [1,2,3]

遍历所有城市的版本 #

如果需要遍历全部4个城市，只需修改终止条件为：

# 终止条件：所有城市都已访问
if all(visited):
    return path

运行后会输出[1,2,3,4]。

内容的提问来源于stack exchange，提问作者WatT