在通用的线性规划问题中,通常给定一个 mn 的矩阵 A、一个 m 维的向量 b 和一个 n 维向量 c,希望能够找到一个 n 维向量 x,使得由 Ax<=b 给定的 m 个约束条件下优化目标函数 cx。单纯形算法并不总能在多项式时间内完成,但却存在其他的运行时间为多项式时间的线性规划算法。单源单目的地最短路径问题和最大流问题都是线性规划问题的特例。
特例:差分约束条件 xi-xj<=bi
通过在对应的约束图中寻找最短路径权重来找到一个差分约束系统的解。那么可以将差分约束问题转化为 Bellman-Ford 算法(SPFA 算法)
设计动态规划算法的步骤:
- 分析最优解的结构
- 递归定义最优解的值
- 自底向上计算最优解的值
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于