利用局部性：近似排序缓冲区问题解析

### 利用局部性：近似排序缓冲区问题解析 #### 1. 问题背景与基础定义 在处理一系列不同颜色和大小的包裹排序问题时，我们假设排序缓冲区初始为空，且处理结束后缓冲区也需为空。可以将缓冲区想象成一辆沿着一排包裹行驶的卡车，途中会不时地装载和卸载包裹。 目标是重新排列输入的包裹序列，使得相同颜色的包裹尽可能在输出序列中连续出现。我们将同一颜色的最大子序列称为颜色块，两个不同颜色块之间会发生颜色变化，而我们的目标就是最小化输出序列中的颜色变化次数。 - **问题 1：最小颜色变化问题** - **描述**：给定一个包裹序列 σ，使用容量为 k 的排序缓冲区对其进行重新排列，以最小化输出序列中的颜色变化次数。 - **相关符号**： - 设 S 是上述问题的一个解决方案，它是 σ 的一种重新排列。 - 整数 dropS(σi) 表示在解决方案 S 中，σi 从缓冲区移除的重排步骤。如果 σi 根本没有存储在缓冲区中，则 dropS(σi) = i。 - BS(j) 表示在解决方案 S 的第 j 步开始时，缓冲区中的包裹集合。 #### 2. 最优解的观察 对于任何输入序列，有以下两个引理成立： - **引理 1**：如果在输入序列中两个相同颜色的包裹相邻，那么存在一个最优解，使得这两个包裹在输出序列中也相邻。 - **引理 2**：对于任何最优解，我们可以假设对于任何颜色，该颜色的包裹在输入序列中的顺序在输出序列中得以保留。 基于引理 1，我们可以将输入序列中的任何颜色块视为一个大包裹。也就是说，我们可以用一个相同颜色的包裹替换由 t 个包裹组成的每个颜色块，并将该包裹的大小设为 t。这样，我们可以假设输入序列中没有相邻的相同颜色包裹。此外，我们可以相对于排序缓冲区容量对包裹大小进行缩放，即缓冲区容量设为 1 而不是 k，每个包裹的大小设为 t/k 而不是 t。我们用 Size(σi) 表示包裹 σi 的大小，对于任何包裹集合 A，用 Size(A) 表示 A 中包裹的总大小。 现在我们来看该问题的最大化变体。如果输出序列中每发生一次颜色变化需要支付一美元，那么当输出序列中有两个相邻的相同颜色包裹时，我们就可以节省一美元。根据引理 2，我们只需考虑那些保留了输入序列中顺序的相邻包裹所节省的美元数。每对这样的包裹称为一个颜色节省。当我们节省的美元数达到最大时，即实现了最大数量的颜色节省，此时颜色变化次数最小。 - **问题 2：最大颜色节省问题** - **描述**：给定一个由不同颜色和大小的包裹组成的序列，且没有两个相邻的相同颜色包裹，使用容量为 1 的排序缓冲区对其进行重新排列，以最大化输出中的颜色节省数量。 - **问题等价性**：问题 1 和问题 2 是等价的，因为我们可以将自己限制在符合引理 1 和引理 2 假设的调度方案中。然而，一个用于最大化问题的常数近似算法可能不是用于最小化问题的常数近似算法。我们给出了问题 2 的常数近似算法，但问题 1 的此类算法尚未可知。 我们进一步扩展符号，给定 σ = σ1, σ2, ..., σn，我们用 ri 表示 σ 中第 i 个颜色为 r 的包裹，用 ri 表示该包裹在 σ 中的索引（即 ri = σri）。对于每种颜色 r 和索引 i，我们称 ri - ri+1 为一对，其中 ri 是该对的第一个包裹，ri+1 是最后一个包裹。如果在解决方案 S 的输出序列中，ri+1 出现在 ri 的右侧相邻位置，我们称 ri - ri+1 是 S 中的一个颜色节省。 例如，输入序列为 a1b1c1a2c2b2c3a3（字母表示颜色，索引区分相同颜色的包裹），共有 8 个包裹。假设所有包裹大小相同，缓冲区可容纳 2 个包裹（即对于所有 i = 1, 2, ..., 8，Size(σi) = 0.5）。一个最优解决方案 S 的输出序列为 a1a2b1b2c1c2c3a3。S 将 b1 和 c1 存储在缓冲区中，在 a2 步骤后卸载 b1，存储 c2，并在 b2 步骤卸载 c1 和 c2。输出序列有 3 次颜色变化和 4 次颜色节省（可能的颜色节省有 5 次），其中 a2 - a3 是唯一不是颜色节省的一对。 如果 ri - ri+1 是 S 中的一个颜色节省，设 j = dropS(ri)。如果 j < ri+1 - 1，我们称其为被动颜色节省。在这种情况下，为了实现颜色节省，ri+1 不存储在缓冲区中，而所有包裹 {σj+1, σj+2, ..., σri+1 - 1} 都存储在缓冲区中。我们称这些包裹为 ri - ri+1 的清除区。需要注意的是，一个包裹不能同时处于多个清除区。在上述示例中，颜色节省 a1 - a2 和 b1 - b2 是被动的，其中 dropS(a1) = a1 = 1，dropS(b1) = a2 = 4 < 6 = b2 - 1。a1 - a2 的清除区是 {b1, c1}，b1 - b2 的清除区是 {c2}。 基于这些术语，我们可以对最优解做出进一步假设： - 每个进入缓冲区的包裹都有其目的，要么是为了实现颜色节省，要么是为了帮助另一个包裹实现颜色节省（被动颜色节省）。 - 在后者情况下，当包裹不再需要时，应立即从缓冲区移除。 - 如果一个包裹进入缓冲区是为了实现颜色节省，但该颜色节省是被动的（例如，包裹在到达目的地之前就被卸载了），我们假设这是因为清除区中的某个包裹开始了一个颜色节省（否则，为什么不一直进行下去以实现主动颜色节省呢）。 以下是相关引理和推论： - **引理 3**：对于任何最优解，我们可以假设： 1. 如果 ri 存储在缓冲区中，那么要么 ri 是一个颜色节省的第一个包裹，要么 ri 处于另一个颜色节省的清除区中。 2. 设 cs