算法核心要素

• 评估函数 f(n)：决定节点的搜索优先级
• 实际代价 g(n)：从起点到当前节点的实际路径代价
• 启发函数 h(n)：估计从当前节点到目标的代价
• 开放列表（Open List）：待探索的节点集合
• 关闭列表（Closed List）：已探索的节点集合

算法优势

• 结合了 Dijkstra 算法的完备性和最佳优先搜索的效率
• 通过启发函数可以大幅减少搜索空间
• 保证找到最优解（当启发函数满足条件时）
• 适用于大规模路径规划问题

常用启发函数

• 曼哈顿距离：|x1 - x2| + |y1 - y2|，适用于四方向移动
• 欧几里得距离：√((x1-x2)² + (y1-y2)²)，适用于任意方向移动
• 对角线距离：适用于八方向移动的网格地图

算法步骤

1. 将起点加入开放列表
2. 重复以下步骤：
   • 找出开放列表中f(n)最小的节点n
   • 把节点n移到关闭列表
   • 对于节点n的每个相邻节点m：
     • 如果m在关闭列表中，跳过
     • 如果m不在开放列表中，加入开放列表
     • 如果m已在开放列表中，更新其f值
3. 直到找到目标节点或开放列表为空

算法核心要素

• 队列（Queue）：存储待访问的节点
• 访问标记（Visited Set）：记录已访问的节点
• 层次遍历：按照节点到起点的距离递增顺序访问
• 路径记录：通过父节点指针记录最短路径

算法优势

• 保证找到最短路径（边数相等的情况下）
• 完整性：一定能找到所有可能的解
• 时间复杂度：O(V + E)，其中 V 为顶点数，E 为边数
• 特别适合解决最小步数类问题

算法步骤

1. 初始化：
   • 创建空队列，将起点加入队列
   • 创建访问集合，标记起点为已访问
   • 创建路径记录字典，记录每个节点的父节点
2. 主循环：当队列不为空时
   • 取出队首节点作为当前节点
   • 如果当前节点是目标节点，返回路径
   • 遍历当前节点的所有相邻节点：
     • 如果相邻节点未访问，将其加入队列
     • 标记相邻节点为已访问
     • 记录相邻节点的父节点为当前节点
3. 如果队列为空仍未找到目标，返回失败

代码实现要点

from collections import deque

def bfs(graph, start, goal):
    # 初始化队列和访问集合
    queue = deque([start])
    visited = {start}
    parent = {start: None}
    
    while queue:
        current = queue.popleft()  # 取出队首节点
        if current == goal:
            return reconstruct_path(parent, goal)
            
        # 遍历相邻节点
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                parent[neighbor] = current
                
    return None  # 未找到路径

def reconstruct_path(parent, goal):
    path = []
    current = goal
    while current is not None:
        path.append(current)
        current = parent[current]
    return path[::-1]  # 反转路径

注意事项

• 需要额外的空间存储访问标记和队列
• 在处理大规模图时，内存消耗可能较大
• 不适合解决带权图的最短路径问题
• 对于递归深度大的问题，BFS通常比DFS更安全

算法核心要素

• 递归/栈：用于实现回溯功能
• 访问标记：记录已访问的节点
• 回溯机制：返回到上一个决策点
• 深度探索：优先访问未探索的分支

算法优势

• 空间复杂度较低（相比BFS）
• 实现简单，尤其是递归版本
• 适合搜索深层的解决方案
• 适合解决连通性和拓扑排序问题

算法实现方式

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')  # 访问当前节点
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
            

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            stack.extend(n for n in graph[node] if n not in visited)
            

算法步骤

1. 选择起始节点，标记为已访问
2. 对于当前节点的每个未访问的邻接节点：
   • 将当前节点入栈
   • 递归访问邻接节点
   • 如果无法继续前进，回溯到栈顶节点
3. 重复步骤2，直到访问完所有可达节点

复杂度分析

• 时间复杂度：O(V + E)，其中V为顶点数，E为边数
• 空间复杂度：
  • 递归版本：O(H)，其中H为图的深度（递归调用栈的深度）
  • 迭代版本：O(V)，需要visited集合和stack栈

注意事项

• 递归实现可能导致栈溢出
• 不保证找到最短路径
• 需要注意处理环的情况
• 遍历顺序依赖于图的表示方式

算法核心要素

• 距离数组（dist[]）：记录从起点到各节点的当前最短距离
• 访问集合（visited）：标记已确定最短路径的节点
• 优先队列（PriorityQueue）：按距离排序的待处理节点队列
• 前驱数组（parent[]）：记录最短路径中每个节点的前驱节点

算法步骤

1. 初始化：
   • 将所有节点的距离设为无穷大
   • 将起点距离设为0
   • 创建空的已访问集合
   • 将起点加入优先队列
2. 主循环：当优先队列非空时
   • 取出队列中距离最小的节点u
   • 将节点u标记为已访问
   • 对于u的每个未访问的邻接节点v：
     • 计算经过u到达v的距离
     • 如果新距离小于v的当前距离，则更新v的距离
     • 更新v的前驱节点为u
3. 算法终止条件：
   • 找到目标节点
   • 或优先队列为空（访问完所有可达节点）

实现代码

import heapq
from typing import Dict, List, Set, Tuple

def dijkstra(graph: Dict[int, Dict[int, int]], start: int, end: int) -> Tuple[List[int], int]:
    """
    使用Dijkstra算法计算最短路径
    
    Args:
        graph: 邻接表表示的加权图
        start: 起点
        end: 终点
    
    Returns:
        路径列表和总距离的元组
    """
    # 初始化距离数组和前驱数组
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}
    
    # 初始化优先队列和已访问集合
    pq = [(0, start)]
    visited = set()
    
    while pq:
        # 取出当前最短距离的节点
        current_distance, current_node = heapq.heappop(pq)
        
        # 如果节点已访问，跳过
        if current_node in visited:
            continue
            
        # 标记节点为已访问
        visited.add(current_node)
        
        # 如果到达终点，构建并返回路径
        if current_node == end:
            path = []
            while current_node:
                path.append(current_node)
                current_node = predecessors[current_node]
            return path[::-1], current_distance
            
        # 检查所有邻接节点
        for neighbor, weight in graph[current_node].items():
            if neighbor in visited:
                continue
                
            # 计算新的距离
            new_distance = current_distance + weight
            
            # 如果找到更短的路径，更新距离和前驱
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                predecessors[neighbor] = current_node
                heapq.heappush(pq, (new_distance, neighbor))
    
    # 如果没有找到路径，返回空路径和无穷大距离
    return [], float('infinity')

复杂度分析

• 时间复杂度：
  • 使用二叉堆：O(E log V)
  • 使用邻接矩阵：O(V²)
  • 使用斐波那契堆：O(E + V log V)
• 空间复杂度：O(V)，用于存储距离数组和访问集合

算法特点

• 贪心策略：每次选择当前最短距离的节点
• 适用条件：边权重必须非负
• 最优性：保证找到最短路径
• 可扩展性：可以添加多种优化策略

常见优化

• 使用斐波那契堆优化优先队列操作
• 双向搜索：同时从起点和终点开始搜索
• 启发式搜索：结合A*算法的思想
• 预处理：对于静态图可以预先计算部分路径