Donald Knuth 和 Michael Plasss 提出的分页问题是一个 NP 完全问题。从直观上看，这个问题与包装问题相关，因此很难解决。然而，通过将 L 2度量放宽到 L 1，Brüggemann-Klein 等人 [1] 声称已经解决了这个问题。由于我不是判断这个问题的专家，我想知道这个问题是否真的已经得到解决，至少在 L 1度量上。
[1] Brüggemann-Klein，Anne，Rolf Klein 和 Stefan Wohlfeil。 “关于复杂文档的分页。”计算机科学的视角。 Springer Berlin Heidelberg，2003 年。49-68。
答案1
Plass 在他的博士论文中证明了，使用动态规划和非常具体的优化函数对文档进行分页是 NP 完全的，但对于其他函数则不是这样。然而，Knuth 认为没有任何方法（即要最小化的合理目标函数）既可以在实际中利用现有的计算机能力，同时提供合理的结果。因此，TeX 最终使用了一种简单的首次适应算法进行分页。
基本上，我们必须提醒自己，没有解决“换行问题”或解决“分页问题”之类的事情。这完全取决于您在算法中添加了哪些标准以及您应该优化哪些类型的函数（即定义您的“质量”），并且这些条件的每种组合都会导致解决完全不同的问题。例如，Knuth 的换行算法仅就其最小化的目标函数而言是最佳的（这在大多数实际情况中提供了有用的质量定义），但显然它不知道段落中的河流，并且会很乐意产生它们。他最小化的缺点是经过严格限制的，因此您不需要跟踪如何到达某个断点（除了知道前一行是松散还是紧密设置，但不知道之前发生了什么）。河流处理会打乱这一点，并可能使换行问题成为 NP 完全问题。
Wohlfeil 在他的博士论文中（您引用的与 Anne 合作的论文是该工作的早期版本）研究了以下问题：
- 文档模型由文本和图形组成
- 数字可以浮动但会保持秩序
- 它们不会出现在其主要参考之前（或者至少从那里可见，即它们可能会稍微浮动在主要参考的前面）
- 质量函数基于查看需要翻多少页才能从其主要参考文献中看到一个图
（还有一些其他的变体和扩展，例如脚注或双跨页，可能比其他的更大，但以上是所考虑的页面模型的要点）
虽然他已经“解决”了分页问题，但问题是这在实际生产中是否足够实用。在他的博士论文中，他记录了一个名为 X-Formatter 的原型实现，但该系统从未公开出现（据我所知）。
在我看来，这不是一个普遍可用的解决方案（尽管这是朝着这样的系统迈出的明确一步），因为它没有涵盖，例如：
- 使用具有多列的更复杂的布局
- 不止一条图形流，不同类型的花车可以在争夺空间的同时相互超越。
然而，我确实认为，他已经清楚地表明，存在一些可以以有用的实际方式衡量“质量”的目标函数，这些目标函数可以通过动态规划方法使用，并且考虑到当今的计算机可能可以推广到为系统提供在可接受的时间内提供有用的分页结果。
答案2
以下是 Sean Allred 建议的文档链接：全局多目标破线