基于Python 3.6实现最近邻算法：国家公园最短路径规划问询

Hey there! Let's break this down step by step since you're new to programming—no need to feel overwhelmed, we'll take it one piece at a time.

你需要实现的是：导入包含国家公园名称及两两距离的CSV文件 → 让用户选择起始公园 → 用最近邻算法生成一条遍历所有公园的路径（每次跳去当前位置最近的未访问公园）→ 输出最终路径和总距离

Python是个绝佳的入门选择，语法简单，还有现成工具帮你处理CSV和数据逻辑。

2.1 先规范你的CSV格式 #

建议用「边列表」格式的CSV，每行存储一对公园的距离，比如：

公园1,公园2,距离
黄石国家公园,优胜美地国家公园,560
黄石国家公园,大峡谷国家公园,750
优胜美地国家公园,大峡谷国家公园,380

如果你的CSV是矩阵形式（行/列都是公园名，单元格是距离），解析逻辑会稍有不同，咱们先以最常见的边列表为例。

2.2 读取并解析CSV文件 #

用Python内置的csv模块读取文件，把数据转换成一个易操作的字典结构：每个公园作为键，对应的值是另一个字典，存储它到其他公园的距离。

import csv

def load_park_distances(csv_file):
    distance_dict = {}
    with open(csv_file, mode='r', encoding='utf-8') as file:
        reader = csv.reader(file)
        # 跳过表头（如果你的CSV有表头的话）
        next(reader)
        for row in reader:
            park1, park2, distance = row[0], row[1], float(row[2])
            # 双向存储距离（A到B和B到A的距离是一样的）
            if park1 not in distance_dict:
                distance_dict[park1] = {}
            distance_dict[park1][park2] = distance
            if park2 not in distance_dict:
                distance_dict[park2] = {}
            distance_dict[park2][park1] = distance
    return distance_dict

2.3 让用户选择起始公园 #

先列出所有可选公园，再做简单的输入校验，防止用户输入不存在的公园：

def get_starting_park(parks):
    print("可用的国家公园列表：")
    for idx, park in enumerate(parks, 1):
        print(f"{idx}. {park}")
    while True:
        choice = input("请输入你想作为起点的公园名称：").strip()
        if choice in parks:
            return choice
        else:
            print("抱歉，这个公园不在列表里，请重新输入！")

2.4 实现最近邻算法核心逻辑 #

这部分逻辑很直白：从起点出发，每次筛选出离当前位置最近的未访问公园，直到所有公园都被遍历：

def nearest_neighbor_route(start_park, distance_dict):
    visited = set()
    route = [start_park]
    visited.add(start_park)
    total_distance = 0.0
    current_park = start_park

    # 循环直到所有公园都被访问
    while len(visited) < len(distance_dict):
        min_distance = float('inf')
        next_park = None
        # 遍历所有未访问公园，找到最近的那个
        for park in distance_dict[current_park]:
            if park not in visited and distance_dict[current_park][park] < min_distance:
                min_distance = distance_dict[current_park][park]
                next_park = park
        # 更新路径、总距离和当前位置
        route.append(next_park)
        visited.add(next_park)
        total_distance += min_distance
        current_park = next_park

    return route, total_distance

2.5 整合所有功能并输出结果 #

把上面的函数拼起来，让程序完整运行：

def main():
    # 替换成你的CSV文件实际路径
    csv_path = "park_distances.csv"
    try:
        distance_dict = load_park_distances(csv_path)
    except FileNotFoundError:
        print(f"错误：找不到文件 {csv_path}，请检查路径是否正确！")
        return
    parks = list(distance_dict.keys())
    if not parks:
        print("错误：CSV文件里没有有效数据！")
        return
    start_park = get_starting_park(parks)
    route, total_dist = nearest_neighbor_route(start_park, distance_dict)
    # 输出最终结果
    print("\n你的遍历路径：")
    for i, park in enumerate(route, 1):
        print(f"{i}. {park}")
    print(f"\n总行程距离：{total_dist:.2f} 单位")

if __name__ == "__main__":
    main()

• CSV格式要严谨：确保每行的三个字段没有多余空格，距离是纯数字格式；如果你的CSV有表头，一定要用next(reader)跳过。
• 关于最近邻算法：这是个贪心算法，只能保证「每次选最近的」，但不一定能得到全局最短的遍历路径（也就是旅行商问题的最优解）。不过它简单易实现，完全符合你的需求。
• 可扩展的错误处理：上面的代码加了基础的错误处理（比如文件找不到），你还可以继续完善，比如处理CSV里的无效数据（比如距离不是数字）。

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