算法——对比A*算法与IDA*算法

A*算法与IDA*算法详细解析

1. A*算法

核心思想：
A*算法是一种启发式搜索算法，结合了Dijkstra算法的最短路径保证和贪心最佳优先搜索的高效导向性。其核心是评估函数 ( f(n) = g(n) + h(n) )，其中：

• ( g(n) ): 从起点到当前节点 ( n ) 的实际代价。
• ( h(n) ): 当前节点 ( n ) 到目标节点的启发式估计代价（需满足可采纳性，即不高估实际代价）。

算法步骤：

1. 初始化：将起点加入优先队列（Open List），记录 ( g ) 值和 ( f ) 值。
2. 循环扩展：
   • 取出 Open List 中 ( f(n) ) 最小的节点 ( n )。
   • 若 ( n ) 是目标节点，回溯路径并结束。
   • 将 ( n ) 移入 Closed List（已处理列表）。
   • 遍历 ( n ) 的邻居 ( m )：
     • 计算临时 ( g_{temp} = g(n) + \text{cost}(n, m) )。
     • 若 ( m ) 不在 Open List 或 Closed List，或 ( g_{temp} < g(m) )，更新 ( m ) 的父节点为 ( n )，并重新计算 ( f(m) )，将 ( m ) 加入 Open List。
3. 终止条件：Open List 为空时，表示无解。

关键特性：

• 可采纳性：启发函数 ( h(n) ) 必须满足 ( h(n) \leq h^*(n) )（实际代价），确保最优解。
• 一致性（单调性）：若 ( h(n) \leq \text{cost}(n, m) + h(m) )（对任意边 ( n \to m )），则 A* 无需重复处理节点（Closed List 不再更新）。

优缺点：

• 优点：高效、保证最优解（若 ( h(n) ) 可采纳）。
• 缺点：内存消耗高（需维护 Open/Closed List）。

应用场景：

• 游戏AI路径规划（如RTS游戏单位移动）。
• 地图导航（如GPS路线计算）。

代码

import heapq# 定义节点类
class Node:def __init__(self, x, y, g=float('inf'), h=float('inf'), parent=None):self.x = xself.y = yself.g = gself.h = hself.f = g + hself.parent = parentdef __lt__(self, other):return self.f < other.f# 启发函数：曼哈顿距离
def heuristic(a, b):return abs(a[0] - b[0]) + abs(a[1] - b[1])# A* 算法实现
def a_star(grid, start, goal):rows, cols = len(grid), len(grid[0])open_list = []closed_set = set()start_node = Node(start[0], start[1], 0, heuristic(start, goal))heapq.heappush(open_list, start_node)while open_list:current = heapq.heappop(open_list)if (current.x, current.y) == goal:path = []while current:path.append((current.x, current.y))current = current.parentreturn path[::-1]closed_set.add((current.x, current.y))neighbors = [(current.x + dx, current.y + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]if 0 <= current.x + dx < rows and 0 <= current.y + dy < cols and grid[current.x + dx][current.y + dy] == 0]for neighbor in neighbors:if neighbor in closed_set:continuetentative_g = current.g + 1neighbor_node = Node(neighbor[0], neighbor[1])if tentative_g < neighbor_node.g:neighbor_node.parent = currentneighbor_node.g = tentative_gneighbor_node.h = heuristic(neighbor, goal)neighbor_node.f = neighbor_node.g + neighbor_node.hheapq.heappush(open_list, neighbor_node)return None# 示例使用
grid = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)
path = a_star(grid, start, goal)
print("A* 算法找到的路径:", path)

---

2. IDA*算法（Iterative Deepening A）*

核心思想：
将迭代加深（Iterative Deepening）与A*结合，通过逐步放宽的阈值进行深度优先搜索（DFS），每次搜索限制 ( f(n) ) 不超过当前阈值，避免内存爆炸。

算法步骤：

1. 初始化：阈值 ( \text{threshold} = f(\text{起点}) = h(\text{起点}) )。
2. 深度优先搜索：
   • 从起点出发，递归访问节点 ( n )。
   • 若 ( f(n) > \text{threshold} )，记录超限的最小 ( f ) 值作为下次阈值。
   • 若找到目标，返回路径。
3. 迭代更新：若未找到目标，将阈值设为上一步记录的最小超限值，重新开始DFS。

关键特性：

• 每次迭代类似一次深度受限的DFS，但限制条件是 ( f(n) \leq \text{threshold} )。
• 内存占用低（仅需存储递归栈）。

优缺点：

• 优点：内存效率极高（无Open/Closed List），适合状态空间大的问题。
• 缺点：可能重复访问节点（需权衡启发式函数质量）。

应用场景：

• 解谜问题（如15数码、华容道）。
• 内存受限环境下的路径搜索。

代码:

# 启发函数：曼哈顿距离
def heuristic_ida(a, b):return abs(a[0] - b[0]) + abs(a[1] - b[1])# 递归深度优先搜索
def dfs(grid, node, goal, limit, path):f = node[2] + heuristic_ida((node[0], node[1]), goal)if f > limit:return fif (node[0], node[1]) == goal:path.append((node[0], node[1]))return Truemin_val = float('inf')rows, cols = len(grid), len(grid[0])neighbors = [(node[0] + dx, node[1] + dy, node[2] + 1) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]if 0 <= node[0] + dx < rows and 0 <= node[1] + dy < cols and grid[node[0] + dx][node[1] + dy] == 0]for neighbor in neighbors:result = dfs(grid, neighbor, goal, limit, path)if result is True:path.append((node[0], node[1]))return Trueif result < min_val:min_val = resultreturn min_val# IDA* 算法实现
def ida_star(grid, start, goal):limit = heuristic_ida(start, goal)while True:path = []result = dfs(grid, (*start, 0), goal, limit, path)if result is True:return path[::-1]if result == float('inf'):return Nonelimit = result# 示例使用
grid = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)
path = ida_star(grid, start, goal)
print("IDA* 算法找到的路径:", path)

---

3. A* vs IDA*：对比与选择

特性	A*	IDA*
内存占用	高（需维护Open/Closed List）	极低（仅递归栈）
时间复杂度	通常更低（无重复搜索）	可能更高（重复访问节点）
启发式要求	可采纳性（必须）	可采纳性（必须）
适用场景	内存充足、需快速求解的问题	内存受限、状态空间爆炸的问题
实现复杂度	中等（需优先队列）	简单（递归DFS）

---

4. 示例与启发式函数

• 网格路径规划：
  • 曼哈顿距离：( h(n) = |x_n - x_{goal}| + |y_n - y_{goal}| )（可采纳）。
• 15数码问题：
  • 错位方块数：不在目标位置的方块数（可采纳但较弱）。
  • 曼哈顿距离和：所有方块到目标位置的曼哈顿距离之和（更强启发式）。

---

5. 总结

• 选择A*：需要快速求解且内存充足时优先使用。
• 选择IDA*：面对超大状态空间或严格内存限制时（如嵌入式系统）。

两者均依赖启发式函数的质量，设计优秀的 ( h(n) ) 可大幅提升性能。实际应用中，可结合问题特点进行优化（如双向搜索、剪枝策略）。