2. Dijkstra算法与A*算法对比

任务定义

在20×15的栅格地图上（含障碍物），分别实现Dijkstra算法与A*算法（欧氏距离启发函数），从起点(1,1)规划到终点(18,13)。比较两种算法在相同地图条件下的扩展节点数与运行时间，并输出各自的最优路径长度。

地图与参数定义

# map.py
import numpy as np

# 20列 x 15行，0=可通行，1=障碍
grid = np.zeros((15, 20), dtype=int)

# 设置障碍物（矩形区域）
grid[3:6, 5:8] = 1
grid[8:11, 12:15] = 1
grid[5:9, 10:12] = 1
grid[11:14, 3:6] = 1

START = (1, 1)   # (row, col)
GOAL = (13, 18)

算法实现

# pathfinding.py
import heapq
import math
import time
from map import grid, START, GOAL

def neighbors(pos, grid):
    """返回4邻域可通行邻居"""
    rows, cols = grid.shape
    r, c = pos
    result = []
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r+dr, c+dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
            result.append((nr, nc))
    return result

def heuristic(a, b):
    """欧氏距离启发函数"""
    return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

def dijkstra(grid, start, goal):
    """Dijkstra算法，返回(路径, 扩展节点数)"""
    rows, cols = grid.shape
    dist = {start: 0}
    prev = {}
    pq = [(0, start)]
    expanded = 0
    
    while pq:
        d, current = heapq.heappop(pq)
        if current == goal:
            break
        if d > dist.get(current, float('inf')):
            continue
        expanded += 1
        
        for nb in neighbors(current, grid):
            nd = d + 1  # 单位代价
            if nd < dist.get(nb, float('inf')):
                dist[nb] = nd
                prev[nb] = current
                heapq.heappush(pq, (nd, nb))
    
    # 回溯路径
    if goal not in prev and goal != start:
        return None, expanded
    path = []
    node = goal
    while node != start:
        path.append(node)
        node = prev[node]
    path.append(start)
    path.reverse()
    return path, expanded

def a_star(grid, start, goal):
    """A*算法，返回(路径, 扩展节点数)"""
    rows, cols = grid.shape
    open_set = {start}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}
    prev = {}
    expanded = 0
    
    while open_set:
        # 取f值最小的节点
        current = min(open_set, key=lambda x: f_score.get(x, float('inf')))
        if current == goal:
            break
        open_set.remove(current)
        expanded += 1
        
        for nb in neighbors(current, grid):
            tentative_g = g_score[current] + 1
            if tentative_g < g_score.get(nb, float('inf')):
                prev[nb] = current
                g_score[nb] = tentative_g
                f_score[nb] = tentative_g + heuristic(nb, goal)
                open_set.add(nb)
    
    if goal not in prev and goal != start:
        return None, expanded
    path = []
    node = goal
    while node != start:
        path.append(node)
        node = prev[node]
    path.append(start)
    path.reverse()
    return path, expanded

def run_comparison():
    """运行两种算法并计时"""
    # Dijkstra
    t0 = time.perf_counter()
    dij_path, dij_exp = dijkstra(grid, START, GOAL)
    dij_time = time.perf_counter() - t0
    
    # A*
    t0 = time.perf_counter()
    astar_path, astar_exp = a_star(grid, START, GOAL)
    astar_time = time.perf_counter() - t0
    
    return {
        'dijkstra': {
            'path': dij_path,
            'expanded': dij_exp,
            'time': dij_time,
            'path_len': len(dij_path)-1 if dij_path else None
        },
        'a_star': {
            'path': astar_path,
            'expanded': astar_exp,
            'time': astar_time,
            'path_len': len(astar_path)-1 if astar_path else None
        }
    }

主程序与验证

# main.py
from pathfinding import run_comparison
from map import grid, START, GOAL

if __name__ == '__main__':
    result = run_comparison()
    
    print(f"起点: {START}, 终点: {GOAL}")
    print(f"Dijkstra: 路径长度={result['dijkstra']['path_len']}, "
          f"扩展节点数={result['dijkstra']['expanded']}, "
          f"耗时={result['dijkstra']['time']*1000:.3f}ms")
    print(f"A*:      路径长度={result['a_star']['path_len']}, "
          f"扩展节点数={result['a_star']['expanded']}, "
          f"耗时={result['a_star']['time']*1000:.3f}ms")
    
    # 验证路径可行性
    dij_path = result['dijkstra']['path']
    astar_path = result['a_star']['path']
    
    def verify_path(path):
        if not path:
            return False
        for i in range(len(path)-1):
            r1, c1 = path[i]
            r2, c2 = path[i+1]
            if abs(r1-r2) + abs(c1-c2) != 1:  # 必须相邻
                return False
            if grid[path[i+1]] == 1:  # 不能穿障碍
                return False
        return path[0] == START and path[-1] == GOAL
    
    print(f"\nDijkstra路径有效: {verify_path(dij_path)}")
    print(f"A*路径有效: {verify_path(astar_path)}")

运行方式

python main.py

预期输出与判定标准

两种算法均能找到从(1,1)到(13,18)的最短路径，路径长度相同（因为A*使用可采纳启发函数）。判定标准：

• 路径正确性：程序输出“路径有效: True”，且两种算法路径长度一致
• 扩展节点数：A*的扩展节点数应少于Dijkstra（启发函数引导搜索方向）
• 运行时间：A*通常快于Dijkstra，但受地图规模影响，以实际输出为准

代码说明

本实现中Dijkstra使用优先队列（堆）保证每次取出距离最小的节点，A*使用相同的堆结构但以g+h作为排序键。两者均采用4邻域移动且单位代价为1，因此Dijkstra与A*找到的路径长度必然相同。A*的启发函数采用欧氏距离，满足可采纳性与一致性，保证最优性。扩展节点数通过计数器在每次从堆中弹出节点时累加统计，运行时间使用time.perf_counter()测量，单位为毫秒。