0

我有一个有序列表，表示光纤电缆上的终端，其中每个终端都有多个端口（例如 4、8、12）。给定一根光纤电缆，它将为每个终端端口提供不同的光纤束。光缆可以包含 144 根纤维束，编号为 1-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)

谁能提出一个理想的算法？

4

1 回答 1

1

问题是装箱与订购的一面。单独装箱是 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

第二步是使用算法 X生成所有可能的分组，第三步是通过动态规划评估每个分组。你没有说“尽可能按终端的顺序”是什么意思，所以我会尽量减少inversions。实际上，只要它具有最佳子结构，确切的目标并不重要，即，给定相同组的两个排序，无论其他组如何排列，一个总是优于另一个。

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

于 2013-06-08T12:42:27.433 回答