分组项目(光纤终端)以最适合容器(光纤缓冲区)的算法

Question

我有一个有序列表，表示光缆上的终端，其中每个终端都有多个端口(例如4、8、12)。给定将向每个终端端口提供不同光纤束的光纤电缆。电缆可以包含编号为1-144的144根光纤股，以12根光纤为一组。我希望将光纤线束分配给终端端口，这样在任何一个终端上，我都不需要访问来自多个组的光纤。我想尽可能按照终端的顺序分配纤维。我想尽量避免使用不用的纤维束。

例如，如果我的终端A、B、C、D、E、F的端口大小分别为12、8、12、6、6、12，我希望算法生成结果A (1-12)、B (49-56)、C (13-24)、D (25-30)、E (31-36)、F (37-48)。

有没有人能推荐一个理想的算法？

Answer 1

问题是bin packing有排序的一面。单独装箱是NP难的，所以我要建议的确切算法的运行时间不是多项式的。无论如何，希望它是有用的。

第一步是生成所有可能的组。这里有一些Python来演示我的意思。

def allgroups(terminals, fibrecount=12, groupsofar=[]):
    if terminals:  # is nonempty
        terminal = terminals.pop()  # last element
        if terminal.portsize <= fibrecount:
            groupsofar.append(terminal)
            yield from allgroups(terminals, fibrecount - terminal.portsize, groupsofar)
            groupsofar.pop()  # terminal
        yield from allgroups(terminals, fibrecount, groupsofar)
        terminals.append(terminal)
    elif groupsofar:
        yield groupsofar

第二步是使用Algorithm X生成所有可能的分组，第三步是通过动态编程评估每个分组。您没有说“尽可能按照终端的顺序”是什么意思，所以我将尝试最小化inversions。实际上，准确的目标并不重要，只要它有最优子结构，即给定相同组的两个排序，无论其他组是如何排列的，其中一个总是比另一个更好。

在运行动态程序之前，对于每对组，如果第一个组出现在第二个组之前，则计算反转的数量。这意味着外部循环在第一组上迭代，内部循环在第二组上迭代，计算第一组中的终端应该在第二组中的终端之后出现的次数。现在，对于非降序的每个组的子集，确定该子集的最佳顺序。由于有最优子结构，最优顺序从子集中的某个组开始，以我们已经为其余部分计算的最优解结束。最小化优先选择哪一组。