【“荔”刻出发 | 启发式A*算法原理&实现】

原创

九年义务漏网鲨鱼

发布于 2025-07-01 09:04:11

7240

一、任务背景

在蓝桥杯竞赛、acwing等算法竞赛中，路径规划问题常常出现，在大学阶段我们常常采用Dijkstra、Floyd算法实现路径最小问题。作为圣人钦点的“荔枝使”，我需要从“深圳”将荔枝运往“西安”，并且将路径和总代价告知圣人。目前圣人已经将城市地图以及各个城市的通行时间告诉了我，如下所示：

city_graph = {
    '深圳': {'广州': 1.5, '东莞': 1.0},
    '广州': {'深圳': 1.5, '韶关': 2.5, '长沙': 5.5},
    '东莞': {'深圳': 1.0, '惠州': 1.2},
    '惠州': {'东莞': 1.2, '武汉': 8.0},
    '韶关': {'广州': 2.5, '长沙': 4.0},
    '长沙': {'韶关': 4.0, '武汉': 3.0, '郑州': 8.0},
    '武汉': {'惠州': 8.0, '长沙': 3.0, '郑州': 4.5, '西安': 10.0},
    '郑州': {'长沙': 8.0, '武汉': 4.5, '洛阳': 2.0},
    '洛阳': {'郑州': 2.0, '西安': 5.0},
    '西安': {'武汉': 10.0, '洛阳': 5.0}
}

当我正想用大学算法题常用的Dijkstra、Floyd算法解决这个”简单“的问题时，突然发现，这些算法仅仅是适用于静态的路径规划算法,而在现实交通系统中，路径状态是动态变化的。当存在路径突发情况时，例如断路、临时交通管制、油价波动导致成本变化等都会导致算法需要重构，导致一定的时间延迟，都无法满足系统实时性的需求。

场景	Dijkstra处理方式	Floyd处理方式
突发断路	需全图重新计算	必须重构整个距离矩阵
临时交通管制	无法增量更新	需全量重算
油价波动导致成本变化	需重新执行完整算法	重新构建成本矩阵

为了实现能够应对不同突发情况的场景的算法，我想到了采用启发式算法A-star算法，它结合了Dijkstra算法的完备性和贪心算法的效率。A-star算法可以通过使用启发式函数来估计从当前节点到目标节点的成本，从而优先探索最合适的路径。而当A-star算法遇到以上情况时，只需要局部规划、动态调整启发函数，或者仅仅更新列表权重即可实现。

二、A-star算法原理

A-star算法是综合考虑了到当前节点的实际代价g(n) 以及估算代价h(n) （与贪心算法不同，可以引导搜索方向）：f(n) = g(n)+h(n) ，当不考虑估算代价时，就会退化为Dijkstra算法。因此，如何设计一个估算代价成为提高算法效率的关键因素，一个好的估算代价可以在第一次搜索中就找到最优解。

🔴 hh(n)=0：退化为Dijkstra算法；（完全一致）

🔴 hh(n) > >g(n)：A-star算法趋近于贪心算法（可能错过最优解）；

A-star实现原理：

🟢 维护了一个开放列表（优先队列实现）和关闭列表；

🟢 在每次遍历过程中，将可能的ff(n)存入开放列表中，已经经过的节点存进关闭列表【与Dijkstra算法不同的只有将ff(n)改为gg(n)】；

🟢 当从开放列表中找到结束节点时，算法终止；

三、A-star算法实现

① 只考虑花费时间，不考虑其他代价时，即h(n)=0, f(n)=g(n)

迭代过程：

初始化开放列表: {深圳(g=0, f=0)}，关闭列表：{}；
step1：此时深圳只能连接到广州和东莞，到达广州和东莞的时间代价分别是1.5和1，更新开放列表：广州(g=1.5, f=1.5), 东莞(g=1.0, f=1.0)}，关闭列表：{深圳}；
step2：在开放列表中，f值最小是到达东莞，因此模拟到达东莞，在东莞还能到达惠州，更新开放列表: {广州(g=1.5, f=1.5), 惠州(g=2.2, f=2.2)}，此时到达东莞，东莞进入关闭列表中，更新关闭列表: {深圳, 东莞}
step3：在开放列表中，f值最小是广州1.5，因此模拟到达广州，在广州还能到达韶关、长沙，更新开放列表: {惠州(g=2.2, f=2.2), 韶关(g=4.0, f=4.0), 长沙(g=7.0, f=7.0)}，将广州降入关闭列表中，关闭列表: {深圳, 东莞, 广州}
step4：在开放列表中，f值最小是惠州2.2，因此模拟到达惠州，在惠州还能到达武汉，更新开放列表: {韶关(g=4.0, f=4.0), 长沙(g=7.0, f=7.0), 武汉(g=10.2, f=10.2)} ，将惠州降入关闭列表中，更新关闭列表: {深圳, 东莞, 广州, 惠州}
以此类推，直到将西安加入到关闭列表中

算法实现

import heapq

def a_star_search(graph, start, goal):
    # 所有启发函数设为0，退化为 Dijkstra，但保留 A* 框架
    heuristic = {city: 0 for city in graph}
    
    # open list，优先队列，元素格式：(f(n), g(n), 路径)
    open_list = [(0 + heuristic[start], 0, [start])]
    visited = set()

    while open_list:
        f_score, current_cost, path = heapq.heappop(open_list)
        current_node = path[-1]

        if current_node == goal:
            return path, current_cost

        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, travel_time in graph[current_node].items():
            if neighbor not in visited:
                g = current_cost + travel_time
                h = heuristic.get(neighbor, 0)
                heapq.heappush(open_list, (g + h, g, path + [neighbor]))

    return None, float('inf')

city_graph = {
    '深圳': {'广州': 1.5, '东莞': 1.0},
    '广州': {'深圳': 1.5, '韶关': 2.5, '长沙': 5.5},
    '东莞': {'深圳': 1.0, '惠州': 1.2},
    '惠州': {'东莞': 1.2, '武汉': 8.0},
    '韶关': {'广州': 2.5, '长沙': 4.0},
    '长沙': {'韶关': 4.0, '武汉': 3.0, '郑州': 8.0},
    '武汉': {'惠州': 8.0, '长沙': 3.0, '郑州': 4.5, '西安': 10.0},
    '郑州': {'长沙': 8.0, '武汉': 4.5, '洛阳': 2.0},
    '洛阳': {'郑州': 2.0, '西安': 5.0},
    '西安': {'武汉': 10.0, '洛阳': 5.0}
}

start_city = '深圳'
end_city = '西安'
path, total_cost = a_star_search(city_graph, start_city, end_city)

if path:
    print("最优路径:", " -> ".join(path))
    print("总代价（运输时间）:", round(total_cost, 2), "小时")
else:
    print("未找到从 {} 到 {} 的路径。".format(start_city, end_city))
    
# 最优路径: 深圳 -> 东莞 -> 惠州 -> 武汉 -> 西安
# 总代价（运输时间）: 20.0 小时

② 考虑路程花费，即h(n)=cost, f(n)=g(n)+h(n)

只是在源代码的基础上修改以下h（n）即可

import heapq

def a_star_multi_objective(graph, start, goal):
    heuristic = {city: 0 for city in graph}  # 启发函数设为0
    open_list = [(0, 0, 0, [start])] 
    visited = set()
    while open_list:
        f_score, total_time, total_cost, path = heapq.heappop(open_list)
        current_node = path[-1]
        if current_node == goal:
            return path, total_time, total_cost
        if current_node in visited:
            continue
        visited.add(current_node)
        for neighbor, info in graph[current_node].items():
            if neighbor not in visited:
                time = info['time']
                cost = info['cost']
                g_time = total_time + time
                g_cost = total_cost + cost
                g = g_time + g_cost
                f = g + heuristic.get(neighbor, 0)
                heapq.heappush(open_list, (f, g_time, g_cost, path + [neighbor]))
    return None, float('inf'), float('inf')
city_graph = {
    '深圳': {'广州': {'time': 1.5, 'cost': 40}, '东莞': {'time': 1.0, 'cost': 30}},
    '广州': {'深圳': {'time': 1.5, 'cost': 40}, '韶关': {'time': 2.5, 'cost': 60}, '长沙': {'time': 5.5, 'cost': 120}},
    '东莞': {'深圳': {'time': 1.0, 'cost': 30}, '惠州': {'time': 1.2, 'cost': 35}},
    '惠州': {'东莞': {'time': 1.2, 'cost': 35}, '武汉': {'time': 8.0, 'cost': 180}},
    '韶关': {'广州': {'time': 2.5, 'cost': 60}, '长沙': {'time': 4.0, 'cost': 90}},
    '长沙': {'韶关': {'time': 4.0, 'cost': 90}, '武汉': {'time': 3.0, 'cost': 70}, '郑州': {'time': 8.0, 'cost': 160}},
    '武汉': {'惠州': {'time': 8.0, 'cost': 180}, '长沙': {'time': 3.0, 'cost': 70},
             '郑州': {'time': 4.5, 'cost': 100}, '西安': {'time': 10.0, 'cost': 200}},
    '郑州': {'长沙': {'time': 8.0, 'cost': 160}, '武汉': {'time': 4.5, 'cost': 100}, '洛阳': {'time': 2.0, 'cost': 50}},
    '洛阳': {'郑州': {'time': 2.0, 'cost': 50}, '西安': {'time': 5.0, 'cost': 100}},
    '西安': {'武汉': {'time': 10.0, 'cost': 200}, '洛阳': {'time': 5.0, 'cost': 100}}
}
start_city = '深圳'
end_city = '西安'
path, total_time, total_cost = a_star_multi_objective(city_graph, start_city, end_city)

if path:
    print("最优路径:", " -> ".join(path))
    print("总时间:", round(total_time, 2), "小时")
    print("总费用:", round(total_cost, 2), "元")
    print("综合总代价（加权）:", round(alpha * total_time + (1 - alpha) * total_cost, 2))
else:
    print("未找到路径")
# 最优路径: 深圳 -> 广州 -> 长沙 -> 武汉 -> 西安
# 总时间: 20.0 小时
# 总费用: 430 元

除此之外，还可以在对应的代价函数和启发函数上加入权重因子\alpha ，修改代码如下所示：

def a_star_multi_objective(graph, start, goal, alpha=0.7):
    heuristic = {city: 0 for city in graph}
    open_list = [(0, 0, 0, [start])]
    visited = set()
    while open_list:
        f_score, total_time, total_cost, path = heapq.heappop(open_list)
        current_node = path[-1]
        if current_node == goal:
            return path, total_time, total_cost
        if current_node in visited:
            continue
        visited.add(current_node)
        for neighbor, info in graph.get(current_node, {}).items():
            if neighbor not in visited:
                time = info['time']
                cost = info['cost']
                g_time = total_time + time
                g_cost = total_cost + cost
                g = alpha * g_time + (1 - alpha) * g_cost
                f = g + heuristic.get(neighbor, 0)
                heapq.heappush(open_list, (f, g_time, g_cost, path + [neighbor]))
    return None, float('inf'), float('inf')

③ 断路模拟

在实际情况中，道路的情况并不是静态的，这也是A-star算法的优点，可以实时的改变自己的启发函数适应突法情况，为了模拟突发情况，加入了一个断路函数：

def simulate_road_closure(graph, from_city, to_city):
    new_graph = copy.deepcopy(graph)
    if to_city in new_graph.get(from_city, {}):
        del new_graph[from_city][to_city]
    if from_city in new_graph.get(to_city, {}):
        del new_graph[to_city][from_city]
    return new_graph

# 模拟断路（如 长沙 到 武汉）
closed_from = '长沙'
closed_to = '武汉'
print(f"\n⚠️ 模拟断路: {closed_from} 与 {closed_to} 之间的道路断开...\n")

# ✅ 可达！最优路径: 深圳 -> 东莞 -> 惠州 -> 武汉 -> 西安
# 总时间: 20.2 小时
# 总费用: 445 元