解决哪类问题

:::success 启发式搜索
通常我们需要「确保有解」，A 的启发搜索才会发挥真正价值。而本题，除非 endWord 本身就不在 wordList 中，其余情况我们无法很好提前判断「是否有解」。这时候 A 将不能带来「搜索空间的优化」，效果不如「双向 BFS」。 :::

代码模板

  1. 初始化open_set和close_set；
  2. 将起点加入open_set中，并设置优先级为0（优先级最高）；
  3. 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  4.     如果节点n为终点，则：
  5.         从终点开始逐步追踪parent节点，一直达到起点；
  6.         返回找到的结果路径，算法结束；
  7.     如果节点n不是终点，则：
  8.         将节点n从open_set中删除，并加入close_set中；
  9.         遍历节点n所有的邻近节点：
  10.             如果邻近节点m在close_set中，则：
  11.                 跳过，选取下一个邻近节点
  12.             如果邻近节点m在open_set中，则：
  13.                 判断节点n到节点m的 F(n) + cost[n,m] 值是否 < 节点m的 F(m) 。来尝试更新该点，重新设置f值和父节点等数据
  14.             如果邻近节点m也不在open_set中，则：
  15.                 设置节点m的parent为节点n
  16.                 计算节点m的优先级
  17.                 将节点m加入open_set中

复杂度

O(节点复杂度)

运用思想

递归

例题