Python 中车辆路径问题的贪心解法

from math import sqrt

# 节点的距离缓存
dis_cache = {}

def calc_dis(node1, node2):
    """计算两个节点之间的距离"""
    if node1 == node2:
        return 0
    key = tuple(sorted([node1, node2]))
    if key in dis_cache:
        return dis_cache[key]
    x1, y1 = node1
    x2, y2 = node2
    dis = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2))
    dis_cache[key] = dis
    return dis

def shortest_path(start, end, nodes):
    """使用贪心算法求解车辆路径问题"""
    curr = start   # 当前节点
    path = [curr]  # 路径列表
    while curr != end:
        # 计算当前节点到终点的距离
        dis_to_end = calc_dis(curr, end)
        # 查找当前节点的相邻节点中，距离终点最短的节点
        next_node, next_node_dis = None, float('inf')
        for node in nodes:
            if node in path:
                continue
            dis = calc_dis(curr, node)
            if dis + calc_dis(node, end) < next_node_dis:
                next_node, next_node_dis = node, dis + calc_dis(node, end)
        # 如果找不到下一个节点，则退出循环
        if next_node is None:
            break
        # 将下一个节点加入路径列表，并更新当前节点
        path.append(next_node)
        curr = next_node
    # 返回最短路径
    return path

# 测试
start = (0, 0)
end = (10, 10)
nodes = [(1, 1), (2, 3), (4, 5), (6, 7), (8, 9), (9, 8)]
path = shortest_path(start, end, nodes)
print(path)