问题标签 [clrs]

这是 CLRS 24.4-12 的练习，（不是作业，我只是尝试解决 CLRS 中的所有练习）

当 b 的所有元素都是实值并且某些但不一定是所有未知数 xi 的指定子集必须是整数时，给出一个有效的算法来求解具有差异约束的系统 Ax ≤ b。

如果所有 xi 都是整数，我们可以让 b = floor(b) 并使用 Bellman-Ford 算法在约束图中找到解决问题的最短路径，但是 xi 有些是整数而有些不是呢？它类似于整数规划问题，但整数规划是NP-hard，这个问题的约束较少，有没有更高效的算法？

不确定这是否是问这个问题的正确地方。在 Cormen 第 1056 页中，我读到如果算法的运行时间为 O(k)，并且“k”以一元表示，即 k 1s 的字符串，则该算法的运行时间为 0(n)，其中“n”是输入大小以位为单位，如果“k”表示为二进制，则 n=lg k+1 ，算法的运行时间变为 o(2^n)。

所以我的疑问是为什么在这种情况下不会首选“一元”表示，因为它给出了多项式时间，而在其他情况下是指数。

我正在阅读 Cormen 等人的算法简介中的推流算法。

我很难理解引理 26.20，如下所述：

令 G = (V, E) 为源 s 和汇 t 的流网络，设 f 为 G 中的预流。那么，对于任何溢出的顶点 u，在残差网络 Gf 中存在从 u 到 s 的简单路径.

要查看此 leema 的上下文，可以在以下链接中找到。

http://integrator-crimea.com/ddu0164.html

请求您的帮助以了解这一点。

感谢您的时间和帮助。

我正在阅读“算法导论”，第三版。在“分析算法”部分下，它写道：

我们还假设每个数据字的大小有限制。例如，当处理大小为 n 的输入时，我们通常假设整数由 c lg n 位表示，对于某个常数 c>=1。我们要求 c>=1 以便每个单词都可以保存 n 的值，从而使我们能够索引各个输入元素，并且我们将 c 限制为常数，这样单词大小就不会任意增长。

这里的“字”字有什么意义？这是用“单词”表示数据的标准吗？

我在Cormen 等人的《算法导论》第 47 页看到了这段话。：

表达式中匿名函数的数量被理解为等于渐近符号出现的次数。例如在表达式中：

Σ ( i =1 到n ) O( i )

只有一个匿名函数（i的函数）。此表达式与 O(1) + O(2) + ... + O( n ) 不同，后者实际上并没有清晰的解释。

这是什么意思？

在 CLRS中，对查找数组中第 i 个最小元素(2/e, page 191, section 9.3)的算法的分析通过以下归纳证明给出：SELECT

我理解算法，但证明中的两个操作让我有点难过。

问题 1：在第 2 行中，额外的 c 项是从哪里来的（第二项）？c 乘以(7n/10 + 6)项给出7cn/10 + 6c。

问题 2：在第 4 行中，我们是如何从9cn/10to得到的cn + (-cn/10 ...)？9 系数去哪了？

这不是家庭作业

谢谢！

我正在阅读 CLRS 的算法简介。本书展示了简单的分治矩阵乘法的伪代码：

例如，A11 是大小为 n/2 xn/2 的 A 的子矩阵。作者还暗示我应该使用索引计算而不是创建新矩阵来表示子矩阵，所以我这样做了：

它给了我不正确的结果，但我不确定我做错了什么......

这个问题与动态规划有关，特别是来自 CLRS Pg 362 的棒切割问题

整体最优解包含两个相关子问题的最优解。

通过找到单个子问题的最优解，然后以某种方式将它们组合在一起，从而获得整体最优解。我无法理解直觉和概念。任何链接，示例？

谢谢

在 CLRS 的第 264 页底部，作者说获得后r0 = 17612864，14 个最高有效位r0产生哈希值h(k) = 67。我不明白为什么它给出 67，因为二进制的 671000011是 7 位。

编辑 在教科书中：例如，假设我们有k = 123456, p = 14, m = 2^14 = 16384, and w = 32. 采用 Knuth 的建议，我们选择 A 作为s/2^32最接近的形式的分数(\sqrt(5) - 1) / 2，因此A = 2654435769/2^32。然后k*s = 327706022297664 = (76300 * 2^32) + 17612864，等等r1 = 76300 and r0 = 17612864。14 个最高有效位r0产生该值h(k)=67。

在红黑树插入中，我们总是选择将新节点添加为红色，这样我们就可以避免改变树的黑色高度。为什么这比添加黑色节点更可取？