《Python Algorithm》9.与Edsger和小伙伴们从A到B

Python Algorithms explains the Python approach to algorithm analysis and design.

《Python Algorithm》9.与Edsger和小伙伴们从A到B

• 引言
  • 最短路径问题
    • 前述
      • BFS
      • DAG
    • 问题
      • 环路
      • 权重
    • 应用
      • 最少步移动解决谜题
      • 使用货币汇率差赚钱
      • n个人n个工作
      • 修复XML文件不正确的标签
      • 运筹学
      • VLSI制造
      • 机器人学
• 传播知识
  • 基础
    • Ch4的张弛法思想
    • Ch8的DAG图
  • 代码实现
    • 张弛法操作找最短路径
  • 正确性和尽可能少的调用relax函数
    • 对DAG图
      • 每边只进行一次调用
  • 重要事实
    • 前提
      • 起点s
      • 初始化D[s]为0
      • 其他节点为无穷大
      • d(u,v)为u到v的最短路径
    • d(s,v) <= d(s,u) + W[u,v] （三角不等式）
    • d(s,v) <= D[v]
      • 对于不同于s的v，其D[v]初始化为无穷大
      • 只有找到确切的捷径时减少
    • 如果没有路径到v，D[v]永远是无穷大
    • 假定到v的最短路径定义为s到u的最短路径加u到v的边长，则如果D[u]正确，D[v]正确，路径P[v]正确
    • s到v的最短路径为[s,a,b,...,z,v]
      • 假定所有边(s,a),(a,b)...(z,v)有序使用了张弛法
      • 则D[v]和P[v]正确
• 疯狂的张弛法
  • 两个问题
    • 多久没有变化
    • 答案是否正确
  • 考虑最简单的情况
    • 所有边权重都是相同非负
      • 找最短路径即最少边
      • 低效
  • 通常情况
    • 问题
      • 可能负值
      • 边权重不同
    • 正确验证
    • 负数检测
  • Bellman-Ford算法
    • 允许任意值的有向无向均可以的单源最短路径算法
    • 遇到负数给出当前值并放弃
    • 代码实现
    • 改变检查的优势
      • 如果不需要所有迭代，早终止
      • 检测迭代时多余的变化，指示负循环
• 找到隐藏的DAG图
  • Dijkstra算法
    • 算法
    • Θ((m+n) lg n)
    • 代码实现
    • 像
      • Prim
      • BFS
      • DAG最短路径
• 所有人对所有人
  • Johnson算法
    • 结合Dijkstra和Bellman-Ford解决稀疏图问题
    • 常被算法课/书忽视
  • 动机
    • 解决稀疏图中所有点最短路径问题，使用Dijkstra算法
      • 不能解决负边
    • 对于单源最短路径问题，使用Bellman-Ford算法
  • 算法
    • 添加一个新节点s，到所有已存在结点权重0
      • 从s点运行Bellman-Ford算法
    • 得到从s点到每个节点v的距离h(v)
    • 使用h适应每个边的权重
      • 新权重w'(u,v)=w(u,v)+h(u)-h(v)
    • 两个有用属性
      • 保证每个新权重w'(u,v)非负
      • 从新权重中找最短路径，和原始问题结果一样
    • 为什么正确
      • telescoping sums
  • 代码实现
  • 复杂度
    • Θ(mn lg n)
• 不着边际的子问题
  • Floyd算法
    • 参数化子问题
      • 开始结点
      • 终止结点
      • 允许通过的最大结点数
    • d(u,v,k)
      • 仅允许k个断点时，结点u到v已存在的最短路径的长度
      • d(u,v,k) = min(d(u,v,k-1), d(u,k,k-1) + d(k,v,k-1))
    • 算法
      • 不用k
        • d(u,v,k-1)
      • 用k
        • d(u,k,k-1)
        • d(k,v,k-1)
    • 代码实现
      • Floyd-Warshall算法递归实现
      • 迭代版本
  • 图的传递闭包的计算
    • Warshall算法
    • Ex9-9
• 在中间相遇
  • 问题
    • 只想从结点s到t，而不是遍历所有
  • 解决
    • 从起点和终点分别遍历，在中间相遇
  • 启发式算法
  • 双向Dijkstra算法
    • 算法
    • 代码实现
      • 使用生成器的Dijkstra算法
        • 放弃松弛，使用了堆
        • heappush是新的松弛
      • 双向Dijkstra算法
• 知道你要去哪
  • A*算法
    • 像
      • Johnson
        • 区别
          • 假定边正数
          • 希望遍历时有正确的方向
    • h(v)
      • 启发式
        • 选择
      • 对剩余距离d(v,t)的猜测
      • Dijkstra是特例
        • h(v)=0
    • 算法
      • 来源
        • 网络，非本文
      • 公式
        • f(n)=g(n)+h(n)
          • f(n)
            • 起点经过结点n到目标点的估价函数
          • g(n)
            • 起点到结点n的实际代价
          • h(n)
            • 结点n到目标结点最佳路径的估计代价
      • 算法
        • 把起点放到开启列表
        • 重复
          • 寻找开启列表中F值最低的
            • 称为当前格
          • 把它切换到关闭列表
          • 对相邻格中的每一个
            • 如果不可用或已在关闭列表，则略过
            • 如果不在开启列表，则添加，并把当前格作为父节点，记录F、G、H值
            • 如果在开启列表，用G值检查新路径是否更好
              • G值更低，则把其父节点改为当前格，重新计算G和F值
              • 如果保持开启列表按F值排序，需要重新排序
        • 停止
          • 终点进入关闭列表或开启列表已空但没找到终点
        • 保存路径
          • 从终点开始，沿着每一格的父节点直到回到起点
    • 代码实现
      • A*
        • w = G[u][v] - h(u) + h(v)
      • 字梯问题
        • 问题
          • 从一个单词到另一个单词
          • 每一个词语都是通过将前一个单词改变一个字母形成的
• 扩展阅读
  • 启发式算法
    • A*
      • book by Russell and Norvig
      • landmarks
      • ALT
  • Dijkstra算法
    • Fibonacci堆
  • 使用A*的双向Dijkstra算法