普林斯顿算法讲义（四）（2）

普林斯顿算法讲义（四）（1）https://developer.aliyun.com/article/1484179

练习

1. 粒子碰撞游戏。 实现游戏Particles：你用鼠标控制一个红色球，试图避免与根据弹性碰撞定律行事的蓝色球碰撞。 一段时间后，随机引入一个新的蓝色球。
   
2. 布朗运动。 1827 年，植物学家罗伯特·布朗使用显微镜观察了浸泡在水中的野花花粉颗粒的运动。 他观察到花粉颗粒是随机运动的，遵循后来被称为布朗运动的运动。 这种现象被讨论过，但直到爱因斯坦在 1905 年提供了一个数学解释之前，没有提供令人信服的解释。 爱因斯坦的解释：花粉颗粒的运动是由数百万微小分子与较大颗粒碰撞引起的。 他给出了描述在给定温度下悬浮在液体中的微小颗粒行为的详细公式。 爱因斯坦的解释旨在帮助证明原子和分子的存在，并可用于估计分子的大小。 爱因斯坦的布朗运动理论使工程师能够通过观察单个粒子的运动来计算合金的扩散常数。 这里有一个来自这里的 Einstein’s explanation of Brownian motion 演示。
   
3. 自由程和自由时间。 自由程 = 粒子在碰撞之间行进的距离。 绘制直方图。 平均自由程 = 所有粒子的平均自由程长度。 随着温度的升高，平均自由程增加（保持压力恒定）。 计算自由时间长度 = 粒子与另一个粒子或墙壁碰撞之前经过的时间。
   
4. 碰撞频率。 每秒碰撞次数。
   
5. 均方根速度。 均方根速度 / 平均自由程 = 碰撞频率。均方根速度 = sqrt(3RT/M)，其中摩尔气体常数 R = 8.314 J / mol K，T = 温度（例如，298.15 K），M = 分子质量（例如，氧气为 0.0319998 kg）。
   
6. 麦克斯韦-玻尔兹曼分布。 在硬球模型中，粒子速度的分布服从麦克斯韦-玻尔兹曼分布（假设系统已经热化，粒子足够重，我们可以忽略量子效应）。 分布形状取决于温度。 每个分量的速度分布与 exp(-mv_x² / 2kT)成比例。 在 d 维中速度的大小分布与 v^(d-1) exp(-mv² / 2kT)成比例。 在统计力学中使用，因为模拟大约 10²³ 个粒子是不方便的。 原因：x，y 和 z 方向的速度是正态的（如果所有粒子质量和半径相同）。 在 2d 中，用 Rayleigh 代替麦克斯韦-玻尔兹曼。
   
7. 压力。 感兴趣的主要热力学性质 = 平均压力。压力 = 分子碰撞对容器施加的单位面积的力。在二维中，压力 = 容器壁上单位长度的平均力。
   
8. 温度。 绘制随时间变化的温度（应保持恒定）= 1/N sum(mv²) / (d k)，其中 d = 维度 = 2，k = 玻尔兹曼常数。
   
9. 扩散。 分子移动非常迅速（比喷气机更快），但扩散缓慢，因为它们与其他分子碰撞，从而改变它们的方向。两个通过管道连接的容器，其中包含两种不同类型的粒子。随时间变化测量每种类型粒子在每个容器中的比例。
   
10. 时间可逆性。 改变所有速度并向后运行系统。忽略舍入误差，系统将返回到其原始状态！
    
11. 麦克斯韦的恶魔。 麦克斯韦的恶魔是詹姆斯·克拉克·麦克斯韦于 1871 年构想出来的一个思想实验，旨在反驳热力学第二定律。中间有垂直墙壁，带有分子大小的陷阱门，左半部分有 N 个粒子，右半部分也有 N 个粒子，只有恶魔允许通过的粒子才能通过陷阱门。恶魔让左到右速度比平均速度快的粒子通过，让右到左速度比平均速度慢的粒子通过。可以利用能量重新分配来运行热机，允许热量从左到右流动。（不违反法则，因为恶魔必须与物理世界互动以观察分子。恶魔必须存储关于分子在陷阱门哪一侧的信息。恶魔最终会耗尽存储空间，必须开始擦除先前积累的信息以为新信息腾出空间。这种信息的擦除增加了熵，需要 kT ln 2 单位的工作。)
    
12. 度量空间。 扩展以支持任意度量空间中的球体和超平面。
    
13. 细胞方法。 有用的优化：将区域划分为矩形单元。确保粒子只能在任何时间量子中与九个相邻单元中的粒子发生碰撞。减少必须计算的二元碰撞事件数量。缺点：必须监视粒子在单元之间移动的过程。
    
14. 多粒子碰撞。 处理多粒子碰撞。在模拟台球游戏中的碰撞时，这种碰撞非常重要。
    
15. 动态堆或动态数据结构。（Guibas）
    

创意练习

6.2 B 树

原文：algs4.cs.princeton.edu/62btree

译者：飞龙

协议：CC BY-NC-SA 4.0

本章正在进行重大改建。

问答

练习

6.3 后缀数组

原文：algs4.cs.princeton.edu/63suffix

译者：飞龙

协议：CC BY-NC-SA 4.0

本章正在大规模施工中。

重要说明。

*从 Oracle 和 OpenJDK Java 7，Update 6 开始，substring()方法在提取的子串大小上花费线性时间和空间（而不是常数时间和空间）。String API对其所有方法，包括substring()和charAt()，都不提供性能保证。

课本和书站中的程序已经更新，不再依赖于常数时间的子串操作。但是，如果您使用的是课本的第三版印刷版（或更早版本），请自行考虑。*

后缀排序和后缀数组。

后缀排序：给定一个字符串，按升序对该字符串的后缀进行排序。排序后的列表称为后缀数组。程序 SuffixArray.java 构建了一个后缀数组数据结构。

最长重复子串。

将排序应用于计算生物学和抄袭检测。程序 LongestRepeatedSubstring.java 使用后缀数组解决了这个问题。

上下文关键词（KWIC）。

给定后缀数组，通过二分搜索很容易搜索字符串或句子。内存是线性的。搜索是 O(K log N)，其中 K 是您要搜索的字符串的长度。（通过使用 lcp 数组，可以在 K + log N 内完成。）有时被称为 KWIK（关键词上下文）和共现。被语言学家使用。Concordancer = 制作索引的程序。马丁·阿贝格（Martin Abegg）曾经将死海古卷的索引反向工程并转换为可读文本。程序 KWIK.java。

Manber 算法。

然而，输入大小为 N，因此我们可能希望利用子串的重叠性质并取得更好的效果。程序 Manber.java 使用 Manber-Myers 重复加倍算法的版本对字符串后缀进行排序。Larsson在内部排序例程替换为 O(N log N)基于比较的排序算法时给出了 O(N log N)的分析。

Kasai 算法。

这里是描述Kasai 算法计算 lcp 数组的内容。

问答

线性时间后缀排序。

倾斜分治。最简单的线性时间后缀排序解决方案。递归地对索引为{0, 1, 2} mod 3 的后缀进行排序，然后合并。

练习

1. 给出字符串"abacadaba"的后缀数组。此外，给出 i 从 1 到 n-1 的lcp(i)值表。
   
2. 对字符串"mississippi"重复上一个问题。
   
3. 创建一个长度为 n 的SuffixArray对象需要多少字节？
   
4. 下面的代码片段计算后缀排序的所有后缀有什么问题？

suffix = ""; 
for (int i = s.length() - 1; i >= 0; i--) {
    suffix = s.charAt(i) + suffix;
    suffixes[i] = suffix;
}

1. 答案：二次时间 和 二次空间。
2. 下面的代码片段计算后缀排序的所有循环后缀有什么问题？

int n = s.length();
for (int i = 0; i < n; i++)
    suffixes[i] = s.substring(i, n) + s.substring(0, i);

1. 答案：二次时间 和 二次空间。
2. 下面的代码片段计算后缀排序的所有循环后缀有什么问题？

int n = s.length;
StringBuilder ss = new StringBuilder();
ss.append(s).append(s);
for (int i = 0; i < N; i++)
    suffixes[i] = ss.substring(i, i + n);

1. 答案：二次时间 和 二次空间。
2. 最长公共子串。 编写一个程序 LongestCommonSubstring.java，接受两个文件名作为命令行参数，读取这两个文本文件，并找到两者中都出现的最长子串。提示：为 s#t 创建一个后缀数组，其中 s 和 t 是两个文本字符串，#是两者都不出现的字符。
   1970 年，D. Knuth 猜想在线性时间内解决这个问题是不可能的。事实上，可以使用后缀树或后缀数组在线性时间内（在最坏情况下）解决这个问题。
   
3. Burrows-Wheeler 变换。 Burrows-Wheeler 变换（BWT）是数据压缩算法中使用的一种转换，包括 bzip2 和基因组学中的高通量测序。给定长度为 N 的文本字符串（以特殊的文件结束符 $ 结尾，比任何其他字符都小），考虑 N×N 矩阵，其中每行包含原始文本字符串的不同循环旋转。按字典顺序对行进行排序。Burrows-Wheeler 变换是排序矩阵中的最右列。例如，BWT (mississippi) = i p s s m ) = ipssm)=ipssmpissii。
   
4. Burrows-Wheeler 逆变换。 Burrows-Wheeler 逆变换（BWI）用于反转 BWT。给定文本字符串的 BWT，设计一个线性时间算法来恢复原始文本字符串。例如，BWI(ipssmp i s s i i ) = m i s s i s s i p p i pissii) = mississippipissii)=mississippi。
   
5. 循环字符串线性化。 给定一个字符串 s，找到字典序最小的旋转。在化学数据库中用于循环分子。每个分子表示为循环字符串。规范表示是字典序最小的旋转。设计一个算法来计算循环字符串的规范表示 提示：后缀排序。
   其他解决方案：Duval 算法使用 Lyndon 分解和由周元提出的令人惊讶优雅的最小表达算法。
   
6. 加速排名。 使用以下思想加速 rank() 方法中的二分搜索。让 lo 和 hi 表示当前搜索区间的左右端点。让 lcpLo 表示查询字符串和 suffixes[lo] 的 lcp，让 lcpHi 表示查询字符串和 suffixes[hi] 的 lcp。然后，在将查询字符串与 suffixes[mid] 进行比较时，只需要比较从 lcp = min(lcpLo, lcpHi) 开始的字符，因为搜索区间中的所有后缀都具有相同的前 lcp 个字符。
   
7. 加速排名分析。 显示加速排名的最坏情况运行时间仍然与 L log N 成正比，其中 L 是查询的长度，N 是文本的长度。然而，Myers 和 Manber 报告说这在实践中加快了计算。理论上，可以使用非相邻的 lcp 值将其改进为 L + log N。
   
8. 最长 3 重复子串。 给定一个文本字符串，找到重复 3 次或更多次的最长子串。
   
9. 最长 k 重复子串。 给定一个文本字符串和一个整数 k，找到重复 k 次或更多次的最长子串。
   
10. 长重复子串。 给定一个文本字符串和一个整数 L，找到所有长度大于等于 L 的重复子串。
    
11. 三个字符串中的最长公共子串。 给定三个字符串 r、s 和 t，找到在所有三个字符���中出现的最长子串。
    
12. 最长公共反向互补子串。 给定两个 DNA 字符串，找到出现在一个字符串中的最长子串，其反向 Watson-Crick 互补出现在另一个字符串中。如果 t 是 s 的反向，除了以下替换 AT、CG，则两个字符串 s 和 t 是反向互补的。例如 ATTTCGG 和 CCGAAAT 是彼此的反向互补。 提示：后缀排序。
    
13. 具有更少内存的后缀数组。 不使用子字符串数组，其中 suffixes[i] 指的是第 i 个排序后缀，而是维护一个整数数组，其中 index[i] 指的是第 i 个排序后缀的偏移量。要比较由 a = index[i] 和 b = index[j] 表示的子字符串，比较字符 s.charAt(a) 与 s.charAt(b)，s.charAt(a+1) 与 s.charAt(b+1)，依此类推。你节省了多少内存？你的程序更快吗？
    
14. k-gram 频率计数。 给定一个文本字符串，设计一个数据结构以高效地回答以下形式的查询：给定一个 k-gram 出现了多少次？在最坏情况下，时间复杂度应该与 k log N 成正比，其中 k 是 k-gram 的长度，N 是文本字符串的长度。
    
15. 最频繁的 k-gram。 给定一个文本字符串和一个整数 k，找到出现频率最高的 k-gram。
    
16. 最短唯一子串。 给定一个文本字符串，找到一个出现仅一次的最短子串。这个问题常见于生物信息学。
    
17. 最短非子串。 给定一个比特串，找到一个最短的比特串，它不作为子串出现。
    
18. 最短唯一子串。 给定一个文本字符串，预处理它以回答以下形式的最短唯一子串查询：给定一个索引 q 到文本字符串，找到一个包含索引 q 且在文本中其他地方不作为子串出现的最短子串。
    

6.4 最大流

原文：algs4.cs.princeton.edu/64maxflow

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大规模建设中。

最大流和最小 s-t 割。

程序 FordFulkerson.java 在 E² V 时间内使用 Edmonds-Karp 最短增广路径启发式方法计算带权有向图中的最大流和最小 s-t 割（尽管在实践中，它通常运行得更快）。它使用 FlowNetwork.java 和 FlowEdge.java。

渗透。

2D（始终选择最左边的路径）和 3D 中的最大流。

应用于计算机图形学。

Yuri Boykov在计算机视觉中的分割应用中有关于最大流的论文。maxflow data。

二部图匹配。

练习

1. **包含两个顶点的循环。**给定一个无向图 G 和两个特殊顶点 s 和 t，找到包含 s 和 t 的循环（不一定是简单的），或报告不存在这样的循环。您的算法应该在线性时间内运行。
   答案。当且仅当从 s 到 t 的最大流至少为 2 时，答案是肯定的。因此，在每条边都替换为两条反向边和单位容量的有向图中运行 Ford-Fulkerson 的两次迭代。
   
2. **k-连通。**给定一个无向图，确定两个顶点 s 和 t 是否 k-连通（或等价地，是否存在 k 条边不相交的路径）。
   
3. 真或假。如果为真，请提供简短的证明，如果为假，请给出一个反例。

• 在任何最大流中，没有一个有正流量的有向循环。
  
• 存在一种最大流，其中没有一个有正流量的有向循环。
  
• 如果所有边的容量都不同，最大流是唯一的。
  
• 如果所有边的容量都不同，最小割是唯一的。
  
• 如果所有边的容量增加一个加法常数，最小割保持不变。
  
• 如果所有边的容量乘以一个正整数，最小割保持不变。
  

4. **包含两个顶点的简单循环。**给定一个无向图和两个顶点 s 和 t，找到包含 s 和 t 的简单循环（或报告不存在这样的循环）。
   提示：当且仅当存在两个（内部）顶点不相交的路径时，包含 s 和 t 的有向循环才存在。
   
5. **有向图中的顶点不相交路径。**给定一个有向图 G 和两个顶点 s 和 t，找到从 s 到 t 的最大数量的顶点不相交路径。
   提示：将每个顶点 v（除了 s 和 t 之外）替换为两个顶点 v1 和 v2；从 v1 到 v2 添加容量为 1 的边；将所有指向 v 的边重定向到 v1；将所有从 v 指向的边重定向到 v2。
   
6. **无向图中的顶点不相交路径。**给定一个无向图 G 和两个顶点 s 和 t，找到 s 和 t 之间的最大数量的顶点不相交路径。
   提示：将每条无向边 v-w 替换为两条有向边 v->w 和 w->v。
   
7. **包含三个顶点的简单路径。**给定一个无向图和三个顶点 u、v 和 w，找到包含 u、v 和 w 的简单路径（或报告不存在这样的路径）。
   提示：当且仅当存在两个（内部）顶点不相交的路径，一个从 v 到 u，一个从 v 到 w 时，u 和 w 之间存在一个通过 v 的简单路径。
   
8. **唯一最小割。**给定一个 s-t 流网络，确定最小割是否唯一。
   提示：在 G 和 G^R 中解决 s-t 最小割问题。
   
9. **二部图中的不可匹配边。**给定一个二部图 G，如果边不出现在 G 的任何完美匹配中，则该边是不��匹配的。
   提示：如果 G 没有完美匹配，那么所有边都是不可匹配的。否则，找到一个完美匹配；将完美匹配中的所有边定向为一个方向，将所有剩余的边定向为相反的方向；不在完美匹配中且端点在结果有向图的不同强连通分量中的边都是不可匹配的边。
   
10. 具有最少边的最小割。 给定一个流网络，在所有最小割中，找到一个具有最少边数的割。
    提示：创建一个新的流网络 G’，它等于 G，除了 w’(e) = w(e) * n + 1。
    

6.5 归约

原文：algs4.cs.princeton.edu/65reductions

译者：飞龙

协议：CC BY-NC-SA 4.0

本章节正在建设中。

归约。

在计算机科学中，归约或模拟是一个强大的概念… 将问题 X 转化为一个更简单的问题 Y 的问题解决框架，以便根据 Y 的解推导出原始问题 X 的解。

Eric Alander - “归约提供了一种抽象。如果 A 高效地归约到 B，且 B 高效地归约到 A，那么 A 和 B 在某种意义上是等价的：它们是观察同一问题的两种不同方式。我们不再有无限多的计算问题，而是留下了更少数量的等价问题类。没有什么能让计算社区为这一惊人的洞察做好准备，即人们真正想要解决的计算问题只有几个。根据资源限制将自然计算问题划分为有意义的组别。”

上界。

• 3-共线到排序。
  
• 凸包到排序（Graham 扫描）。
  
• 中位数到排序。
  
• 二分图匹配到最大流。BipartiteMatchingToMaxflow.java 通过将问题归约为最大流，在二分图中计算最大基数匹配。在最坏情况下，每次增广都会增加匹配的基数。Hopcroft-Karp 算法将运行时间改进为 E sqrt(V)。
  
• LP 标准形式：标准形式线性规划是 { max cx : Ax <= b, x ≥ 0 }。展示如何将一般线性规划（带有 ≤、≥ 和 = 约束）归约为标准形式。
  
• 最大流到线性规划。
  
• 分配问题到线性规划。
  
• PERT 到 有向无环图的拓扑排序。
  
• USTCONN（无向图中的 s-t 连通性）到 STCONN（有向图中的无向 s-t 连通性）。
  
• 无向图上的最短路径到有向图上的最短路径。
  
• 欧几里得最小生成树到 Delauney 三角剖分。
  
• LP 可行性归约为 LP。（使用二分搜索。需要限制有界 LP 的值。）
  
• 二人零和博弈到 LP。TwoPersonZeroSumGame.java
  
• LP 可归约为二人零和博弈。（Bradley, Hax, 和 Magnanti 的练习 26）
  

下界。

• 元素唯一性到排序。
  
• 2D 最近点对问题到 2D 欧几里得最小生成树。
  
• 凸包到 Voronoi / Delauney 三角剖分。
  
• 3-SUM 到 3-共线。
  
• 练习：3-SUM 到 4-SUM。
  
• 练习：3-SUM 到 3-SUMplus
  
• 练习：3-共线到 3-共点。
  
• 3-SAT 到 独立集。
  
• 独立集到整数线性规划。
  
• 元素唯一性。 给定 N 个来自全序宇宙的元素 x[1], …, x[n]，是否存在一对 i ≠ j，使得 x[i] = x[j]？在比较树模型和代数决策树模型中有 Theta(N log N) 的下界。通过排序可以轻松达到 O(N log N)。
  解决方案 1（比较树模型）：给定 N 个不同的值。让 ai 成为第 i 小的元素。在任何基于比较的算法中，我们必须比较 a[i] 和 a[i-1]；否则算法无法区分 a[i-1] < a[i] 和 a[i-1] = a[i] 的情况。考虑 N 个元素的两种不同排列。存在一个元素 a[i]，在第一个排列中 a[i-1] 在 a[i] 之前，但在第二个排列中 a[i-1] 在 a[i] 之后。由于每个基于比较的算法必须比较 a[i] 和 a[i-1]，算法在这两个排列上运行不同。因此，至少有 N! 个叶子节点。参考链接
  解法 2（比较树模型）：假设元素都是不同的且 a_1 < a_2 < … < a_N。任何正确的元素唯一性算法必须对每个 i < N 比较 a_i 和 a_i+1。如果不这样做，那么如果我们将 a_i+1 更改为 a_i，算法将产生相同的输出（但这将从无重复更改为有重复的答案）。算法使用的比较集合形成一个 DAG。找到总顺序（线性时间）并得到排序顺序。因此，该算法可用于对不同元素进行排序，且排序下界适用。
  备注：这些论点适用于比较树模型的计算，但不适用于线性决策树或代数决策树模型的计算。这里有一个更一般的论点（由 Jeff Erickson 提供）：考虑所有可能输入的空间 R^n。正输入的集合有 n！个连通分量，每个排列一个。另一方面，可以到达线性决策树中任何叶子的输入子集是凸的，因此是连通的。因此，任何确定唯一性的线性决策树至少有 n！个叶子。线性决策树的结果是由 Dobkin 和 Lipton 在On the complexity of computations under varying sets of primitives.中得出的。代数决策树的结果是由 Ben-Or 在Lower bounds for algebraic computation trees.中得出的。整数输入的特殊情况的结果更微妙：参见 Lubiw 和 Racs 的整数元素唯一性问题的下界。
  
• 3-SUM。
  
• 3-SAT。
  

线性规划。

将线性方程组推广到不等式。

讲座幻灯片

单纯形算法。

由 George Dantzig 于 1948 年发明。根据 Dongarra 和 Sullivan 的说法，单纯形算法是 20 世纪对科学和工程影响最大的十大算法之一。广义的高斯消元以处理不等式。程序 LinearProgramming.java 是一个基本实现。它解决{ max cx : Ax <= b, x >= 0 }假设 b >= 0。因此 x = 0 是一个基本可行解（我们不需要担心单纯形的第一阶段）。

线性规划的基本定理。形式为（P）的每个 LP 都具有以下三个属性：（i）如果它没有最优解，则它要么是不可行的，要么是无界的（ii）如果它有一个可行解，则它有一个基本可行解（iii）如果它有一个最优解，则它有一个基本最优解。

强对偶定理。形式为（P）的每个 LP 都有一个对偶（D）{ min by : y A >= c : y >= 0 }。p1 + p2 + … + pM = 1 -> x1 + x2 + … + xm = 1/V。

如果（P）有���且可行，则（D）也有界且可行。此外，它们具有相同的最优值。单纯形算法同时解决这两个问题。

显著特性。实践中，单纯形算法通常在最多 2(m+n)个主元中终止。n = 总变量（原始+松弛），m = 方程。

陷阱。退化，循环。

分配问题。

形式化为 LP。依赖于 Birchoff-von Neumann 定理：分配问题 LP 的所有极端点都是 {0, 1}。AssignmentProblemToLP.java 将分配问题（最大权重完美匹配）简化为线性规划。EasyAssignmentProblemToLP.java 将所有内容放在主函数中，不提取对偶解。Hungarian.java 实现了匈牙利算法；在最坏情况下，运行时间的增长数量级为 N⁴。 --> AssignmentProblem.java 实现了连续最短路径算法；在最坏情况下，运行时间的增长数量级为 N³ log N。AssignmentProblemDense.java 实现了连续最短路径算法；在最坏情况下，运行时间的增长数量级为 N³。

二人零和博弈。

简化为 LP。可以假设收益矩阵严格为正（对每个条目添加一个常数会使游戏的价值增加 M，但不会改变解）。（P）min { x1 + … + xm, : x >= 0, M^t x >= 1} 和（D）max { y1 + … + yn, : y >= 0, My <= 1}。将解向量 x* 和 y* 标准化，以获得行玩家（最小化）和列玩家（最大化）的最佳策略；标准化常数是游戏的价值。

技巧。替换变量：xi = pi / V；最大化 V -> 最小化 1/V；博弈论，第 6-7 页

程序 ZeroSumGame.java 实现了这种方法。

注意：通过适当的变量更改，任何 LP 都可以转化为这种形式。

极小极大定理。（冯·诺伊曼）。对于每个有限的二人零和博弈，存在一个值 V 和每个玩家的混合策略，使得（i）给定行玩家的策略，列玩家的最佳可能收益是 V，以及（ii）给定列玩家的策略，行玩家的最佳可能收益是 -V。

线性规划求解器。

• LinearProgramming.java 是单纯形算法的简化版本。假设 b >= 0，因此 x = 0 是一个起始的基本可行解。TwoPhaseSimplex.java 是两阶段单纯形算法的简化版本，它消除了假设 b >= 0。
  
• OR-Objects 包含一个 Java 线性规划求解器。LPDemo.java 演示了如何使用 or124.jar 解决线性规划问题。
  
• QSopt 是由大卫·阿普尔盖特、威廉·库克、Sanjeeb Dash 和 Monika Mevenkamp 创造的 Java 线性规划求解器。可以免费用于研究或教育目的。QSoptSolver.java 解决了 LP 格式的线性规划问题，例如 beer.lp。
  
• Matlab 包含优化工具箱中的线性规划求解器。

[wayne:tombstone] ~> matlab
                                      < M A T L A B (R) >
                            Copyright 1984-2009 The MathWorks, Inc.
                          Version 7.9.0.529 (R2009b) 64-bit (glnxa64)
                                        August 12, 2009
>> A = [5 15; 4 4; 35 20];
>> b = [480; 160; 1190];
>> c = [13; 23];
>> lb = [0; 0];
>> ub = [inf; inf];
>> x = linprog(-c, A, b, [], [], lb, ub)
x =
    12.0000
    28.0000

• CPLEX 是用于线性规划、混合整数规划和二次规划的高性能数学规划求解器。支持与 C、C++、Java、Python、Matlab 和 Microsoft Excel 的接口。也可通过建模系统（包括 AIMMS、AMPL、GAMS 和 MPL）访问。

普林斯顿算法讲义（四）（3）https://developer.aliyun.com/article/1484181