采用任意分布式锥体的传送带上的最佳冰淇淋圆锥填充工艺

Question

我有一个由现实生产问题引起的算法问题.

设置.空的冰淇淋甜筒随机分布在移动的传送带上.配料设备有一个软管,可以在一定范围内在带上方移动(远小于带的长度).为了填充空锥体,将软管放置在锥体的正上方并锁定在其上一段时间直到填充过程结束.因此,这意味着在填充过程中,锥体必须保留在软管管道到达区域中.完成后,软管可以移动到另一个锥体.显然,如果速度不够大并且填充过程需要一些时间,如果锥体足够多且不方便放置,则系统将错过一些锥体.所以问题是通过预先安排填充顺序来尽可能多地填充锥体.

正式我们有输入:

• U - 皮带的速度

• V - 软管的速度

• W - 皮带宽度

• L - 腰带的长度

• P - 软管到达区域的长度

• T - 灌装过程的时间

• 锥体 - 皮带上锥体的坐标数组

理想情况下,输出是连续填充的锥体列表,以确保填充锥体的最大数量.或者至少估计可能填充的锥体的最大数量.

任何有关如何解决这个问题的建议将不胜感激!

Answer 1

使用仅向前分配器实现最佳锥形填充

假设传送带从右向左移动。下面我将描述一种以填充最大可能数量的圆锥体的方式制定和解决问题的方法，假设分配器永远不会比传送带更快地向左移动。对于 n 个锥体，基本算法具有非常宽松的（见下文）O(n^3) 时间和 O(n^2) 空间上限 - 这对于最多 1000 个锥体左右应该是可行的。如果你有更多的圆锥体，你可以将它们分成最多这个大小的块，然后简单地一个接一个地处理每个块。还有一种方法可以稍微放松永不向左快速移动的限制，从而可能填充更多的圆锥体，而不会导致整个问题变成指数时间 - 我将在稍后描述。

假设所有圆锥体都有正 x 坐标，并且软管到达区域（最初从 x = 0 向左延伸到 x = -P）在圆锥体上向右移动，而圆锥体本身保持静止。因此，在时间 t 时，软管到达区域将从 x = U * t 向左延伸到 x = U * t - P。在描述分配器的位置时，我将始终使用相同的（即绝对的）co-坐标系；我们将通过确保在任何时间 t 时，其 x 位置位于 U * t - P 和 U * t 之间，来确保其保持有效位置（在软管到达区域内）。请注意，如果我们将其解释为分配器在给定时间直接位于给定锥体上方，则（时间，锥体 ID）对足以完全确定软管到达区域和分配器的位置。（稍后这将有助于简化系统状态的描述。）最后，我将调用分配器的任何不减少其绝对 x 坐标的运动（这包括相对于其外壳的任何向后运动，即速度低于 U，并且根本没有运动）“向前”运动，以及任何进行“向后”运动的运动。

动态规划公式

通过增加 x 位置对圆锥体进行排序，任意打破平局。令 (x_i, y_i) 为排序顺序中第 i 个圆锥体的位置。

令 e(i) 为我们可以将分配器定位在圆锥体 i 上的最早时间（如果它是我们唯一关心的圆锥体），并且分配器已经在正确的垂直位置（即 y_i）处“等待”。软管到达区域的最右端：这就是 x_i / U。

令 m(i, j) 为将分配器从圆锥体 i 移动到圆锥体 j 所需的时间，假设可以这样做而不必等待其中任何一个“滚动到视图中”：这可以轻松计算为任何坐标对 (i, j) 以及速度 V 和 U（即使分配器可以同时在 x 和 y 方向上以任意速度 V_x 和 V_y 移动，这仍然成立）。

现在我们来看看高效解决这个问题的关键函数：

令 f(i, j) 为我们可以完成填充圆锥体 i 的最早时间，这样我们到目前为止已经恰好填充了 j 个圆锥体（包括这个，因此 1 <= j <= i），如果不是，则为无穷大可行的。 令 g(i, j) 为以相同方式定义的辅助函数，只不过我们允许最后一个圆锥体填充步骤将分配器向左推得太远（稍后您就会明白原因）。我们可以计算 g(i, j)，更重要的是，f(i, j) 如下：

g(i, j) = max(e(i), minimum of f(k, j-1) + m(k, i) over all k s.t. j <= k < i) + T
f(i, j) = IF U * g(i, j) - P <= x_i THEN g(i, j) ELSE infinity

真是一团糟！让我们一点一点地来。

该f(k, j-1) + m(k, i)术语是指填充 j-1 个圆锥体（以圆锥体 k 结束），然后将分配器移动到圆锥体 i 所需的最短时间。围绕max(e(i), ...)这一点确保了，如果上述术语隐含的移动会导致分配器向右移动太远（即，到某个 x 坐标 > U * t），则不会采用该移动。相反，我们将把分配器移动到 (U * t, y_i)——也就是说，移动到圆锥体 i 的正确 y 坐标并尽可能靠右——然后等待圆锥体 i 滚动（因此在时间 e(i) 出现在分配器正下方）。无论我们采取哪一种行动，都需要另外 T 个时间单位来填充圆锥体 i。

（从技术上讲，上述计算假设，如果可以在某个给定时间 t 将分配器移动到 (x_i, y_i)，那么也可以在同一时间将其移动到 (U * t < x_i, y_i)最新的。但是由于我们的起始 x 位置 <= U * t，唯一可能无法成立的方法是，如果描述在 2 个给定点之间移动所需时间的函数违反了三角形不等式，则这种情况不会发生当软管相对于其外壳以恒定速度 V 移动时，或者以恒定速度 V_x 和 V_y 独立地在 2 个方向上移动时，或者实际上使用任何非疯狂驱动系统时。）

软管延伸区域的左边缘怎么样？ U * g(i, j) - P是该区域的左边缘在时刻g(i,j)的位置。由于该时间是我们可以完成填充 j 个圆锥体的任务的最早可能时间，其中最后一个是圆锥体 i，因此该表达式给出了任务完成时软管到达区域的左边缘可能位于的最左边的可能位置完成了。因此，如果该位置仍然位于 x_i 的左侧，则意味着我们可以在 j-1 个较早的圆锥体之后填充圆锥体 i - 但如果不是，我们知道尝试这样做会迫使分配器太靠左（这可能会在尝试移动到圆锥体 i 或填充圆锥体时发生 - 这并不重要）。因此，在后一种情况下，我们将与任务 f(i, j) 相关的时间成本一直限制到无穷大，保证它不会被用作任何更大子问题的解决方案的一部分。

时间和空间使用

计算任何特定的 f(i, j) 值需要 O(n) 时间，因此计算所有这些值的 O(n^2) 时间需要 O(n^3) 时间。然而在实践中，我们几乎不需要考虑上述最小值中 k 小于 i 的所有可能值。除了确保 所隐含的运动顺序f(i, j)仍然可行之外，这max(e(i), ...)也是实际加速的关键：一旦我们发生 ak ，就会导致 e(i) 项“启动”（成为较大的） )中的两项进行比较max()，它仍然是最佳可行的选择 - 因为任何后续的 k 旨在允许更快地完成任务，必然涉及在最后一步中将分配器向右推得太远。这意味着我们不需要尝试任何其他 k 值：e(i) 确实是真正的最小值。

如果我们想要计算的是填充给定数量的圆锥体所需的最短时间，我们实际上可以在 O(n) 空间中完成它，利用计算 f(i, j) 时我们只需要曾经访问第二个参数等于 j-1 的 f() 的先前值。但由于我们真正想要的是与这样一个最小时间 对应的动作序列，所以我们需要记录一个前驱表 p[i][j]，这确实需要 O(n^2) 空间。

伪代码

Sort cone[1 .. n] by increasing x co-ord.
Compute e[i] for all 1 <= i <= n.
Set f[i][1] = e[i] + T for all 1 <= i <= n.
Set f[i][j] = infinity for all 1 <= i <= n, 2 <= j <= i.
maxCones = 0.
bestTime = infinity.

# Compute f(i, j) for all i, j.
For j from 2 up to n:
    For i from j up to n:
        g = infinity.             # Best time for f(i, j) so far.
        For k from j up to i-1:
            z = f[k][j-1] + m(k, i) + T.
            If z < g:
                p[i][j] = k.
                If z < e[i] + T:
                    g = e[i] + T.
                    Break out of innermost (k) loop.
                Else:
                    g = z.

        If U * g - P <= cone[i].x:
            f[i][j] = g.
            If maxCones < j or (maxCones == j and g < bestTime):
                maxCones = j.     # New record!
                bestI = i.
                bestTime = g.
        Else:
            f[i][j] = infinity.

# Trace back through p[][] to find the corresponding action sequence.
For j from maxCones down to 1:
    fill[j] = bestI.
    bestI = p[bestI][j].

运行后，maxCones将包含可以填充的最大圆锥体数量，如果 >= 1，则fill[1]throughfill[maxCones]将包含要填充的相应圆锥体 ID 序列maxCone（排序序列中的位置），以及所需的总时间将会在bestTime.

可能的增强功能

上述算法仅在分配器永远不会“太快”向后移动的限制下最优地解决问题。这在实践中可能会受到很大的限制：例如，如下所示的圆锥体图案

X X X X


 X X X X

将导致分配器在其填充的每个圆锥体之间进行较长的垂直移动（假设它能够填充所有圆锥体）。在同一行中填充多个圆锥体，然后再移动到另一行会节省大量时间。

在没有上述限制的情况下最优地解决该问题的困难在于，它开始看起来非常像某些 NP 难问题，例如欧几里得 TSP 问题。我没有时间寻找正式的简化，但我相信你的问题的无限制版本是 NP 难的，所以我们希望用多项式时间算法做的最好的事情就是寻找良好的启发式方法。为此：

上面的 DP 解决方案基本上找到了对于每个圆锥体 i ，总共填充 j 个圆锥体的最佳方式，以圆锥体 i 结束并仅使用其左侧的其他圆锥体。我们可以通过将已排序的锥体序列分解为 b 个锥体的连续块来解决稍微更一般的问题，然后为每个锥体 i 找到填充总共 j 个锥体的最佳方法，该方法在锥体 i 处结束并且仅使用锥体它们要么 (a) 在较早的块中（这些锥体必须位于 i 的左侧），要么 (b) 在与 i 相同的块中（这些锥体不一定位于 i 的左侧）。这种方法唯一忽略的解决方案是那些需要我们在某个块中填充圆锥体，然后在较早的块中填充圆锥体的解决方案（这特别包括我们在某个块中填充圆锥体，在某个块中填充圆锥体的所有解决方案）一个不同的块，然后再次在第一个块中出现另一个圆锥体——块之间的两次移动中至少有一个必须是到前一个块的移动）。

显然，如果我们选择 b = n，那么这将找到整体最优值（一百万年），但 b 不需要接近这么大就能获得最优解。使用O(n^2*2^n) DP 算法的变体来求解 TSP来帮助计算块内最优路径，例如选择 b = 10 将是非常可行的。

另一个建议是，不是将块大小固定为恰好 b，而是首先可以更智能地将圆锥体分割成大小最多为b 的块，也就是说，以这种方式（未知）最优解很少需要填充圆锥体在前一个块中。事实上，如果可以启发式地对断点“质量”进行评分（例如，通过使用 2 个块中任意一对点之间的最小距离），则可以在 O(bn) 时间内轻松完成计算最大化分数的阻塞模式，使用（不同的）DP！