我想了解有关 TeX 文本对齐算法的实现的更多信息（固定胶水）。
在浏览了 Knuth TeXbook 的第 12 章后，我猜固定胶水必须由受约束的线性规划组成
- 其变量代表单词间的粘合，
- 其约束对应于每个单词间粘合所允许的收缩和拉伸。
然而，如果我的直觉是正确的，那么随着文档长度的增加，所讨论的线性程序必须很快变得非常大，至少对于当时的计算机来说是如此。固定胶水使用一些启发式方法吗？
编辑：感谢 egreg 的回答。然而，我意识到我应该在我的问题中包含段落制作算法。
我仍然不太清楚
- 段落生成算法（我推测它决定了换行的位置），以及
- 文本对齐算法（决定单词之间的粘合）。
在我看来，这两个问题并不是独立的。段落生成算法在生成一个又一个换行符的过程中，是否也没有使用有关每个粘连项（自然宽度、拉伸和收缩组件）的信息？
答案1
不涉及线性规划。
TeX 将项目存储在列表中（垂直、水平或数学列表）。数学列表会转换为水平列表，因此只需讨论前两个列表，但它们在设置粘合时是相似的。
胶水被存储为胶水项目，用其表示自然宽度，拉伸组件和收缩组件。
当 TeX 需要根据水平列表构建具有一定宽度的框或根据垂直列表构建具有一定高度的框（例如，段落或页面中的行）时，它会将所有自然宽度相加，添加非粘合项目的宽度并计算粘合必须拉伸或收缩的量。
如果拉伸s是必需的，并且吨总拉伸可用，TeX 计算“拉伸比”r=英石；如果胶水物品有X拉伸组件，TeX 添加接收至自然宽度。
收缩的情况类似，不同之处在于 TeX 永远不会低于规定的收缩量，并且如果总的收缩量不够，则会输出一个过满的框。
由于拉伸或收缩可以用“无限单位”来表示，因此会有些复杂。好吧，可用的总拉伸或收缩的计算保持了计算结果的更高无穷阶，并且只对符合其规范中无穷阶的粘合项添加（或从自然宽度中移除）。
在任何计算机上，这些操作都非常简单且快速。
段落制作算法仅以间接的方式考虑其构建的水平列表中粘合项的可拉伸性和可收缩性。
粘合项标记可行的换行点，前提是它们前面有一个不可丢弃的项（其他项也标记可行的换行点）。在此阶段，TeX 会查看项的自然宽度，简单地说，选择一系列换行点，使得没有一行会超出当前行\hsize。
实际上，这种选择基于许多参数，基于列表中的惩罚（或隐含惩罚）以及计算出的缺点。可能的断点也是在过程中可能自动插入的任意连字符。
对于每个可行的断点，TeX 都会计算出结果行的粘合率，从而为行分配一个坏度，该坏度将用于计算总缺点。但是此时不会设置粘合，只有当 TeX 选择了最佳的断点序列（根据其规则和各种相关参数的值最佳）时才会设置粘合：\hsize本质上，这些行被放置在宽度为 的水平盒中，\hbox to \hsize{...}现在粘合设置如上所述。
答案2
tex 段落构建算法的工作原理是动态规划在 Knuth, Donald E.; Plass, Michael F. (1981) 的“将段落拆分成行”一文中有所描述，软件：实践与经验 11 (11): 1119–1184，doi:10.1002/spe.4380111102。事实上，它使用动态规划限制了可以实施的一些惩罚类型，但与一般线性规划相比，它可以提供更有效的解决方案。
动态规划基本上意味着您设置问题，以便可以从其子问题的最优解构建最优解。这允许在每个阶段丢弃次优解，因此无需回溯。在 Knuth/Plass 的简化版本中，您可以考虑一个有向无环图 G=(V,E)，其中顶点 v0,v1,v2...vn 表示在段落中插入换行符的可能位置（v0 紧接在段落的第一个单词之前，vn 紧接在最后一个单词之后），边 e0,e1,...,em 带有权重，表示在两个换行符之间设置一行的“坏处”。坏处来自空间需要拉伸/收缩的程度，还包括惩罚，例如不良连字符。问题是找到 G 上从 v0 到 vn 的最小权重路径，这是使用动态规划的经典案例，例如Dijkstra 算法完整的 Knuth/Plass 算法添加了一些改进（例如通过向每个顶点添加松散度标签 0..3 将顶点集增加四倍），而不会失去动态规划的优势，并且进行了一些效率调整（例如不在无用的地方寻找断点，并且仅在没有连字就无法获得好的段落时才确定连字点）。